List

In computer science "list" often means linked list. A Python list is not one. It's a dynamic array (what other languages call a vector or array list). That single fact decides which operations are fast, which are slow, and how you should answer performance questions in an interview.

How a list is laid out#

A PyListObject has three fields that matter:

Each slot holds a pointer (8 bytes on 64-bit) to an object stored elsewhere. That's why one list can hold [10, "a", True]: the array itself is just a row of same-sized addresses.

Why append is amortised O(1)#

When you call append(x):

• There's a spare slot (ob_size < allocated): write the pointer there. $O(1)$.
• The array is full: allocate a bigger array, copy the pointers over, then write. $O(n)$ for this one call.

CPython over-allocates by roughly 1/8 of the current size plus a small constant, so resizes get rarer as the list grows. Averaged over many appends, each one costs $O(1)$ (amortised).

You can watch it happen. The slot count stays flat, then jumps:

import sys

nums = []
base = sys.getsizeof(nums)
last = None
for i in range(40):
    nums.append(i)
    slots = (sys.getsizeof(nums) - base) // 8
    if slots != last:
        print(f"len={len(nums):>2}  slots={slots}")
        last = slots

On CPython 3.12 this prints growth points like:

The exact numbers are an implementation detail and change between versions. The shape (flat, then a jump) is what matters.

What operations cost#

Because a list is a contiguous array, the cost of each operation depends on how many slots it touches.

Need fast pops from the front (a BFS queue)? Use collections.deque, where popleft() is $O(1)$.

Mutation: same object, new contents#

Lists are mutable. a[1] = "hello" swaps one pointer in the slot array. The list object keeps its address.

nums = [1, 2, 3]
before = id(nums)
nums[0] = 99
nums.append(4)
print(id(nums) == before)   # True: same list, changed in place

a = a + [x] vs a += [x]#

a = [1]
alias = a
a = a + [2]       # builds a NEW list; alias still sees [1]
print(alias)      # [1]

a = [1]
alias = a
a += [2]          # calls extend(): mutates the SAME list
print(alias)      # [1, 2]

Mutable default arguments#

A default value is evaluated once, when the function is defined, so every call shares the same list:

def add_bad(item, box=[]):
    box.append(item)
    return box

print(add_bad("A"))   # ['A']
print(add_bad("B"))   # ['A', 'B']  <- the same list again

def add_good(item, box=None):
    if box is None:
        box = []          # fresh list per call
    box.append(item)
    return box

Copies: shallow vs deep#

b = a[:] (or a.copy(), list(a)) creates a new list object whose slots point at the same items. Changing the structure of a doesn't affect b, but changing a mutable item inside does.

import copy

a = [[1, 2], [3, 4]]
b = a[:]
a.append([5])          # structure change: b unaffected
a[0].append(99)        # inner object change: b sees it
print(b)               # [[1, 2, 99], [3, 4]]

c = copy.deepcopy(a)   # copies inner lists too
a[1].append(0)
print(c[1])            # [3, 4]

The same trap in grid setup:

bad = [[0] * 3] * 3            # 3 references to ONE row
bad[0][0] = 1
print(bad)                     # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

grid = [[0] * 3 for _ in range(3)]   # 3 independent rows

Mutation in backtracking#

Backtracking code usually shares one path list and mutates it. That's fast, but you must undo each change and copy when you save a result.

def subsets(nums):
    res, path = [], []

    def dfs(i):
        if i == len(nums):
            # copy: path keeps changing after this
            res.append(path[:])
            return
        path.append(nums[i])      # choose
        dfs(i + 1)
        # undo, so the caller sees path unchanged
        path.pop()
        dfs(i + 1)                # skip

    dfs(0)
    return res

print(subsets([1, 2]))   # [[1, 2], [1], [2], []]

Appending path instead of path[:] is the classic bug: every saved result is the same list, which ends up empty.

Key takeaways#

• A list is a contiguous array of pointers, so indexing is $O(1)$ and items can be any type.
• Over-allocation makes append amortised $O(1)$; inserting or popping at the front is $O(n)$.
• a += b mutates in place; a = a + b builds a new list.
• a[:] is a shallow copy; use copy.deepcopy for nested data and a comprehension for grids.
• In backtracking, undo every mutation and save path[:], not path.