# Lists: Python's Dynamic Array — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/s-list

> Understand list internals and the cost of each operation.

## 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.

![A header box with length and capacity fields pointing to a row of slots, the first few filled with arrows to separate objects and the last few empty.](assets/figures/data-structures-python/section-2-map.svg) — Figure 2.1 — Length, capacity and references.

## Costs of common list operations

Fast at the end, slow at the front.

```python
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()`.

**Quiz:** What is the time complexity of list.insert(0, x) for a list of n items?

- [ ] O(1)
- [ ] O(log n)
- [x] O(n)
- [ ] O(n log n)

*Answer:* O(n). Every existing reference must shift one position to the right.