2.1 Arrays

Prerequisite: Asymptotic Bounds, Recurrences, and Amortized Analysis, about 35 minutes. This lesson puts index, size, capacity, movement count, and amortized cost into one dynamic-array contract.

The Array's First Contract

Start by separating size from capacity: the former is the current element count, while the latter is how many elements the allocated storage can hold. The names look harmlessly similar; confusing them produces remarkably energetic bugs.

Split "Arrays" into Three Layers

Abstract Array

An abstract array is a collection of slots indexed by integers. As long as the index is valid, you can directly read from or write to that slot.

Index:   0      1      2      3      4
       ┌──────┬──────┬──────┬──────┬──────┐
Value: │  10  │  20  │  30  │  40  │  50  │
       └──────┴──────┴──────┴──────┴──────┘

Fixed-Size Array

Once created, its length cannot change. Java's int[] and C++'s std::array<int, N> fall into this category. You can modify elements, but you cannot change the length from 5 to 6; to add more slots, you must create a new array and copy the contents over.

Python does not have a built-in fixed-length container that matches Java's native arrays exactly. A tuple has immutable length, but its elements cannot be replaced; list and array.array both support resizing. Calling array.array a static array is inaccurate: Python documents it as a mutable sequence constrained by a type code.

Dynamic Array

A dynamic array maintains two integers:

• size is the current number of stored elements.
• capacity is the total number of slots the current buffer can hold.

As long as size < capacity, appending to the end can directly write into the next available slot. When the buffer is full, the container allocates a larger contiguous block of slots, moves the existing elements over, and then writes the new element.

size = 3, capacity = 5

       ┌──────┬──────┬──────┬──────┬──────┐
Slot:  │  10  │  20  │  30  │ free │ free │
       └──────┴──────┴──────┴──────┴──────┘

Python's list, Java's ArrayList, and C++'s std::vector all belong to the dynamic array family, though they differ in element representation, growth strategies, and rules for element invalidation.

Why index access is Θ(1)

If each slot width is fixed, the conceptual address can be written as:

address(k) = base + k × slot_width

In the unit-cost RAM model, this requires only a fixed number of arithmetic operations, boundary checks, and one slot access; the work does not grow with the array length n, so it is Θ(1).

This formula is a model, not a guarantee that it will compile into exactly one multiplication and one addition machine instruction. The compiler, addressing modes, element representation, and runtime can all alter the generated instructions.

CPython’s list implementation stores object references in contiguous slots; the integers or custom objects they refer to may live elsewhere. values[k] can still access the kth reference in constant time, but this doesn't mean all object contents are arranged in contiguous blocks.

A Runnable Dynamic Array Model

The following Python 3.10+ class implements the operations used in this chapter. It doubles capacity when full. The returned movement count covers suffix shifts during insertion or deletion; it excludes copying during growth and initializing new slots. Doubling belongs to this teaching model, not to a fixed growth contract for Python, Java, or C++.

Reads and pop accept negative indices. insert accepts only 0 ≤ i ≤ size; it does not clamp out-of-range positions as the built-in list does. operator.index checks integer indices before any mutation, so an invalid insertion cannot trigger a resize first.

# dynamic_array_demo.py
from operator import index as integer_index

class DynamicArray:
    def __init__(self, initial_capacity: int = 2) -> None:
        initial_capacity = integer_index(initial_capacity)
        if initial_capacity <= 0:
            raise ValueError("initial capacity must be positive")
        self._buffer: list[object | None] = [None] * initial_capacity
        self._size = 0
        self.growths: list[tuple[int, int]] = []

    @property
    def size(self) -> int:
        return self._size

    @property
    def capacity(self) -> int:
        return len(self._buffer)

    def _grow(self) -> None:
        old_capacity = self.capacity
        new_capacity = old_capacity * 2
        new_buffer: list[object | None] = [None] * new_capacity
        for index in range(self._size):
            new_buffer[index] = self._buffer[index]
        self._buffer = new_buffer
        self.growths.append((old_capacity, new_capacity))

    def _check_index(self, index: int) -> None:
        if index < 0 or index >= self._size:
            raise IndexError("index out of range")

    def append(self, value: object) -> None:
        if self._size == self.capacity:
            self._grow()
        self._buffer[self._size] = value
        self._size += 1

    def insert(self, index: int, value: object) -> int:
        index = integer_index(index)
        if index < 0 or index > self._size:
            raise IndexError("insert index out of range")
        if self._size == self.capacity:
            self._grow()

        movements = self._size - index
        for position in range(self._size, index, -1):
            self._buffer[position] = self._buffer[position - 1]
        self._buffer[index] = value
        self._size += 1
        return movements

    def pop(self, index: int = -1) -> tuple[object, int]:
        index = integer_index(index)
        if index < 0:
            index += self._size
        self._check_index(index)

        value = self._buffer[index]
        movements = self._size - index - 1
        for position in range(index, self._size - 1):
            self._buffer[position] = self._buffer[position + 1]
        self._size -= 1
        self._buffer[self._size] = None
        return value, movements

    def __getitem__(self, index: int) -> object:
        index = integer_index(index)
        if index < 0:
            index += self._size
        self._check_index(index)
        return self._buffer[index]

    def to_list(self) -> list[object]:
        return [self._buffer[index] for index in range(self._size)]

def main() -> None:
    values = DynamicArray(2)
    for value in (10, 20, 30, 40):
        values.append(value)
    insert_movements = values.insert(1, 15)
    removed, delete_movements = values.pop(2)

    assert values.growths == [(2, 4), (4, 8)]
    assert insert_movements == 3
    assert (removed, delete_movements) == (20, 2)
    assert values.to_list() == [10, 15, 30, 40]
    assert values.capacity == 8

    for old, new in values.growths:
        print(f"Resize: {old} → {new}")
    print(f"Insert move: {insert_movements}")
    print(f"Delete move: {delete_movements}")
    print(f"Contents: {values.to_list()}")
    print(f"Capacity: {values.capacity}")
    print("Array check passed")

if __name__ == "__main__":
    main()

Run:

python3 dynamic_array_demo.py

Output:

Resize: 2 → 4
Resize: 4 → 8
Insert move: 3
Delete move: 2
Contents: [10, 15, 30, 40]
Capacity: 8
Array check passed

This output separates four distinct cost components:

• The third and fifth writes encounter a full buffer, triggering a copy operation.
• Insertion at index 1 first copies four old slots during growth, then shifts three suffix elements right. The reported 3 counts only the latter.
• When deleting at index 2, the two subsequent elements shift left.
• No active shrinking occurs after deletion, so the capacity remains at 8. Whether a real container shrinks is determined by its own growth contract.

Cost of Operations on Dynamic Arrays

Let the logical length of the array before an insertion or deletion be n.

Operation	More Precise Workload	Common Worst-Case Bound	Explanation
Read or modify element at index i	Constant	Θ(1)	Excludes cost of element manipulation
Append to end, no resizing required	Constant	Θ(1)	Write into a single empty slot
Append to end, triggering resize	Copy n slots	Θ(n)	Worst-case in a single operation
Sequential appends	Total copy count grows linearly	Amortized Θ(1) per operation	Start empty with fixed initial capacity and grow by a fixed factor
Insert at index i	Move n - i slots	Θ(n)	Growth copies old slots in addition to shifting the suffix
Delete element at index i	Move n - i - 1 slots	Θ(n)	Deletion at the end avoids moving a suffix
Unordered value lookup	Up to n comparisons	Θ(n)	Best case may hit the first element
Copy a range of length k	Copy k slots	Θ(k)	Also produces Θ(k) output space

Without growth, inserting one element at index i costs Θ(n - i + 1): shift the suffix, then write the new value. The extra 1 preserves the constant cost of a tail insertion. If growth occurs, copying and initialization raise this operation’s cost to Θ(n).

Creating this example’s array with capacity c initializes c slots and takes Θ(c) time and storage. It never shrinks, so memory after deletion depends on capacity, not just the remaining size. growths is a diagnostic log of resizes.

Why Amortized Cost Works Θ(1)

Start with an empty array and a fixed initial capacity, and grow by a fixed factor greater than 1. Under doubling, the total copying across n consecutive appends is less than:

1 + 2 + 4 + ... < 2n

Initializing new buffers also forms a geometric series. Adding the first write of each element gives Θ(n) total work. Splitting this cost across n appends, each append incurs an amortized cost of Θ(1).

This does not rely on randomness, nor does it imply that every append operation has a constant worst-case cost. An append that triggers a resize still copies existing elements.

Do not treat the specific growth factor as a language guarantee:

• CPython can adjust its over-allocation strategy for list.
• Java ArrayList only exposes the amortized constant cost of append operations, not the fixed growth factor.
• The C++ standard requires vector to satisfy the required complexity and contiguity guarantees, without specifying the exact growth factor.

Search, Sort, and Maintain Order

Searching in an unsorted array requires a full scan in the worst case, taking time Θ(n). After sorting, binary search becomes possible with worst-case time Θ(log n), but two common costs are easily overlooked:

1. For distinct elements with no extra restrictions, comparison sorting requires Ω(n log n) comparisons in the worst case; merge sort achieves Θ(n log n). This is not a bound on every individual input.
2. If the array must remain sorted and an element is inserted at position i, the suffix must still be shifted, resulting in a worst-case cost of Θ(n).

Thus, "binary search is fast" does not automatically imply that a sorted array is suitable for frequent insertions. First, consider the ratio of reads to updates.

Copying, Slicing, and Views

Python list slicing creates a shallow copy:

original = [[1], [2], [3]]
copied = original[1:]
copied[0].append(99)

print(original)  # [[1], [2, 99], [3]]

The slice copies references, not recursively copying the objects they point to. Copying k references requires Θ(k) time and new list memory.

Range APIs in different languages may return either copies or views. Java's subList is a view supported by the original list; C++ iterators do not copy elements when describing a range. Before using these APIs, check how changes propagate, how long the backing data lives, and when views become invalid.

Two-dimensional data doesn't necessarily mean a rectangular block of memory

This Python code appears to create three rows, but in reality it only creates one inner list and assigns the same reference three times:

wrong = [[0] * 3] * 3
wrong[0][0] = 7
print(wrong)  # [[7, 0, 0], [7, 0, 0], [7, 0, 0]]

Using a list comprehension to create independent rows:

matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 7
print(matrix)  # [[7, 0, 0], [0, 0, 0], [0, 0, 0]]

Python list-of-lists and Java arrays-of-arrays are both nested-reference structures, so you can't directly apply the assumption that "a whole matrix is stored row-wise in contiguous memory." Native multidimensional arrays in C and C++, as well as numerical libraries like NumPy, have their own well-defined memory layouts. Before analyzing row-major or column-major traversal, you must first confirm the actual representation.

Contiguous Slots and Cache Locality

Adjacent slots in arrays help processors use spatial locality and prefetching. Sequential traversal is often more cache-friendly than chasing scattered elements. The use of the word "often" here is intentional:

• Cache line sizes and hierarchies vary by processor architecture.
• CPython list stores references in contiguous slots; the objects they refer to may still be scattered.
• Element size, access stride, branching patterns, allocators, and data scale all influence performance outcomes.

Therefore, this chapter does not provide a fixed "how much faster" or a universal memory latency. Complexity is used to assess scalability, and benchmarks compare implementations using representative real-world workloads. Details on cache behavior can be explored further in Vol. 3: Caches and Memory Hierarchy.

Correspondences Across Languages

Requirement	Python	Java 17+	C++
General dynamic sequence	list	ArrayList<E>	std::vector<T>
Fixed length	Length is agreed upon and not changed; no direct built-in equivalent	T[]	std::array<T, N>
Compact homogeneous numeric values	array.array	Native numeric array	std::vector<T> / std::array<T, N>
Frequent insertion and removal at both ends	collections.deque	ArrayDeque<E>	std::deque<T>

The contiguous-element model for std::vector<T> assumes T is not bool. vector<bool> may pack bits and does not provide a contiguous array of bool objects.

A few verifiable contracts:

• The Python official tutorial notes that list.insert(0, value) and pop(0) shift other elements and recommends using collections.deque for queues. array.array is a mutable sequence of homogeneous values.
• Java's ArrayList provides constant-time indexing and amortized constant-time appending. ensureCapacity may reduce progressive reallocation, but capacity is not equal to list size.
• C++'s vector::reserve(n) prevents subsequent insertions from reallocating until an insertion would exceed the current capacity. When reallocation happens, element references, pointers, and iterators become invalid. Without reallocation, references, pointers, and iterators at or after the insertion point still become invalid. The standard draft specifies these rules under vector capacity and modifiers.

None of these containers automatically achieve thread safety simply because they resemble arrays. Concurrent read and write operations must adhere to the synchronization contracts specified by their respective APIs.

How to Diagnose Common Errors

Symptom	First Check
IndexError / IndexOutOfBoundsException	The effective read range is 0 ≤ i < size
Insertion causes element order to be incorrect	Are elements shifted from right to left so unread slots are not overwritten?
References remain to the end after deletion	Has the logical end slot been properly cleared to avoid unintentionally retaining objects?
Reading null values after reserving capacity	reserve/capacity does not increase the logical size
Modifying a 2D list's row results in multiple rows changing	Are you duplicating the same row object via multiplication?
C++ pointers suddenly become invalid	Did the operation trigger vector reallocation or suffix movement?

Hands-on Derive Move and Resize Operations

1. Add set(index, value) to the teaching version DynamicArray, and align the out-of-bounds rules with __getitem__.
2. Derive how many existing elements must be shifted and how many new elements must be written when inserting a contiguous block of m elements at index i in an array of length n.
3. Design a workload that justifies no automatic shrinking, and another that benefits from shrinking. Compare memory usage and copy counts between the two cases.
4. Benchmark row-and-column traversal using Python’s list-of-lists and a numerically contiguous array layout. First state the layout assumptions, then explain the observed results.

Verify Three Costs

Inserting an element at index i in a dynamic array of length n requires shifting n-i existing elements; deleting at the same index shifts n-i-1 elements. Test the implementation by expanding capacity from 2 to 4, then to 8, and record the number of elements copied in each case. Then use a full append sequence to explain why the amortized cost remains Θ(1).

Next, verify whether slicing returns a copy or a view, and construct a row-wise alias for a two-dimensional list. Fast index access stems from layout and cost modeling, while expensive in-place modifications arise from maintaining a consistent set of contiguous indices. Both costs follow from the same representation.

Continue Learning: Linked Lists

A linked list maintains order through references. The next lesson explains why "updating two links" is constant time only when the caller already holds the correct node or its predecessor.

Continue learning about linked lists