Lists: Python's Dynamic Array

A resizable array of references

A Python list is a dynamic array: a contiguous block of pointers to objects, plus a length and a capacity. Indexing (a[i]), assignment by index, len and appending are fast: O(1), with append amortised O(1) because CPython over-allocates spare capacity when it grows (roughly by an extra eighth plus a constant), so most appends need no copy. Operations at the front or middle are O(n) because elements must shift: insert(0, x), pop(0) and del a[i]. Searching (x in a, index, count, remove) is O(n). Slicing a[i:j] copies j - i references. sort uses Timsort, a stable O(n log n) algorithm that is very fast on partially sorted data, and sorted returns a new list. Lists are ideal for ordered collections that you append to and iterate over, and as stacks (append and pop from the end). Use a deque for queue behaviour, a set or dict for membership tests, and array or NumPy for large homogeneous numeric data.

Inside a list

A list object points to an array of references with spare capacity at the end.

Costs of common list operations

Fast at the end, slow at the front.

from timeit import timeit

# O(1) amortised: append and pop at the end
stack = []
for i in range(5):
    stack.append(i)
print(stack.pop())                     # 4

# O(n): insert or pop at the front shifts every element
setup = "a = list(range(100_000))"
print(timeit("a.append(1); a.pop()", setup=setup, number=10_000))
print(timeit("a.insert(0, 1); a.pop(0)", setup=setup, number=10_000))   # much slower

# slicing copies; sort is stable Timsort
scores = [("asha", 91), ("ravi", 78), ("meera", 91), ("kabir", 64)]
by_score = sorted(scores, key=lambda p: p[1], reverse=True)
print(by_score)   # asha before meera (stable): [('asha', 91), ('meera', 91), ('ravi', 78), ('kabir', 64)]

top_two = by_score[:2]                 # new list of 2 references
evens = [n for n in range(20) if n % 2 == 0]   # comprehension: fast and readable
print(evens[-3:])                      # [14, 16, 18]

Avoid pop(0) in loops

Processing a list with while items: x = items.pop(0) is O(n²) overall. Iterate with a for loop, reverse the list and pop from the end, or use collections.deque.popleft().

त्वरित जाँच: What is the time complexity of list.insert(0, x) for a list of n items?

• O(1)
• O(log n)
• O(n)
• O(n log n)