Arrays and Dynamic Arrays
How arrays sit in memory, why indexing is instant, and how a growable array amortizes its cost.
beginner35 min#arrays#memory#amortized-analysis
Why it matters
Arrays are the default container of almost every program, and many other structures (hash tables, heaps, stacks, queues, matrices, even the vectors behind AI embeddings) are built on top of one. Interviewers love them because a small change in the problem (sorted? duplicates? in-place?) changes the best solution.
Intuition
Picture a row of numbered lockers, all the same size, built side by side. If you know the number of the first locker and the size of each, you can walk straight to locker i without opening any other: address = start + i * size. That single multiplication is why reading a[i] takes the same time whether the array holds ten items or ten million.
The price is rigidity. Lockers are contiguous, so inserting in the middle means sliding every later item over by one, and the row cannot grow if something else sits right after it.
How it works
- Contiguous memory: items are stored back to back, which is also very friendly to CPU caches.
- Fixed capacity: a low-level array has a size decided up front.
- Dynamic array: Python's
listand JavaScript'sArrayhide a fixed array behind a wrapper. When it fills up, the wrapper allocates a bigger block (typically about twice the size), copies everything, and carries on.
Growing by a constant factor makes appends cheap on average. If the capacity doubles each time, copies happen at sizes 1, 2, 4, 8, ... and the total copying work for n appends is about 2n. Spread over n appends, that is O(1) each. This is called amortized O(1).
A dynamic array of capacity 4 receiving a 5th item. Click Next to step through.
| Operation | Time | Notes |
|---|---|---|
| Read / write a[i] | O(1) | Address arithmetic |
| Append at end | O(1) amortized | Occasional O(n) resize |
| Insert / delete at index i | O(n) | Shifts later items |
| Search unsorted | O(n) | Check each item |
| Search sorted (binary search) | O(log n) | Halve the range each step |
Code: build a dynamic array
The best way to understand the table above is to build the wrapper yourself. Python's list already does this, so we use a plain list only as raw storage and never call its growth features.
class DynamicArray:
def __init__(self):
self._capacity = 4
self._size = 0
self._data = [None] * self._capacity # raw fixed-size storage
def __len__(self):
return self._size
def __getitem__(self, i):
if not 0 <= i < self._size:
raise IndexError("index out of range")
return self._data[i]
def append(self, value):
if self._size == self._capacity:
self._resize(self._capacity * 2)
self._data[self._size] = value
self._size += 1
def insert(self, i, value):
if not 0 <= i <= self._size:
raise IndexError("index out of range")
if self._size == self._capacity:
self._resize(self._capacity * 2)
for j in range(self._size, i, -1): # shift right: O(n)
self._data[j] = self._data[j - 1]
self._data[i] = value
self._size += 1
def pop(self):
if self._size == 0:
raise IndexError("pop from empty array")
value = self._data[self._size - 1]
self._data[self._size - 1] = None
self._size -= 1
if self._capacity > 4 and self._size <= self._capacity // 4:
self._resize(self._capacity // 2) # shrink at 1/4 to avoid thrashing
return value
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
arr = DynamicArray()
for n in range(10):
arr.append(n * n)
arr.insert(2, 99)
print(len(arr), arr[2], arr.pop())class DynamicArray {
constructor() {
this.capacity = 4;
this.size = 0;
this.data = new Array(this.capacity); // raw fixed-size storage
}
get(i) {
if (i < 0 || i >= this.size) throw new RangeError("index out of range");
return this.data[i];
}
append(value) {
if (this.size === this.capacity) this.#resize(this.capacity * 2);
this.data[this.size++] = value;
}
insert(i, value) {
if (i < 0 || i > this.size) throw new RangeError("index out of range");
if (this.size === this.capacity) this.#resize(this.capacity * 2);
for (let j = this.size; j > i; j--) this.data[j] = this.data[j - 1]; // O(n)
this.data[i] = value;
this.size++;
}
pop() {
if (this.size === 0) throw new RangeError("pop from empty array");
const value = this.data[--this.size];
this.data[this.size] = undefined;
if (this.capacity > 4 && this.size <= this.capacity / 4) {
this.#resize(this.capacity / 2); // shrink at 1/4 to avoid thrashing
}
return value;
}
#resize(newCapacity) {
const next = new Array(newCapacity);
for (let i = 0; i < this.size; i++) next[i] = this.data[i];
this.data = next;
this.capacity = newCapacity;
}
}
const arr = new DynamicArray();
for (let n = 0; n < 10; n++) arr.append(n * n);
arr.insert(2, 99);
console.log(arr.size, arr.get(2), arr.pop());Both versions print 11 99 81.
Common pitfalls
- Off-by-one errors: valid indexes are
0ton - 1. Insert allowsn(the end); read does not. - Mutating while looping: removing items from a list you are iterating skips elements. Build a new list or loop backwards.
- Hidden O(n):
list.insert(0, x)in Python andarray.shift()orunshift()in JavaScript shift every item. Use adequeor an index pointer for queues. - Copy vs reference:
b = adoes not copy the array. Usea[:]/list(a)in Python or[...a]/a.slice()in JavaScript, and remember these are shallow copies.
Practice
Two Sum (sorted input) easy
Hint
Keep one pointer at each end. If the sum is too small, which pointer should move?
Show solution
Use two pointers. Start l = 0, r = n - 1. If a[l] + a[r] equals the target, return the pair; if it is smaller, move l right to increase the sum; otherwise move r left. Each step discards at least one candidate, so the time is O(n) and the extra space is O(1).
Remove duplicates in place medium
Hint
Use a slow pointer for where the next unique value goes and a fast pointer that scans.
Show solution
For a sorted array, keep write = 1. For each read from 1 to n - 1, if a[read] != a[read - 1] copy it to a[write] and increment write. Return write. O(n) time, O(1) space.
Rotate an array by k medium
Hint
Reversing is its own inverse. How many reversals give a rotation?
Show solution
Reverse the whole array, then reverse the first k % n items, then reverse the rest. Three O(n) passes, O(1) extra space.
Interview questions
- Why is array indexing O(1) but insertion O(n)? Indexing is address arithmetic; insertion shifts every later element.
- Why is
appendamortized O(1) and not O(1)? An occasional append triggers an O(n) resize; averaged over many appends the cost per append is constant. - When would you pick a linked list over an array? Rarely in practice. Mainly when you hold node references and need O(1) splicing, or must never invalidate references. Arrays win on cache locality for most workloads.
Interviewers look for: stating complexity unprompted, asking whether the input is sorted or can contain duplicates, and handling the empty array and single-element cases.
Quick check
You append 1,000,000 items to a dynamic array that doubles when full. Roughly how many total element copies happen during resizes?
Finished this lesson?
Further resources
- Dynamic array (Wikipedia) (article)
- Python tutorial: lists (docs)
- MDN: Array (docs)