Data Structures

Date: September 28 2021

Summary: An overview of asymptotic notation and time complexity

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

Bibliography

Not Available

Table of Contents

Arrays

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 $\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 $10$ objects into an array of size $5$, the array will need to be expanded.

ArrayList

Characteristics

• A type of List Abstract Data Type backed by an array.

- Really just a wrapper around arrays

• ArrayLists are expanded when reaching capacity

- 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

Definitions

• size - the number of data (non-null) stored in an ArrayList.

• capacity - number of data that can be stored in an ArrayList without resize

• Amortized Analysis - looks at the cost over time rather than cost per add operation

Requirements

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

• Examples:

- 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. https://jacobzelko.com/10012021003603-data-structures. September 28 2021.

References

Discussion: