FundamentalsData structureaka vector, ArrayList, resizable array, growable array, list (Python)

Dynamic Array

An array that grows automatically by doubling its capacity, giving amortized O(1) append with O(1) indexed access.

Pattern: Two PointersPractice (4)
Progress

Definition

A dynamic array wraps a plain Array with two numbers: size (elements in use) and capacity (slots allocated). Appends write into spare capacity; when it runs out, the structure allocates a new block twice as large, copies everything over, and continues.

Doubling makes the expensive copies rare enough that the total work of n appends is O(n) — amortized `O(1)` per append — while indexed access stays O(1). This is std::vector in C++, ArrayList in Java, list in Python, [] in JavaScript, and slices in Go.

It is the most used container in practice because it keeps the cache-friendliness of arrays while removing the fixed-size constraint. Its remaining weakness is the same as a static array: inserting or deleting in the middle costs O(n).

amortizeddoublingvectorArrayListresizingcontiguous

Intuition

A mental model before the formal terms.

Imagine packing books into a box. When the box is full you do not buy a box one book bigger — you buy one twice the size and move everything once. As the box grows you move books less and less often, so on average each book is handled only about two or three times over its lifetime, no matter how many books you own.

Compare that with growing by a fixed 10 slots each time: you would re-pack every 10 books, and the total moves would add up to n²/20 — quadratic. Doubling (or any constant factor > 1) is what keeps the total linear.

How it works

  1. Keep data (a raw array), size and capacity. Initially capacity is small (e.g. 4 or 8) and size = 0.
  2. push(v): if size == capacity, call grow(); then data[size] = v; size++.
  3. grow(): allocate a new array of 2 * capacity (or 1 if capacity was 0), copy data[0..size-1] into it, replace data and update capacity.
  4. pop(): size-- and return data[size]. Optionally shrink when size <= capacity / 4 to keep memory proportional to size without thrashing.
  5. get(i) / set(i, v): bounds-check 0 <= i < size, then direct index. insertAt / deleteAt shift elements exactly like a static array.

Why it works

Amortized analysis: with doubling, the k-th resize copies 2^k elements. Reaching size n triggers resizes copying 1 + 2 + 4 + … + n ≤ 2n elements in total. Dividing by n appends gives at most 2 extra copies per element — a constant.

The accounting view: charge each append 3 units — one to write the element, two saved for a future copy of itself and of an older element. When a resize copies c elements, the c/2 newest each paid 2 units, exactly covering all c moves.

Shrinking at 1/4 (not 1/2) full avoids oscillation: after shrinking to half capacity the array is exactly half full, so it needs size/2 pushes before growing again or size/4 pops before shrinking again — both Θ(size), so each resize is still paid for.

Operations

OperationDescriptionCost
get(i) / set(i, v)Direct indexed access with bounds check 0 <= i < size.O(1)
push(v)Append at data[size]; doubles capacity first if full.O(1) amortized, O(n) worst
pop()Remove and return the last element; optionally shrink at 1/4 occupancy.O(1) amortized
insertAt(i, v)Grow if needed, shift data[i..size-1] right, write v.O(n)
deleteAt(i)Shift data[i+1..size-1] left and decrement size.O(n)
search(v)Linear scan; O(log n) with binary search if kept sorted.O(n)
grow()Allocate 2 * capacity, copy size elements.O(n)

Recognition

How to tell a problem wants this.

  • You need to collect results whose count is unknown in advance (filtered output, BFS frontier, path reconstruction).
  • The language's built-in list/vector is being used as a stack (push/pop at the end).
  • The problem mentions amortized complexity, "why is append fast?", or asks you to implement ArrayList / vector.
“sorted array” → Two Pointers“have you seen this before” → Hashing“balanced parentheses” → Stack

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1class DynamicArray:
2  data = allocate(4); size = 0; capacity = 4
3  push(v):
4    if size == capacity: grow()
5    data[size] = v; size += 1
6  grow():
7    bigger = allocate(2 * capacity)
8    copy data[0..size-1] into bigger
9    data = bigger; capacity *= 2
10  pop():
11    size -= 1; v = data[size]
12    if size <= capacity / 4 and capacity > 4: shrink to capacity / 2
13    return v
14  get(i): assert 0 <= i < size; return data[i]

Implementation

1from typing import Generic, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class DynamicArray(Generic[T]):
7    """Growable array; Python's built-in list already does exactly this."""
8 
91 · Storage, size and capacity
10    def __init__(self, initial: int = 4) -> None:
11        self._data: list[T | None] = [None] * initial
12        self._n = 0
13        self._cap = initial
14 
15    def __len__(self) -> int:
16        return self._n
17 
18    @property
19    def capacity(self) -> int:
20        return self._cap
21 
222 · Resize by copying into a new block
23    def _resize(self, new_cap: int) -> None:
24        bigger: list[T | None] = [None] * new_cap
25        for i in range(self._n):
26            bigger[i] = self._data[i]
27        self._data = bigger
28        self._cap = new_cap
29 
303 · Push (amortized O(1))
31    def push(self, value: T) -> None:
32        if self._n == self._cap:
33            self._resize(self._cap * 2)
34        self._data[self._n] = value
35        self._n += 1
36 
374 · Pop with shrink
38    def pop(self) -> T:
39        if self._n == 0:
40            raise IndexError("pop from empty array")
41        self._n -= 1
42        value = self._data[self._n]
43        self._data[self._n] = None
44        if self._cap > 4 and self._n <= self._cap // 4:
45            self._resize(self._cap // 2)
46        return value  # type: ignore[return-value]
47 
485 · Bounds-checked access
49    def get(self, i: int) -> T:
50        if not 0 <= i < self._n:
51            raise IndexError(i)
52        return self._data[i]  # type: ignore[return-value]
53 
54    def set(self, i: int, value: T) -> None:
55        if not 0 <= i < self._n:
56            raise IndexError(i)
57        self._data[i] = value
Walkthrough
  1. [None] * initial is the backing block; _n and _cap track logical and allocated size.
  2. _resize copies live slots into a bigger (or smaller) list — CPython does this in C inside list_resize.
  3. push doubles when full, then stores at _n; this is what list.append does with a ~1.125x growth factor.
  4. pop clears the slot and halves capacity at 25% usage; CPython also shrinks when a list drops below half.
  5. get/set reject negative indices, unlike list, to keep the teaching model simple.
Complexity (this implementation)
time O(1) amortized push/pop, O(1) access · space O(n)

CPython over-allocates by about 12.5%, so more reallocations happen than with doubling, but each is a fast C memcpy of pointers.

Language notes
  • Python list is a dynamic array of object pointers; append/pop() are amortized O(1), insert(0, x)/pop(0) are O(n).
  • sys.getsizeof(lst) shows the over-allocation growing in steps.
  • For a queue use collections.deque; for dense numbers use array.array or NumPy.
Common mistakes in this language
  • Using lst.pop(0) in a loop — O(n) per call.
  • Building a list with lst = lst + [x] in a loop — copies every time, O(n^2).
  • Assuming a list comprehension pre-sizes the result; it still grows incrementally (though faster than append).
Language differences that matter here
  • Growth factor: libstdc++ std::vector doubles, MSVC uses 1.5x, V8 uses ~1.5x + 16, CPython list uses ~1.125x — all are amortized O(1) per append.
  • Only C++ exposes capacity()/reserve()/shrink_to_fit(); JS and Python hide the backing store entirely.
  • Reallocation invalidates C++ iterators and references; JS and Python references stay valid because they point at objects, not slots.
  • Popping from empty: C++ is undefined behaviour, JS returns undefined, Python raises IndexError.

Complexity

OperationAverageWorstNote
AccessO(1)O(1)
SearchO(n)O(n)
InsertO(n)O(n)Middle insert shifts; see Push for the end.
DeleteO(n)O(n)O(1) amortized at the end (Pop).
UpdateO(1)O(1)
Push (append)O(1) amortizedO(n)Worst case is the resize copy.
PopO(1) amortizedO(n)O(n) only when shrinking.
ResizeO(n)O(n)
SpaceO(n)Capacity is at most 2n right after growth and at least n/4 with shrinking; memory is Θ(n).

Advantages & disadvantages

Advantages
  • Amortized O(1) append with O(1) random access — the best of arrays without a fixed size.
  • Contiguous memory: cache-friendly iteration and low overhead (no per-element pointers, unlike Linked List).
  • Ubiquitous: every mainstream language provides one as the default sequence type.
  • Doubles as an efficient Stack.
Disadvantages
  • Individual appends can be O(n) when a resize happens — unacceptable in hard real-time code.
  • Up to 50% of allocated memory may be unused right after a resize (with doubling).
  • Insert/delete in the middle is O(n); insert at the front is O(n) (use a Deque for that).
  • Resizing invalidates raw pointers/iterators into the old buffer (C++), a classic source of bugs.

Use cases

  • Default collection for building up results, adjacency lists (Adjacency List), and DP tables of unknown length.
  • Stack implementation (push/pop at the back).
  • Backing storage for a Binary Heap / Priority Queue and for Hash Table bucket arrays that rehash on growth.
  • String builders that accumulate characters before a final join.
Use it when
  • Default choice for any sequence whose length is not known in advance.
  • Stack-like access (push/pop at the end) with occasional random access.
  • You want array performance (cache locality, O(1) index) without managing capacity yourself.
Avoid it when
  • Frequent insert/delete at the front or middle — use a Deque (front) or a Linked List / balanced tree (middle by position).
  • Strict per-operation latency bounds — a single append may trigger an O(n) copy.
  • Keyed lookups — use a Hash Map; sorted-order queries — use a Binary Search Tree or keep the array sorted with Binary Search inserts.

Alternatives

ArrayLinked ListDequeSkip List

Common mistakes

  • Growing by a constant amount (e.g. +10) instead of a constant factor — total append cost becomes O(n²).
  • Shrinking at 1/2 occupancy — a push/pop sequence at the boundary then resizes on every operation (thrashing).
  • Holding a pointer/iterator across a push in C++ and reading freed memory after a resize.
  • Calling insert(0, x) in a loop and expecting O(n) total; it is O(n²).
  • Quoting O(1) append without the word "amortized" when asked about worst case.

Interview patterns

  • "Implement ArrayList/vector" — write push with doubling and explain the amortized bound.
  • Using a list as a stack for parentheses matching, monotonic stacks and DFS.
  • Building an Adjacency List as an array of dynamic arrays.
  • O(1) delete by swapping with the last element and popping (insert/delete/getRandom in O(1)).
Interview questions on this
Mock interviews

Interview problems

Insert Delete GetRandom O(1)mediumValid ParentheseseasyMin StackmediumDaily Temperaturesmedium