To understand the performance characteristics of Python lists, one must delve into their internal implementation in CPython, the reference interpreter. A Python list is not a simple array but a sophisticated, dynamically-sized data structure built for efficiency. Its core is a C array of pointers to Python objects (a PyObject **). This design choice is fundamental, as it allows the list to store references to any type of object while maintaining the contiguous memory layout necessary for fast indexing.

Over-Allocation: The Engine of Amortized O(1) Appends

The most critical performance optimization in the list implementation is over-allocation. When a list is created or extended, CPython does not allocate memory for just the requested number of elements. Instead, it allocates more memory than is immediately needed. This extra, unused space is called over-allocation.

The logic for this is governed by a growth pattern. When a list is created, the underlying C array (ob_item) is allocated with a certain capacity. The number of elements currently in the list is its length (ob_size). When an element is appended using list.append() and the current capacity is full, the list must be resized. Resizing is an expensive operation (O(n)) because it requires allocating a new, larger memory block and copying all existing elements from the old block to the new one.

To avoid performing this copy on every single append, CPython uses a growth strategy. The formula for the new capacity is roughly new_allocated = (new_size >> 3) + (new_size < 9 ? 3 : 6). In simpler terms, the capacity grows by approximately 12.5% each time resizing is required. This geometric growth ensures that as the list gets larger, the number of resizes required becomes increasingly rare.

This strategy leads to amortized constant time (O(1)) for appending elements. While an individual append that triggers a resize is expensive, the cost of that resize is “amortized” or spread out over the many cheap appends that follow which only require storing a pointer in the pre-allocated space. You can observe this behavior by examining a list’s __sizeof__() method, which returns the memory consumption of the list itself (not its elements). The growth becomes visible when the list length crosses certain thresholds.

import sys

lst = []
previous_size = sys.getsizeof(lst)
for i in range(100):
    lst.append(i)
    current_size = sys.getsizeof(lst)
    if current_size != previous_size:
        print(f"Length: {len(lst):2d} | Size in bytes: {current_size:4d} | Growth")
        previous_size = current_size

Expected Output:

Length:  0 | Size in bytes:   56 | Growth
Length:  1 | Size in bytes:   88 | Growth
Length:  5 | Size in bytes:  120 | Growth
Length:  9 | Size in bytes:  184 | Growth
Length: 11 | Size in bytes:  184 | 
Length: 17 | Size in bytes:  256 | Growth
Length: 26 | Size in bytes:  336 | Growth
Length: 37 | Size in bytes:  440 | Growth
Length: 51 | Size in bytes:  568 | Growth
Length: 68 | Size in bytes:  712 | Growth
Length: 91 | Size in bytes:  920 | Growth

Notice how the size (capacity) only increases sporadically, not on every append.

Time Complexity of Common Operations

The over-allocation strategy directly informs the time complexity of list operations:

  • Indexing (lst[i]) and assignment (lst[i] = x): O(1). These operations are a simple pointer lookup or store in the contiguous underlying array.
  • Appending (lst.append(x)): Amortized O(1). As explained, most appends are a simple store, with the occasional expensive resize.
  • Popping from the end (lst.pop()): O(1). This only requires decreasing the size counter; the memory is not usually freed immediately (though it may be reallocated if a much smaller list is created).
  • Popping from an arbitrary index (lst.pop(i)): O(n). This operation requires shifting all elements after index i one position to the left to fill the gap. The cost is proportional to the number of elements that need to be shifted.
  • Inserting at an arbitrary index (lst.insert(i, x)): O(n). Similarly, this requires shifting all elements from index i onward one position to the right to make space. This may also trigger a resize.
  • Deletion by index (del lst[i]) or by value (lst.remove(x)): O(n). Both involve finding the element (the latter by scanning the list) and then shifting elements to close the gap.
  • Containment check (x in lst): O(n). This requires a linear scan of the list until the value is found.
  • Slicing (lst[a:b]): O(k). The complexity is proportional to the number of elements k in the slice, as a new list must be created and all elements copied into it.

Pitfalls and Best Practices

  1. Prefer .append() for Building Lists: Due to amortized O(1), building a list by repeated appending is efficient. Avoid using insert(0, x) to build a list, as it requires shifting the entire list each time, resulting in O(n²) performance. If you need to prepend frequently, consider using collections.deque, which is optimized for appends and pops from both ends.

  2. List Comprehensions Over Loops: List comprehensions are not just syntactic sugar; they are highly optimized. They often execute faster than a equivalent for loop with .append() because they can pre-allocate the list with the correct final size in a single operation, minimizing the number of resizes.

# Slower
result = []
for i in range(1000):
    result.append(i * 2)

# Faster - CPython can often optimize the allocation
result = [i * 2 for i in range(1000)]

  1. Beware of Mid-List Mutations: Be acutely aware of the O(n) cost of insert, pop(i), remove, and del for non-end indices. Performing these operations inside a loop can quickly lead to quadratic performance. If you must frequently remove elements from the middle of a large list, consider alternative data structures like a linked list (though they have their own trade-offs) or use a filter operation to create a new list.

  2. Understanding a += b vs. a = a + b: The += operator for lists is implemented as list.__iadd__(), which extends the list a in-place. This is efficient, especially if a has enough over-allocated space. The statement a = a + b creates a brand new list and reassigns the variable a to it. This is less efficient as it requires copying all elements from both a and b.

# Efficient: in-place extension
list_a = [1, 2, 3]
list_b = [4, 5, 6]
list_a += list_b  # Uses .extend() internally

# Less efficient: creates a new list
list_a = [1, 2, 3]
list_b = [4, 5, 6]
list_a = list_a + list_b  # Allocates and copies into a new list