Arrays Explained: O(1) Indexing, O(n) Inserts, Dynamic Arrays

The array is the first data structure most people use and the one most interview answers quietly rely on. Its whole personality comes from one physical fact: the items sit back to back in a single block of memory. That makes reading any position instant and makes inserting in the middle slow, and almost every array technique, from two pointers to prefix sums, is a way to enjoy the first property without paying for the second.

The problem it solves

Programs constantly need "the item at position i": the 47th score, the pixel at row 3, the price on day 12. A structure that has to search for position i, like a linked list, pays for every lookup. An array computes the location instead: if the block starts at address base and each item takes size bytes, item i lives at base + i × size. One multiplication and one addition, whether the array holds ten items or ten million. That is what O(1) indexing means.

The price is rigidity. Because position is arithmetic, inserting a new item at the front means every existing item must move one slot to the right to keep the arithmetic true. And a block of memory has a fixed size, so growing beyond it means allocating a bigger block and copying everything across.

The intuition

Five operations, five costs:

• Read or write by index: O(1). Address arithmetic, no scanning.
• Length: O(1). The array stores it.
• Append at the end: O(1) amortised. Usually there is a free slot; occasionally the block is full and a dynamic array allocates a larger one, roughly double, and copies. Because the block grows geometrically, the copies add up to less than two per item over the array's life.
• Insert or delete in the middle: O(n). Every item after the position shifts by one. At the front, that is all of them.
• Search for a value: O(n) unless the array is sorted, in which case binary search makes it O(log n).

A Python list is a dynamic array of references: the block holds pointers, and the objects they point to live elsewhere. The array module and NumPy store raw values in the block instead, which is smaller and faster to scan. The costs above are the same either way.

Watch it run

The animation uses the lesson's prices = [12, 7, 30, 5]. An array stores values back to back, so slot i always sits at base + i × size. prices[2] lands straight on the slot: no scanning, one arithmetic step, which is O(1). prices[0] = 99 overwrites in place, and writing by index costs the same as reading, with zero shifts. append(8) drops in at the end, and nothing else has to move. Then insert(1, 42) has to push every later value one slot to the right: four shifts here, n shifts in general. The closing frame sums it up: indexing is free and rearranging is not, and that trade-off is what array problems are really about.

The code

First, address arithmetic done for real. ctypes gives a genuine C array of four 32-bit integers, and we read and write slot 2 by computing its address:

import ctypes
import random
import sys

prices = (ctypes.c_int32 * 4)(12, 7, 30, 5)     # a real C array: 4 ints back to back
base, size = ctypes.addressof(prices), ctypes.sizeof(ctypes.c_int32)
print(size, ctypes.sizeof(prices))               # 4 16
slot = ctypes.c_int32.from_address(base + 2 * size)   # base + i * size, i = 2
print(slot.value)                                # 30
slot.value = 31                                  # write through the computed address
print(list(prices))                              # [12, 7, 31, 5]

Four bytes per item, sixteen for the block, and the value at base + 2 × 4 is the third price; writing there changes the array. Now a toy model of a dynamic array: a fixed block that doubles when full, counting every element it moves:

class DynamicArray:
    """A fixed block that doubles when full. Counts every element moved."""
    def __init__(self):
        self.block, self.n, self.copies, self.shifts = [None], 0, 0, 0

    def _grow(self):
        bigger = [None] * (2 * len(self.block))
        for i in range(self.n):
            bigger[i] = self.block[i]
            self.copies += 1
        self.block = bigger

    def __getitem__(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)
        return self.block[i]                     # one step, whatever n is

    def append(self, x):
        if self.n == len(self.block):
            self._grow()
        self.block[self.n] = x
        self.n += 1

    def insert(self, i, x):
        if self.n == len(self.block):
            self._grow()
        for j in range(self.n, i, -1):           # shift the tail right, back to front
            self.block[j] = self.block[j - 1]
            self.shifts += 1
        self.block[i] = x
        self.n += 1

    def pop(self, i):
        x = self.block[i]
        for j in range(i, self.n - 1):           # close the gap
            self.block[j] = self.block[j + 1]
            self.shifts += 1
        self.n -= 1
        self.block[self.n] = None
        return x

a = DynamicArray()
for v in range(100_000):
    a.append(v)
print(a.copies, len(a.block), a.copies / a.n)    # 131071 131072 1.31071
b = DynamicArray()
for v in range(1000):
    b.insert(0, v)
print(b.shifts, b[0], b[999])                    # 499500 999 0

sizes = set()
lst = []
for v in range(10_000):
    lst.append(v)
    sizes.add(sys.getsizeof(lst))                # the real list's allocated size
print(len(sizes) < 100)                          # True

A hundred thousand appends moved 131,071 elements in total, 1.31 per append: the doublings cost 1 + 2 + 4 + ... + 65,536, which is less than twice the final size. A thousand inserts at the front shifted 499,500 elements, the quadratic 0 + 1 + ... + 999. CPython's own list resized only 47 times over 10,000 appends on the 3.9 interpreter used here; it over-allocates by roughly an eighth rather than doubling (from memory, as of October 2026), which is still geometric and still amortised O(1). Finally, 300 seeded runs of random appends, inserts and pops are compared with a Python list after every step, including the exact shift count of each insert:

ok = True
for seed in range(300):
    rng = random.Random(seed)
    arr, ref, pushes = DynamicArray(), [], 0
    for _ in range(rng.randint(0, 150)):
        op = rng.random()
        if op < 0.4:
            v = rng.randint(0, 99); arr.append(v); ref.append(v); pushes += 1
        elif op < 0.7:
            i, v = rng.randint(0, len(ref)), rng.randint(0, 99)
            before = arr.shifts
            arr.insert(i, v); ref.insert(i, v); pushes += 1
            ok &= arr.shifts - before == len(ref) - 1 - i
        elif ref:
            i = rng.randrange(len(ref))
            ok &= arr.pop(i) == ref.pop(i)
        ok &= [arr[i] for i in range(arr.n)] == ref
        ok &= arr.copies < 2 * max(pushes, 1)
print(ok)                                        # True

The complexity

• Index read or write, length: O(1).
• Append: O(1) amortised; a single append that triggers growth is O(n).
• Insert or delete at position i: O(n - i) shifts, so O(n) at the front.
• Space: O(n), plus spare capacity of up to a constant factor.

The Big-O cheat sheet has these next to linked lists and hash tables, and the Python cheat sheet lists the list methods with hidden O(n) costs.

Where it goes wrong

• Front inserts in a loop. insert(0, x) or pop(0) inside a loop is quietly quadratic, one of the hidden quadratics. Use a deque for queue-like access.
• Searching with in repeatedly. Each check is a scan; build a set once.
• Off-by-one indexing. Valid indexes are 0 to n - 1. Python's negative indexes count from the end, which hides some bugs instead of raising.
• Copying without noticing. A slice copies its elements; slicing inside a loop multiplies the work.

When it shows up in interviews

Constantly, usually without being named: two pointers, the sliding window, prefix sums and in-place tricks such as moving zeroes all exist to get answers from an array without paying for shifts. Expect to state the cost of each operation you use, especially append versus insert(0, ...).

How to say it in an interview

"An array stores elements contiguously, so element i is at the base address plus i times the element size: reading or writing by index is O(1). Inserting or deleting in the middle shifts everything after it, so that is O(n). A dynamic array like Python's list grows geometrically when full, copying into a bigger block, which makes append amortised O(1). So I index freely, append at the end, and avoid inserts and deletes at the front, reaching for a deque or a different structure when I need them."