Dynamic Arrays (How Python Lists Work)

What this lesson is about

You have already used Python lists: [10, 20, 30]. A list is a sequence of values you can index into, add to, and remove from. This lesson explains what a list actually is underneath, so that when you write code you know which operations are cheap and which are expensive.

The underlying structure is called a dynamic array. “Array” is the name for a block of values laid out one after another in memory. “Dynamic” means it can grow as you add items. Python’s list is a dynamic array. So are ArrayList in Java, vector in C++, and List in C#. Understanding one teaches you all of them.

A quick vocabulary note before we start:

• Memory is the computer’s working storage, a long row of numbered slots. Each slot has an address, which is just its number (slot 0, slot 1, slot 2, and so on).
• Element or item: one value stored in the array.
• Index: the position of an element, counting from 0. In [10, 20, 30] the element 20 is at index 1.

Contiguous memory and why indexing is O(1)

The key idea is contiguous memory. “Contiguous” means the elements sit in memory back-to-back, with no gaps, in order. If an array of 4 elements starts at address 1000, then element 0 is at 1000, element 1 is at 1001, element 2 at 1002, element 3 at 1003 (using 1 slot per element to keep the picture simple).

Because the layout is regular, the computer can compute the address of any element with arithmetic:

address of element i  =  start_address + i * size_of_one_element

No searching is involved. To read index 500 the computer does one multiplication and one addition, then goes straight to that slot. It takes the same amount of work whether the array has 10 elements or 10 million.

Picture the list [10, 20, 30, 40] laid out in four back-to-back memory slots. Each cell knows its index and its address, and the addresses go up by one from the start:

graph LR
    S["start<br/>addr 1000"]
    A["index 0<br/>addr 1000<br/>value 10"]
    B["index 1<br/>addr 1001<br/>value 20"]
    C["index 2<br/>addr 1002<br/>value 30"]
    D["index 3<br/>addr 1003<br/>value 40"]
    S --> A --> B --> C --> D

To find index i, the computer does not walk this chain one node at a time; it jumps straight to 1000 + i in a single arithmetic step. The picture is a chain only so you can see the order and spacing.

We describe this with Big-O notation, a way of saying how the cost of an operation grows as the data gets larger. O(1) (“order 1”, also called constant time) means the cost does not depend on the size of the array. O(n) (“order n”, linear time) means the cost grows in proportion to the number of elements n. Indexing an array is O(1).

scores = [10, 20, 30, 40, 50]
print(scores[0])   # -> 10
print(scores[3])   # -> 40
print(scores[-1])  # -> 50  (Python lets you count from the end; -1 is the last item)

Every one of those reads is O(1). This constant-time random access is the whole reason arrays exist and the main reason to choose them.

Fixed-capacity arrays vs growable lists

In lower-level languages the most basic array has a fixed capacity. Capacity is how many elements the block of memory can hold. You decide the capacity up front, the computer reserves exactly that much contiguous memory, and it cannot change. If you make room for 5 elements and then need a 6th, the original block will not stretch, because the memory right after it may already be used by something else.

A Python list hides this problem. You never declare a capacity; you just append and it grows. It manages this with two separate numbers:

• length (also called size): how many elements you have actually stored.
• capacity: how many the currently reserved block could hold.

The capacity is usually larger than the length. Those extra reserved slots are empty space kept on purpose, so that the next few appends have somewhere to go without any extra work. When the length reaches the capacity and you append again, the list must grow: it reserves a bigger block, copies the existing elements over, and then adds the new one. We look at exactly how in the next section.

nums = []          # length 0, some small capacity reserved internally
nums.append(1)     # length 1
nums.append(2)     # length 2
print(nums)        # -> [1, 2]
print(len(nums))   # -> 2   (len gives the length, not the capacity)

Python does not expose the capacity directly, so you cannot print it. It exists, and it is what makes the following behavior possible.

How append is amortized O(1) via doubling

Adding one element to the end with append sounds like it should always be cheap, and most of the time it is O(1): there is a free reserved slot, you drop the value in, done.

The exception is when the array is full (length equals capacity). Then appending has to grow the array first:

1. Reserve a new, larger contiguous block.
2. Copy all n existing elements into it. This copy is O(n).
3. Release the old block.
4. Store the new element in the fresh space.

That one append is O(n), not O(1). So how can we call append cheap? The trick is how much bigger the new block is. A dynamic array does not grow by one slot each time; it multiplies the capacity, typically doubling it (Python grows by roughly 1.125x, but doubling is the classic example and the reasoning is the same). Growing by a factor means the expensive copies happen rarely, and rarely enough that the average cost per append stays constant.

That average-over-many-operations cost has a name: amortized cost. “Amortized O(1)” means that although a single append can occasionally be O(n), if you do many appends in a row the total work divided by the number of appends is a constant. Spreading the rare expensive operation across the many cheap ones gives O(1) each on average.

Here is the intuition for why doubling works. Suppose you append n elements starting from empty, doubling capacity each time it fills. The copy costs happen at sizes 1, 2, 4, 8, …, up to n. Add those up:

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

The total copying work is less than 2n, which is O(n) for all n appends together. Divide by n appends and you get a constant amount of copying per append. That is the whole argument.

data = []
for i in range(1000):
    data.append(i)      # amortized O(1) each; a few of these trigger an O(n) grow
print(len(data))        # -> 1000
print(data[999])        # -> 999

Space: the array uses O(n) memory. Because of the spare capacity it may reserve up to roughly twice the elements it currently holds, but “up to 2 times n” is still O(n) overall.

To make the doubling concrete, here is a step-by-step trace of appending five values a, b, c, d, e starting from an empty list, using the doubling model. “Full?” asks whether length equals capacity before this append; if so we grow first. The last three columns show the full state after the step finishes.

Read the “Elements copied” column: most appends copy nothing, and the copies that do happen (0, 1, 2, 4, …) sum to less than twice the final length. Step 4 was free because step 3 had already reserved room. That is the doubling argument in a table.

Watch the capacity double as elements are appended. In each box the reserved capacity is the whole box and the filled part is the current length:

flowchart TD
    A["capacity 1, length 1<br/>[a]"] -->|"append b: full, double"| B
    B["capacity 2, length 2<br/>[a][b]"] -->|"append c: full, double"| C
    C["capacity 4, length 3<br/>[a][b][c][ _ ]"] -->|"append d: free slot, cheap"| D
    D["capacity 4, length 4<br/>[a][b][c][d]"] -->|"append e: full, double"| E
    E["capacity 8, length 5<br/>[a][b][c][d][e][ _ ][ _ ][ _ ]"]

Notice that appending d in the middle was cheap because a reserved slot was already there. Only the steps that ran out of room paid the copy cost, and each of those roughly doubled the room for future appends.

Why insert and delete in the middle are O(n)

Contiguous memory is what makes indexing fast, but it is also what makes inserting or removing in the middle slow.

Suppose you have [10, 20, 30, 40] and you want to insert 99 at index 1, giving [10, 99, 20, 30, 40]. The elements must stay contiguous and in order, so 20, 30, and 40 each have to move one slot to the right to open a gap. Inserting near the front means shifting nearly every element. In the worst case (inserting at the front) you shift all n elements, so insertion is O(n).

xs = [10, 20, 30, 40]
xs.insert(1, 99)     # shift 20, 30, 40 right by one
print(xs)            # -> [10, 99, 20, 30, 40]

Before the insert, index 1 holds 20:

graph LR
    b0["index 0<br/>10"] --> b1["index 1<br/>20"] --> b2["index 2<br/>30"] --> b3["index 3<br/>40"]

After inserting 99 at index 1, the three elements 20, 30, 40 have each moved one slot to the right to open the gap, and the array is one longer:

graph LR
    a0["index 0<br/>10"] --> a1["index 1<br/>99 new"] --> a2["index 2<br/>20 moved"] --> a3["index 3<br/>30 moved"] --> a4["index 4<br/>40 moved"]

Deleting from the middle is the mirror image: to remove index 1 from [10, 99, 20, 30, 40], everything after the hole shifts one slot left to close the gap. That is O(n) as well.

ys = [10, 99, 20, 30, 40]
ys.pop(1)            # remove index 1, shift the rest left
print(ys)            # -> [10, 20, 30, 40]

Before the delete, index 1 holds 99:

graph LR
    d0["index 0<br/>10"] --> d1["index 1<br/>99 remove"] --> d2["index 2<br/>20"] --> d3["index 3<br/>30"] --> d4["index 4<br/>40"]

After removing index 1, everything past the hole slides one slot left to close the gap, and the array is one shorter:

graph LR
    e0["index 0<br/>10"] --> e1["index 1<br/>20 moved"] --> e2["index 2<br/>30 moved"] --> e3["index 3<br/>40 moved"]

The ends are special, and cheap:

zs = [1, 2, 3]
zs.append(4)   # add at the end, amortized O(1) (nothing to shift)
zs.pop()       # remove the last element, O(1) (nothing to shift)
print(zs)      # -> [1, 2, 3]

Contrast the pictures. Appending 4 to [1, 2, 3] writes into the free slot at the end and moves nothing:

graph LR
    p0["index 0<br/>1"] --> p1["index 1<br/>2"] --> p2["index 2<br/>3"] --> p3["index 3<br/>4 new"]

Popping the last element removes index 3 and, again, moves nothing:

graph LR
    q0["index 0<br/>1"] --> q1["index 1<br/>2"] --> q2["index 2<br/>3"]

Because no other element changes position, both end operations are O(1) (append amortized). Only middle and front operations pay the shifting cost.

Here is the summary you should memorize for dynamic arrays:

That last row is worth calling out: finding whether a value is present, or where it is, means scanning until you find it, because the array is not sorted or indexed by value. x in mylist is O(n).

When arrays are the right choice

Reach for a dynamic array (a Python list) when:

• You mostly read elements by index, or walk through them in order. Both are fast.
• You add and remove mostly at the end. append and pop() are cheap.
• You want the elements kept in a definite order and packed together, which also makes them memory-efficient and fast to iterate.

Prefer a different structure when:

• You insert or delete in the middle or front a lot. Every such change is O(n). A different structure called a linked list makes those O(1) once you are at the spot (at the cost of losing O(1) indexing).
• You look things up by a key or value rather than by position, and want it fast. A dictionary (hash table) gives average O(1) lookup by key, versus O(n) scanning a list.
• You repeatedly add and remove at the front. For a queue, Python’s collections.deque gives O(1) at both ends, while list.insert(0, x) and list.pop(0) are O(n).

Most of the time a list is the correct default. The point is to know its two weak spots (middle insertion/deletion, and search by value) so you can switch structures when those dominate your program.

Common pitfalls

Off-by-one errors. Indices run from 0 to len(xs) - 1. The length is not a valid index. Reaching for xs[len(xs)] is the single most common beginner mistake.

xs = [10, 20, 30]
print(len(xs))        # -> 3
print(xs[len(xs)-1])  # -> 30  (last valid index is length minus one)
# print(xs[3])        # IndexError: list index out of range

Growing or shrinking a list while iterating over it. When you loop for x in xs: and add or delete items inside the loop, the positions shift underneath you, so you skip elements or loop in ways you did not intend. Build a new list instead, or iterate over a copy.

xs = [1, 2, 3, 4]
# Wrong: removing while iterating skips elements.
# for x in xs:
# if x % 2 == 0:
# xs.remove(x)   # positions shift; 4 gets skipped -> [1, 3]... or worse

# Right: build a new list.
xs = [x for x in xs if x % 2 != 0]
print(xs)   # -> [1, 3]

Assuming insert(0, x) is cheap. Adding at the front shifts every element, so it is O(n). Building a list by repeatedly inserting at the front turns an O(n) job into O(n^2). Append at the end and reverse once if you need the other order, or use collections.deque.

Confusing length with capacity. len(xs) is how many elements you stored, not how much memory is reserved. You never manage capacity yourself in Python; do not try to.

Practice

1. Without running it, predict the output, then check: a = [5, 6, 7, 8]; a.insert(2, 99); a.pop(0); print(a). Then state, in words, how many elements had to shift for the insert and how many for the pop.

2. You are given a list and must remove every negative number from it. Write it two ways: one that builds a new list with a list comprehension, and one that mutates the original safely (hint: iterate over a copy, or loop by index from the back). Explain why iterating forward and calling remove inside the loop is buggy.

3. Explain in two or three sentences why appending 1,000,000 items to a list one at a time is O(n) total (not O(n^2)), even though a handful of those appends each cost O(n) on their own. Reference the doubling argument.