What is an Array?
An array is a data structure that contains a group of equally-sized elements, organized sequentially in a contiguous area of memory. Items in an array are indexed to allow for efficient lookup.
There are two main types of arrays; static arrays and dynamic arrays. Some programming languages, default to using dynamic arrays (Python lists), while others encourage you to specify the size at the point of creation (C# arrays).
This guide walks you through everything you need to know about the array data structure, with clear, commented code samples.
- When to use an array
- Pros and cons of arrays
- Big O time complexity of operations
- Static vs. dynamic arrays
- Create an array in Python
- Leetcode array questions
When to Use an Array
If you need to store and iterate over data, arrays are often the best data structure to use. They’re also an excellent choice for lookups, as elements can be accessed directly using their index. e.g. arr[0]
However, arrays are not the best option if you need to frequently insert and delete items from the middle of the array. That’s because each delete and insert requires a shift of the other items in the array.
If you need to frequently insert and delete items, a linked list offers better performance.
Although linked list nodes have the overhead of storing a pointer to the next node, this is often more memory efficient than declaring a very large array with most elements left empty.
Pros and Cons of Arrays
- Fast lookups
- Fast push/pop
- Ordered
- Slow inserts
- Slow deletes
- Fixed size if using static array
Big O Time Complexity of Operations
| Operation | Big O |
|---|---|
| Lookup | O(1) |
| Push | O(1) |
| Insert | O(n) |
| Delete | O(n) |
| Search | O(n) |
The ‘push’ operation can only be done in constant time if the array still has space to hold the item.
In a worst-case situation, if the ‘push’ operation exceeds the size of our array, it must be dynamically resized, which is an operation with linear O(n) time complexity.
Because this resizing operation happens so rarely, we say that the amortized cost of an insert or delete is O(1).
Static vs. Dynamic Arrays
Static Arrays
The size of a static array must be declared at the point of creation.
Properties of a static array:
- Must specify size ahead of time. e.g. C++: int a[20]
- Guarantees we can reserve consecutive slots in memory
If the number of items to be added to the static array exceeds the defined size:
- Create a copy of the array large enough to hold current items and new items
- Copy items from original array into new array
- Add the new items into the new array
- Update array pointer to point to new array
- Dispose of the old array
A random-access data structure that is of fixed size. “Adding” or “deleting” an element from an array requires creating an appropriately sized contiguous chunk of memory, and copying the elements that you want to keep into the new array.
Strengths
- The item lookup by index for arrays is very quick – O(1).
- Only use the memory we actually need. No empty elements.
Weaknesses
- Slow to add new items or remove existing ones. Requires copying and array creation each time.
Time Complexity of Common Operations
| Operation | Description | Time complexity |
|---|---|---|
| append(item) | Adds item to the end of the array | O(n) |
| delete(index) | Removes item from array | O(n) |
| access | Retrieves element at index | O(1) |
| search | Search for an element | O(n) |
Dynamic Array
The main advantage that dynamic arrays have over static arrays is they support automatic resizing, with space reserved for additional elements.
This means you don’t have to create a new array, copy elements from the old array to the new array, then delete the old array each time you add or delete, the way you do with a static array.
If the number of items to be added to the dynamic array exceeds the current limit:
- Create a copy of the array, twice the size
- Copy items from original array into new array
- Update array pointer to point to new dynamic array
- Dispose of the old array
Useful terms
- Logical size
The number of elements being used by the array’s contents. - Physical size
The size of the underlying array, counted in either the number of elements it has room for, or the number of bytes used.
Strengths
- The item lookup by index for arrays is very quick – O(1).
- On average, appending elements to the end of the dynamic array is quick.
Weaknesses
- Have inconsistent run times for adding to the array.
- Requires empty space to be reserved in memory in anticipation of new elements being added.
Time Complexity of Common Operations
| Operation | Description | Time complexity |
|---|---|---|
| append(item) | Adds item to the end of the array | O(1) (amortized) |
| delete(index) | Removes item from array | O(n) |
| delete(index) | Removes last item from array | O(1) |
| access | Retrieves element at index | O(1) |
| search | Search for an element | O(n) |
Deleting the last item from a dynamic array is O(1) constant time, as it doesn’t require any shifting. It also doesn’t require the process of creating a new array and copying elements over, which is necessary with a static array.
Python and Javascript automatically re-allocate memory. Python lists are an example of dynamic arrays.
Create an Array in Python
A Python list is an example of a dynamic array. There’s no need to specify the size ahead of time, and the size automatically adjusts depending on the number of items you add and remove.
strings = ['a', 'b', 'c', 'd']
strings[2] # lookup O(1)
strings.append('e') # push O(1), or O(n) if add item larger than capacity
strings.pop() # pop O(1)
strings.insert(0, '0') # insert: O(n). Requires a shift of items up
del strings(0) # delete: O(n). Requires a shift of items back
