The Array Data Structure

An array is 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 0.

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

Operation	Time	Space
Insert	O(n)	O(n)
Delete	O(n)	O(n)
Append	O(1)	O(1)
Lookup	O(1)	-

Array Pros

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

Array Cons

Inserting an element may require copying all elements to a new array, taking O(n) space and O(n) time.
Deleting an element requires all elements to scoot over to fill the gaps.

Dynamic Arrays

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 O(1) because:

The resizing operation doubles the number of allowed appends.
The need to allocate space reduces each time.

Python Arrays

In Python, lists are dynamic arrays under the hood.

Let's set up an array.

colors = ['blue', 'purple', 'red']
print(colors[1]) # purple

The code above prints purple, the second item in colors.

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).

An array is the most fundamental data structure in computer science. Which is why it's commonly tested data structure in interviews.

6 Essential Arrays Coding Interview Problems

Master Arrays by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.