The Array Data Structure
arrayis a collection of items stored in a contiguous location in memory.
Items in an array can be accessed with a numeric index, which maps to a memory address.
For example, the first item in an array can be accessed with index
example_array = [4, 3, 9, 7, 2]
Static arrays need to be initiatilized with a fixed size.
Dynamic arrays automatically resizes itself when needed. Many languages, such as python, support dynamic arays.
Array Big O Overview
- Fast lookup when index is known
- Cache friendly since elements are in contiguous locations in memory
- The runtime of appending an element is constant if there's extra space in the array
- Inserting an element may require copying all elements to a new array, taking
- Deleting an element requires all elements to scoot over to fill the gaps.
Dynamic arrays don't require a fixed size.
Instead, a dynamic array automatically resizes itself when it is about to run out of space.
When an element is appended to the end of a full array, the resize operation includes:
- Allocate a new array with double the current capacity
- Copy all elements over to the new array.
- Append the new element
Even if the worst case time and space required is
O(n), the amortized cost of appends is
- The resizing operation doubles the number of allowed appends.
- The need to allocate space reduces each time.
In Python, lists are dynamic arrays under the hood.
Let's set up an array.
colors = ['blue', 'purple', 'red']print(colors) # purple
The code above prints
purple, the second item in
Under the hood, an array's index maps to a location in memory where the item is stored. So accessing an single item in an array is done in constant O(n) time, which is fast since the memory address is known.
colors = ['blue', 'purple', 'red']for color in colors:print(color)
Iterating through all the items in an array is done in linear time, O(n).
arrayis the most fundamental data structure in computer science. Which is why it's commonly tested data structure in interviews.