List Memory Growth, Slicing and Complexity

18 min · Intermediate

A Python list is not a linked list; it is a dynamically resized contiguous array of pointers in C (PyListObject). Understanding its internal memory architecture explains why .append() is blazingly fast while .insert(0, val) degrades performance.

Contiguous Pointer Array Architecture

Dynamic array is a block of memory that holds items side by side. When it fills up, it is replaced by a bigger block and the items are copied across.

In CPython, a list stores an array of memory pointers pointing to objects scattered across the heap.

Python

import sysitems = []print("Empty list bytes:", sys.getsizeof(items))

Example 1 · A list stores references

Python

row = [0, 0]grid = [row, row]grid[0][0] = 5print(grid)print(grid[0] is grid[1])

Output

[[5, 0], [5, 0]]
True

What this code does

grid holds two pointers to the same row list, not two copies.
Changing one row changes the other because both names reach the same object.

The base overhead of an empty list is 56 bytes on 64-bit systems, storing the object header, size, and capacity pointers.

The Over-Allocation Growth Formula

Amortized O(1) means a cost that is occasionally high but averages out to constant time per operation over many operations.

To avoid copying on every .append(), CPython keeps spare slots. When the list grows to a new length, the new capacity is about (new_len + (new_len >> 3) + 6) & ~3.

Python

import sysl = []for i in range(9):    print(f"Len: {len(l)} | Allocated Bytes: {sys.getsizeof(l)}")    l.append(i)

Example 2 · Counting reallocations

Python

1import sys2
3def track_allocations(n):4    lst = []5    prev_size = sys.getsizeof(lst)6    reallocs = 07    for i in range(n):8        lst.append(i)9        cur_size = sys.getsizeof(lst)10        if cur_size != prev_size:11            reallocs += 112            prev_size = cur_size13    return reallocs14
15print("Reallocations for 20 appends:", track_allocations(20))

Sample output

Reallocations for 20 appends: 4

What this code does

Appending 20 items only required 4 memory reallocations.
Over-allocation reduces expensive heap realloc operations significantly.

The byte count rises in steps (here at lengths 1, 5 and 9), not on every append. The exact numbers depend on the Python version. This stair-step growth is what makes append amortized O(1).

Time Complexities: Append vs Insert/Pop(0)

Time complexity describes how the work of an operation grows as the number of items N grows, written as O(1), O(N) and so on.

Adding at the end touches one slot. Adding at the front moves every item. These are the costs, where N is the number of items.

list.append(x): Amortized O(1) because spare capacity accommodates most appends without reallocation.
list.pop(): O(1) because removing the tail requires zero element shifts.
list.insert(0, x): O(N) because every single existing pointer in the array must shift right by one index in memory.
list.pop(0): O(N) because all remaining pointers must shift left.

Advanced Slicing and Shallow Copying

Shallow copy is a new container that holds the same item objects as the original, so nested lists are shared, not duplicated.

Slicing l[start:stop:step] always builds a NEW list that holds the same references (a shallow copy).

Python

1data = [10, 20, 30, 40, 50]2print(data[1:4])     # [20, 30, 40]3print(data[::-1])    # [50, 40, 30, 20, 10] (Reversed)4
5# Slice assignment (in-place replacement)6data[1:3] = [99, 98, 97]7print(data)

Example 3 · A shallow copy shares inner lists

Python

1orders = [["A1", 2], ["B7", 1]]2copy_of = orders[:]3copy_of[0][1] = 994copy_of.append(["C3", 4])5print(orders)6print(copy_of)

Output

[['A1', 99], ['B7', 1]]
[['A1', 99], ['B7', 1], ['C3', 4]]

What this code does

append changed only copy_of, because the outer lists are separate.
The inner list ["A1", 99] is shared, so both lists show 99.

Slice assignment mutates the list in place, expanding or contracting the array as needed.

Queues: use a deque, not a list

Deque is a double-ended queue from the collections module. It adds and removes at both ends in O(1).

A list is slow at the front. When orders must leave in the order they arrived, collections.deque removes the first item in O(1).

Python

1from collections import deque2
3queue = deque(["order-1", "order-2", "order-3"])4queue.append("order-4")5first = queue.popleft()6print(first, list(queue))

Example 4 · Serving tickets with a deque

Python

1from collections import deque2
3tickets = deque()4for number in range(1, 5):5    tickets.append(f"T-{number}")6
7served = []8while tickets:9    served.append(tickets.popleft())10print(served)

Output

['T-1', 'T-2', 'T-3', 'T-4']

What this code does

Tickets leave in the order they arrived (first in, first out).
Each popleft() is O(1); list.pop(0) would shift every remaining item.

popleft() and append() both run in O(1). A deque gives up fast indexing in the middle, so pick it only for queue-like work.

Next step

Check your understanding

10 quick questions

1import sys2 3def track_allocations(n):4 lst = []5 prev_size = sys.getsizeof(lst)6 reallocs = 07 for i in range(n):8 lst.append(i)9 cur_size = sys.getsizeof(lst)10 if cur_size != prev_size:11 reallocs += 112 prev_size = cur_size13 return reallocs14 15print("Reallocations for 20 appends:", track_allocations(20))

1data = [10, 20, 30, 40, 50]2print(data[1:4]) # [20, 30, 40]3print(data[::-1]) # [50, 40, 30, 20, 10] (Reversed)4 5# Slice assignment (in-place replacement)6data[1:3] = [99, 98, 97]7print(data)