Python calls list a mutable sequence. That is the right interface description and the wrong performance model. "Sequence" also describes tuples, ranges, strings, deques, and user-defined objects whose storage can be radically different.

For working code, the more predictive model is: a CPython list is a dynamic array of object references. Its elements have integer positions. Those positions map to adjacent pointer-sized cells. The array sometimes owns spare cells at the end so it can grow without allocating on every append.

That one model explains why indexing and appending are comfortable, why inserting at the front is expensive, why slices allocate, why membership still scans, and why a list of a million integers does not contain a million integers inline.

Version note. The language-level examples apply to Python 3.10 through 3.14 and were verified on CPython 3.14.7. Pointer arrays, allocation formulas, byte counts, and specialized implementation paths are CPython 3.14 details. Other implementations may preserve the same behavior with different storage.

A list stores references, not values

Assignment does not put a copy of an object into a list. It puts another reference to that object into one cell. Repetition repeats references too:

row = [0, 0]
grid = [row] * 3

grid[0][1] = 9

print(grid)
print(grid[0] is grid[1] is grid[2])

[[0, 9], [0, 9], [0, 9]]
True

The outer list has three cells, but every cell points to the same inner list. Use a comprehension when each position should receive a distinct object:

grid = [[0, 0] for _ in range(3)]
grid[0][1] = 9

print(grid)
print(grid[0] is grid[1])

[[0, 9], [0, 0], [0, 0]]
False

Python guarantee. List repetition is equivalent to adding the sequence to itself repeatedly; it does not recursively copy elements. list.copy(), list(existing), and a full slice are shallow copies for the same reason.

This is not merely a beginner's aliasing trap. It affects snapshots, work queues, default templates, and cache entries. If elements own mutable state, decide explicitly whether a new outer container, a shallow copy, or copy.deepcopy() matches the domain.

The CPython shape

At a simplified level, CPython's PyListObject has three relevant pieces:

list object                         separately allocated array
+-------------------+              +-----+-----+-----+-----+-----+
| logical length: 3 |              |  *  |  *  |  *  |     |     |
| allocated: 5      |------------->+--|--+--|--+--|--+-----+-----+
+-------------------+                 |     |     |
                                      v     v     v
                                    objects elsewhere on the heap

The logical length controls what Python code can access. The allocated capacity can be larger. Each occupied cell contains a PyObject *, not the object's payload. The objects can live anywhere, and multiple cells or containers can point to the same object.

This gives constant-time positional access: after normalizing a negative index and checking bounds, the implementation reads the pointer at the base address plus an offset. It does not walk through earlier elements as a linked list would.

Python guarantee versus complexity. Python specifies indexing behavior, including negative indexes and IndexError. The language reference does not require a contiguous pointer array or promise a particular Big-O bound. Constant-time list indexing is the dependable behavior of mainstream implementations and follows directly from CPython's representation, but the C layout is not a language contract.

Contiguous references improve locality when traversing the list's cells. They do not make the pointed-to Python objects contiguous. A list of boxed numbers is therefore not equivalent to a packed numeric array.

Spare capacity buys cheap append

If every append() resized an exact-fit allocation, building a list would repeatedly copy all existing pointers. CPython instead overallocates mildly. Most appends fill an already allocated cell; occasional appends grow the pointer array.

We can see the steps through the public, shallow sys.getsizeof() measurement:

import sys


items = []
previous = sys.getsizeof(items)
print(f"0 items -> {previous} bytes")

for value in range(40):
    items.append(value)
    current = sys.getsizeof(items)
    if current != previous:
        print(f"{len(items)} items -> {current} bytes")
        previous = current

On 64-bit CPython 3.14.7 in our test environment, the beginning was:

0 items -> 56 bytes
1 items -> 88 bytes
5 items -> 120 bytes
9 items -> 184 bytes
17 items -> 248 bytes
25 items -> 312 bytes
33 items -> 376 bytes

The size changes at selected lengths, not every length. CPython 3.14's list_resize() rounds capacity and grows by roughly one eighth plus a small constant, with adjustments for bulk growth and allocator alignment. The source documents an initial capacity pattern of 0, 4, 8, 16, 24, 32, 40, 52, ... for repeated one-at-a-time growth.

Do not encode that formula into application logic. It has changed before and can change again. The portable conclusion is only that repeated append is amortized constant time on CPython: a resize is occasionally linear, but its cost is spread over many cheap appends.

sys.getsizeof() counts the list's shallow storage, including its pointer array. It does not recursively count the objects referenced by those pointers. Memory totals that add every referent can also double-count shared objects.

Position determines movement

Dynamic arrays are asymmetric. Adding or removing at the right edge often changes only the length and one cell. Changing the left edge moves the references that follow.

CPython's insertion loop makes this literal: after ensuring capacity, it copies cells one position to the right from the end down to the insertion point. Deleting or popping from the middle moves the tail left. The number of shifted references depends on position.

This small timing experiment exposes the difference without claiming stable benchmark numbers:

from timeit import timeit


setup = "items = list(range(10_000))"

right = timeit("items.append(-1); items.pop()", setup=setup, number=20_000)
left = timeit("items.insert(0, -1); items.pop(0)", setup=setup, number=20_000)

print(left > right)
print(round(left / right, 1))

The first line printed True; the ratio is machine-dependent. The point is structural, not numerical. append() and pop() at the end avoid shifting the existing 10,000 references. insert(0, ...) and pop(0) shift approximately all of them each time.

Use collections.deque for a queue with frequent operations at both ends:

Pyodide / WebAssembly
from collections import deque


pending = deque(["compile", "test"])
pending.append("deploy")

while pending:
    print("[step] dequeued job:", pending.popleft())

Use a list as a stack with append() and pop(). A deque can index, but indexing in the middle is not its strength; changing structures swaps one access profile for another.

Indexing is direct; searching is not

Knowing an index and searching for a value are different operations. items[5000] jumps to one cell. target in items, items.index(target), items.count(target), and items.remove(target) compare elements in sequence.

We can instrument equality to watch membership stop at the first match:

Pyodide / WebAssembly
class Probe:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        print(f"[event] comparing stored {self.value} to target {other}")
        return self.value == other


items = [Probe(10), Probe(20), Probe(30)]
print("[check] list contains 20:", 20 in items)

compare 10 to 20
compare 20 to 20
True

Python guarantee. General sequence membership asks whether an item is equal to the target. Lists retain duplicates and order. No hashability is required.

That is precisely why lists remain useful for small collections and unhashable values. A set usually gives faster membership for a large collection, but it imposes hashability, uniqueness, and unordered semantics. Conversion is not free either. Building set(items) for one lookup can cost more than one scan; build and retain an index when repeated queries justify it.

Slices are new lists

A list slice copies references into a new list. It does not create a view into the original array:

Pyodide / WebAssembly
records = [{"id": 1}, {"id": 2}, {"id": 3}]
page = records[:2]

page.append({"id": 4})
page[0]["status"] = "seen"

print("[state] records and page lengths:", len(records), len(page))
print("[state] shared first record after mutation:", records[0])

3 3
{'id': 1, 'status': 'seen'}

The outer arrays are independent, so appending to page does not affect records. Their first cells still refer to the same dictionary, so mutating that dictionary is visible through both.

A slice of length k needs time and shallow storage proportional to k. Repeatedly trimming work with items = items[1:] copies the entire remaining tail and can turn a linear process into a quadratic one. Prefer an index, an iterator, or a deque depending on whether you need random access, one-pass consumption, or destructive queue semantics.

Slice assignment is different: items[a:b] = iterable mutates the existing list object. It can grow or shrink the array and shift the tail. Extended slice assignment such as items[::2] = values requires exactly as many replacement values as selected positions.

Pyodide / WebAssembly
items = [0, 1, 2, 3, 4, 5]
items[1:4] = [10, 11]
print("[state] after contiguous slice assignment:", items)

items[::2] = [20, 21, 22]
print("[state] after extended slice assignment:", items)

[0, 10, 11, 4, 5]
[20, 10, 21, 4, 22]

Mutation while iterating follows indexes

List iterators do not snapshot values and do not generally raise an error when the list changes size. The Python documentation describes forward and reversed mutable-sequence iterators as advancing an index against the live sequence.

That can skip values:

Pyodide / WebAssembly
numbers = [1, 2, 3, 4, 5, 6]

for number in numbers:
    if number % 2:
        numbers.remove(number)

print("[state] numbers after removing odd values:", numbers)

[2, 4, 6]

This particular input happens to produce the intended result: after removing an odd value, the following even value slides into the index the iterator has already passed. Change the predicate or adjacent values and elements can be missed unexpectedly.

Pyodide / WebAssembly
numbers = [1, 3, 5, 8]

for number in numbers:
    if number < 8:
        numbers.remove(number)

print("[state] numbers after mutation during iteration:", numbers)
# [3, 8]

Iterate over a copy when mutations are genuinely required, or more commonly construct the desired result:

Pyodide / WebAssembly
numbers = [1, 3, 5, 8]
numbers = [number for number in numbers if number >= 8]
print("[result] filtered numbers:", numbers)

Do not import dictionary and set intuition here. Those iterators detect many size changes and raise RuntimeError; list iteration has different documented mechanics.

Sorting exposes list semantics too

list.sort() rearranges references in place and returns None; sorted(iterable) builds a new list. Python guarantees stability: records with equal keys preserve their original relative order.

Pyodide / WebAssembly
events = [
    ("build", 2),
    ("lint", 1),
    ("test", 2),
    ("format", 1),
]

events.sort(key=lambda event: event[1])
print("[result] events sorted stably by priority:", events)

[('lint', 1), ('format', 1), ('build', 2), ('test', 2)]

Stability is a Python guarantee, not just a fortunate CPython property. CPython 3.14 uses an adaptive stable natural mergesort implementation documented in listsort.txt; the precise algorithm and its tuning are implementation details.

The key function runs once per item for a normal successful sort, and comparisons are then performed on saved keys. Prefer key= over comparison adapters when possible. Also remember that an exception during comparison can leave the list partially modified, as the official documentation warns.

Choosing the representation

A list is the practical default when you need an ordered, mutable collection and its dominant operations align with a dynamic array:

  • choose a list for positional access, iteration, append-heavy building, stack operations, sorting, and small linear searches;
  • choose a tuple for a fixed sequence whose immutability is meaningful;
  • choose a deque for frequent additions and removals at both ends;
  • choose a set for repeated membership and uniqueness when elements are hashable and order is not the contract;
  • choose a dictionary when identity maps to associated data;
  • choose array.array, a numeric library, or another packed representation when millions of homogeneous values must be stored or processed densely;
  • keep a separate index when you need both ordered records and repeated lookup by key.

Do not replace every pop(0) on sight. For a five-element list outside a hot path, clarity can dominate asymptotics. Conversely, a queue that may hold hundreds of thousands of jobs has a structural mismatch worth fixing before micro-optimizing syntax.

The same restraint applies to preallocation. Python exposes no general list.reserve() method. [None] * n creates a list of logical length n, not an empty list with hidden capacity. Filling known positions can be appropriate, but manufacturing placeholders solely to imitate a lower-level API usually complicates code and retains real references.

Exercises: test the model

  1. Predict which objects are shared after outer = [template.copy()] * 4. Modify an inner mutable value and then replace one outer cell. Explain both outcomes.
  2. Repeat the getsizeof() growth experiment with extend(range(20)) instead of twenty appends. Which observations are portable, and which only describe that CPython build?
  3. Time pop() at indexes -1, len(items) // 2, and 0 for several list sizes. Relate the trend to the number of shifted references rather than to one timing ratio.
  4. Rewrite a loop that repeatedly performs items = items[1:] using an iterator, an index, and a deque. State what semantics each version changes.
  5. Sort records first by a secondary key and then by a primary key. Use stability to explain the final order.

Keep this model

A CPython list is an ordered, resizable array of references. The pointer array makes index access and traversal natural. Spare capacity makes repeated append cheap on average. The same layout makes front and middle changes pay for movement, and it cannot turn equality-based membership into indexed lookup.

The interface and representation should remain separate in your reasoning. Python guarantees mutable-sequence behavior, shallow repetition, stable sorting, and live index-based mutable-sequence iteration. CPython 3.14 supplies the current pointer layout, growth formula, and concrete memory sizes.

When list performance surprises you, ask:

  1. Am I reading a known position or searching by value?
  2. How many references must this operation allocate, copy, or shift?
  3. Do I need a sequence at all, or does another access pattern dominate?

Those questions turn "lists are fast" into a useful engineering model.

Primary sources