Lists & Tuples¶

Estimated time: 22 min read · Part: Data Structures That Carry Real Work

A list is an ordered, mutable sequence backed by a dynamic array of object pointers. A tuple is an ordered, immutable sequence. On the surface they look nearly identical; under the hood they serve fundamentally different purposes, and the gap between knowing their API and understanding their internals is the difference between writing code that works and writing code that scales.

In production data pipelines, knowing that list membership is O(n) — and reaching for a set instead — has eliminated hours-long nightly ETL jobs. Knowing that tuples are hashable has unlocked efficient dict-keying of composite records. These are not theoretical concerns; they are daily engineering decisions that separate junior from senior code.

Under the Hood: CPython's Dynamic Array¶

A Python list is not a linked list. It is a contiguous block of object pointers — on a 64-bit system, each pointer is 8 bytes, and they sit side by side in memory. This is why index access is O(1): to find element i, Python computes base_address + i × 8 in one arithmetic step, then follows the pointer to the actual object on the heap.

When you append(), Python checks whether spare capacity exists. If so, it writes the new pointer into the next slot — O(1). If the array is full, Python allocates a larger block (roughly 1.125× the current allocation), copies all pointers, then adds the new element. This copy is O(n), but because capacity grows geometrically, copies happen exponentially less often as the list grows. The amortized cost per append is O(1): you pay a big cost occasionally, and that cost averages out over many cheap appends.

import sys

lst = []
last_size = 0
for i in range(16):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != last_size:
        print(f"len={len(lst):2d}  allocated capacity changed  bytes={size}")
        last_size = size

len= 1 allocated capacity changed bytes=88 len= 5 allocated capacity changed bytes=120 len= 9 allocated capacity changed bytes=184 len=17 allocated capacity changed bytes=248

CPython List Internal Layout
─────────────────────────────────────────────────────────
  PyListObject header
  ┌──────────┬──────────┬───────────┬──────────────────┐
  │ refcount │  type*   │ ob_size   │  allocated       │
  │  (int)   │ (list)   │ (used=4)  │  (capacity=8)    │
  └──────────┴──────────┴──────────┬┴──────────────────┘
                                   │ ob_item ──────────────────────────────┐
                                   └───────────────────────────────────────↓
  Contiguous pointer block (8 bytes × allocated)
  ┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
  │  ptr0  │  ptr1  │  ptr2  │  ptr3  │  ---   │  ---   │  ---   │  ---   │
  └───┬────┴───┬────┴───┬────┴───┬────┴────────┴────────┴────────┴────────┘
      ↓        ↓        ↓        ↓      (4 spare slots pre-allocated)
   obj0     obj1     obj2     obj3      (objects live elsewhere on heap)

Index access:  ptr = ob_item[i]         → O(1) arithmetic + deref
Append (room): ob_item[ob_size] = ptr   → O(1) single write
Insert front:  shift ob_item[0..n-1]    → O(n) moves every pointer

Core Operations and Their Complexity¶

The pointer-array architecture directly explains every complexity result. Once you know the layout, none of these are facts to memorize — they are consequences of one design decision.

nums = [3, 1, 4, 1, 5, 9, 2, 6]

# ── O(1) ─────────────────────────────────────────────
nums[3]             # 1        — pointer math: base + 3*8
nums[-1]            # 6        — len-1 then pointer math
nums.append(7)      # extend at end, amortized O(1)
nums.pop()          # 7        — shrink at end, O(1)
len(nums)           # 8        — stored as a field, not counted

# ── O(k) — proportional to slice length ──────────────
nums[2:5]           # [4, 1, 5]  — copies 3 pointers into new list
nums[::-1]          # reversed  — copies all n pointers

# ── O(n) — touch every element ───────────────────────
nums.insert(0, 99)  # shifts EVERY element right by one
nums.pop(0)         # shifts EVERY element left by one
3 in nums           # linear scan — compare one by one
nums.index(5)       # linear scan for first match
nums.count(1)       # linear scan counting matches
nums.reverse()      # in-place reversal

# ── O(n log n) ────────────────────────────────────────
nums.sort()                    # in-place Timsort (stable)
sorted(nums)                   # returns new sorted list
nums.sort(key=lambda x: -x)    # sort with key function

# BUG: the default [] is created once and reused
def add_tag(tag, tags=[]):     # WRONG — shared across calls
    tags.append(tag)
    return tags

add_tag("python")    # ["python"]
add_tag("data")      # ["python", "data"]  — unexpected!
add_tag("api")       # ["python", "data", "api"]

# CORRECT: None sentinel, fresh list each call
def add_tag(tag, tags=None):
    if tags is None:
        tags = []
    tags.append(tag)
    return tags

add_tag("python")    # ["python"]
add_tag("data")      # ["data"]  — independent, correct

Tuples: Semantic Immutability and Hashability¶

A tuple is not a "frozen list." It carries a distinct semantic meaning: a fixed record whose structure is part of the interface. A 2-tuple (lat, lon) communicates that two floats always travel together and their position matters. A 3-tuple (status_code, body, headers) is a complete response record. When a function return a, b produces a tuple, it signals: "this is one result in two parts."

Immutability brings concrete benefits. Tuples are hashable (if all their elements are hashable), so they work as dict keys and set members. They are slightly smaller than equivalent lists — no over-allocation headroom. CPython interns and caches small tuples, making their creation faster. And they protect data that must not change from accidental mutation — an invariant you can express in the type itself.

import sys

# Tuples as typed records
coord   = (51.5074, -0.1278)         # (lat, lon) — structured record
rgb     = (255, 128, 0)              # immutable colour
db_row  = ("ada@x.io", "engineer", 36)

# Hashable: tuples can be dict keys and set members
visit_counts = {}
visit_counts[(51.5074, -0.1278)] = 42   # coordinates as key
visit_counts[(40.7128, -74.0060)] = 18

# Try the same with a list — TypeError
try:
    d = {[1, 2]: "value"}
except TypeError as e:
    print(e)    # unhashable type: 'list'

# Memory: tuples are smaller (no over-allocation)
lst = [1, 2, 3, 4, 5]
tup = (1, 2, 3, 4, 5)
print(sys.getsizeof(lst))   # 104 bytes  (capacity headroom)
print(sys.getsizeof(tup))   #  80 bytes  (exact fit)

# Extended unpacking — the most powerful unpack form
first, *middle, last = (10, 20, 30, 40, 50)
# first=10  middle=[20, 30, 40]  last=50

# Discard with _ by convention
_, important, _ = ("ignore", "keep_this", "ignore")

# Pythonic swap — no temp variable needed
x, y = 5, 10
x, y = y, x          # x=10, y=5  (uses tuple packing/unpacking)

# Function returning multiple values is always a tuple
def divmod_custom(a, b):
    return a // b, a % b   # packs into a tuple

quotient, remainder = divmod_custom(17, 5)
# quotient=3  remainder=2

unhashable type: 'list' 104 (list bytes) 80 (tuple bytes)

Slicing, Comprehensions, and Generator Expressions¶

Python's slice syntax [start:stop:step] works on any sequence type (list, tuple, string, bytes). Any component can be omitted: [:5] means "first 5", [::2] means "every other", [::-1] reverses. Slicing creates a new object containing copies of the selected pointers — it is O(k) where k is the slice length, not O(1).

List comprehensions are the idiomatic way to build a list from an iterable: [expr for item in iterable if condition]. They are more readable than a loop-with-append and faster (CPython optimizes the bytecode path). Replace the brackets with parentheses to get a generator expression — lazy, single-pass, using almost no memory — ideal when you immediately feed the result to sum(), max(), any(), or another aggregator.

data = [10, 20, 30, 40, 50, 60, 70, 80, 90]

# Slicing
data[2:5]      # [30, 40, 50]   — indices 2, 3, 4
data[:4]       # [10, 20, 30, 40]  — first 4
data[-3:]      # [70, 80, 90]   — last 3
data[1::2]     # [20, 40, 60, 80]  — every other starting at 1
data[::-1]     # [90, 80, ... 10]  — full reversal (new list)

# Slice assignment — in-place replacement, works even with different length
data[1:3] = [200, 300, 350]    # replace 2 elements with 3

# List comprehension vs manual loop — identical output, comp preferred
squares_loop = []
for n in range(10):
    squares_loop.append(n ** 2)

squares_comp = [n ** 2 for n in range(10)]
# [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# Filtered comprehension — real-world: parse valid prices from messy data
raw = ["19.99", "N/A", "5.00", "", "12.49", "SOLD"]
prices = [float(p) for p in raw if p.replace(".", "", 1).isdigit()]
# [19.99, 5.0, 12.49]

# Generator expression — no intermediate list, lazy evaluation
# Use when you pipe directly into sum/max/any/all/join
total = sum(p * 1.2 for p in prices)          # sum without a list
has_expensive = any(p > 15 for p in prices)   # short-circuits at first True

# Memory comparison: comprehension vs generator for 10M items
import sys
comp_mem = sys.getsizeof([x for x in range(100)])    # ~904 bytes for 100 items
gen_mem  = sys.getsizeof(x for x in range(100))      # ~208 bytes regardless of size
print(f"list: {comp_mem}  generator: {gen_mem}")

[19.99, 5.0, 12.49] list: 904 generator: 208

When to Reach for collections.deque¶

A deque (double-ended queue) solves the O(n) front-insertion problem. It is implemented as a doubly-linked chain of fixed-size blocks, giving O(1) at both ends. The trade-off: random index access is O(n) (no direct pointer math). Use it when your access pattern is predominantly at the ends: queues, BFS frontiers, sliding windows, and any producer-consumer pipeline.

from collections import deque

# BFS graph traversal — deque is the canonical frontier
def bfs(graph, start):
    visited  = {start}
    frontier = deque([start])    # O(1) popleft — critical for BFS
    order    = []
    while frontier:
        node = frontier.popleft()
        order.append(node)
        for nbr in graph.get(node, []):
            if nbr not in visited:
                visited.add(nbr)
                frontier.append(nbr)
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
bfs(graph, "A")   # ['A', 'B', 'C', 'D', 'E']

# Fixed-size sliding window — maxlen auto-evicts oldest
def moving_average(values, n):
    window = deque(maxlen=n)
    result = []
    for v in values:
        window.append(v)
        if len(window) == n:
            result.append(sum(window) / n)
    return result

moving_average([1, 3, 5, 7, 9, 11], n=3)
# [3.0, 5.0, 7.0, 9.0]  — each is avg of last 3 values

# Task queue (producer-consumer)
tasks = deque()
tasks.append("send_email")        # producer adds to right
tasks.append("process_payment")
tasks.popleft()   # "send_email"  — consumer takes from left, O(1)

['A', 'B', 'C', 'D', 'E'] [3.0, 5.0, 7.0, 9.0] | Feature | list | deque | |---|---|---| | Append right | O(1) amortized | O(1) | | Pop right | O(1) | O(1) | | Append left / prepend | O(n) | O(1) | | Pop left | O(n) | O(1) | | Index access [i] | O(1) | O(n) | | Memory layout | Contiguous array | Linked 64-item blocks | | Fixed-size window | Manual slicing | maxlen= parameter | | Best for | Random access, growing one end | Queues, BFS, sliding windows |

WHY Why is the list the default sequence? Python's philosophy is "one obvious way." A list handles the overwhelming majority of sequence use cases — ordered, mutable, growable — with excellent average performance. Specialized tools (deque, array, NumPy) exist for specific needs. Making list the default means you never have to think "which sequential container?" for ordinary work; that cognitive budget is preserved for things that matter.

HOW How does amortized O(1) work mathematically? Append n items to an empty list. Resize copies happen at sizes 1, 2, 4, 8 ... log₂(n), each copying 1, 2, 4, 8 ... items. Total copy work: 1+2+4+...+n = 2n. Spread over n appends: 2n/n = 2, a constant. The series converges so the average cost per operation is O(1) regardless of n.

WHERE Where does O(n) membership bite hardest? Inside nested loops over large datasets. An ETL deduplication loop checking if row_id in seen_ids where seen_ids is a list becomes O(n²). With 500k rows that's 125 billion comparisons. Converting seen_ids to a set makes it O(n): 500k comparisons. A one-character change that turns a 2-hour job into 2 seconds.

from collections import deque

def recent_unique(events, window):
    """
    Return IDs appearing in the last `window` events, deduplicated,
    preserving order of first appearance within the window.
    Time: O(n)  Space: O(window)
    """
    recent = deque(maxlen=window)  # auto-drops oldest on append
    result = []
    seen   = set()                 # O(1) membership — crucial

    for event_id in events:
        # If window is full, the oldest element is about to be evicted
        if len(recent) == window:
            evicted = recent[0]
            # Only remove from seen if it won't appear again in new window
            # (deque evicts before the append, so check count now)
            if recent.count(evicted) == 1:
                seen.discard(evicted)

        recent.append(event_id)   # auto-evicts oldest if at maxlen

        if event_id not in seen:  # O(1) with set, O(window) with list
            seen.add(event_id)
            result.append(event_id)

    return result

# Tests
print(recent_unique([1, 2, 1, 3, 2, 4, 5], window=4))  # [1, 2, 3, 4, 5]
print(recent_unique([1, 1, 1, 1], window=3))            # [1]

# Complexity note:
# With set: O(n) overall — O(1) membership × n events
# With list: O(n × window) — O(window) scan × n events
# For window=10,000 and n=1,000,000: set=1M ops vs list=10B ops