the cedar ledge

Data Structures

Date: September 28 2021

Summary: An overview of asymptotic notation and time complexity

Keywords: ##summary #data #structures #abstract #types #archive


Not Available

Table of Contents

    1. Arrays
    2. ArrayList
      1. Characteristics
      2. Definitions
      3. Requirements
      4. Amortized Analysis
  1. How To Cite
  2. References
  3. Discussion:


Arrays are: - Statically allocated (they are stored in memory and do not change; values can tho) - Contiguous blocks of memory (meaning that they are stored end to end in memory)

They provide constant complexity of O(1)\mathcal{O}(1) when accessing data at a specific index in memory.

They are of particular use in storing sequences of related items. However, they are not very efficient when dealing with dynamically changing sizes for elements. If you try to fit 1010 objects into an array of size 55, the array will need to be expanded.



- Really just a wrapper around arrays
- Handled automatically by implementation
- Dynamically allocated via moving data to be copied when more space for the data is needed
	- This takes $\mathcal{O}(n)$ time to do



  1. Data must be contiguous (no gaps between data).

  2. Data must be zero-aligned (meaning that all values from zero to the end of the list, must be filled with data).

  3. Size should be stored for efficiency.

NOTE: The empty blocks in the ArrayList sketch contain NULLs

Amortized Analysis

- Insertion:
	- Adding to the back of an ArrayList is $\mathcal{O}(1)$
	- Adding at an arbitrary position in the ArrayList is $\mathcal{O}(n)$
		- This is because when an element is inserted, the rest of the data in the list must be shifted to accommodate for the new data
- Removing examples:
	- Removing from back of ArrayList is $\mathcal{O}(1)$
	- Removing at arbitrary position in ArrayList is $\mathcal{O}(n)$

How To Cite

Zelko, Jacob. Data Structures. September 28 2021.



CC BY-SA 4.0 Jacob Zelko. Last modified: May 19, 2024. Website built with Franklin.jl and the Julia programming language.