Arrays, linked lists, stacks and queues

Contiguous memory versus pointers, why pop from the front is the classic performance mistake, and how to pick a container.

Contiguous memory versus pointers

An array holds its elements next to each other, so index i is one multiplication away and the hardware prefetcher reads ahead for free. A linked list holds each element in its own allocation with a pointer to the next, so reaching index i means following i pointer hops and touching memory that is scattered across the heap.

import sys
from array import array as c_array

# A Python list is a dynamic array of pointers: contiguous, with growth by doubling
dynamic = []
for i in range(10):
    dynamic.append(i)
print(sys.getsizeof(dynamic))       # grows in steps as capacity doubles
print(dynamic[5])                   # O(1): base address plus offset

# array.array stores raw values with no pointer indirection: 8 bytes per float
raw = c_array('d', [1.0, 2.0, 3.0])
print(raw.itemsize * len(raw), sys.getsizeof(raw))

dynamic.insert(0, -1)               # O(n): every element shifts right
del dynamic[0]                      # O(n) for the same reason

# A node-based list shows why the pointer chasing costs more
class Node:
    __slots__ = ('value', 'next')

    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)        # O(1) prepend, no shifting at all
    return head

def at(head, index):
    for _ in range(index):
        head = head.next            # O(index) hops, each a cache miss
    return head.value

head = build([3, 2, 1])
print(at(head, 2))                  # 1

Python's list over-allocates so that appends stay amortised O(1); array.array and NumPy arrays store raw values and cut memory per element by an order of magnitude on numeric data, at the cost of a fixed element type.

Stacks and queues

from collections import deque
import heapq

# Stack: last in, first out. A list is already a stack.
stack = []
stack.append('a')          # push
stack.append('b')
top = stack.pop()          # pop -> 'b', O(1)
print(top, stack[-1])      # b a

# Queue: first in, first out. Never use list.pop(0).
queue = deque(['a'])
queue.append('b')          # enqueue at the right, O(1)
first = queue.popleft()    # dequeue from the left, O(1)
print(first)

# Priority queue: always hands back the smallest item
pq = []
heapq.heappush(pq, (3, 'deploy'))
heapq.heappush(pq, (1, 'rollback'))
print(heapq.heappop(pq))   # (1, 'rollback')

# Balanced parentheses: the textbook stack
PAIRS = {')': '(', ']': '[', '}': '{'}

def balanced(text):
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

print(balanced('a(b[c]d)e'))    # True

import time
from collections import deque

# Measuring the mistake: pop(0) shifts the whole array every single time
n = 20000

items = list(range(n))
start = time.perf_counter()
while items:
    items.pop(0)
print('list pop from front :', round(time.perf_counter() - start, 4), 's')

items = deque(range(n))
start = time.perf_counter()
while items:
    items.popleft()
print('deque popleft       :', round(time.perf_counter() - start, 4), 's')

# The ratio grows with n: 20x here, far more at a million items

# Breadth-first search is a queue; depth-first search is a stack
graph = {'a': ['b', 'c'], 'b': ['d'], 'c': [], 'd': []}

def bfs(graph, start):
    order, seen, queue = [], {start}, deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

def dfs(graph, start):
    order, seen, stack = [], set(), [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        stack.extend(graph[node])
    return order

print(bfs(graph, 'a'), dfs(graph, 'a'))

Choosing a container

• Index by position and iterate constantly: an array or list. Nothing else is as cache-friendly.
• Push and pop from one end only: a stack. In Python that is a plain list.
• Push and pop from both ends: collections.deque, an O(1) double-ended queue built from blocks of items.
• Always take the smallest or largest remaining item: a heap, which gives O(1) peek and O(log n) insert and extract.
• Insert and delete frequently in the middle, while iterating: a linked list, but only if you already hold the node. Otherwise the search is the O(n) part and the array wins anyway.
• Python's list is a better default than a hand-rolled linked list in nearly every case: the pointer overhead per node and the cache misses usually outweigh the asymptotically better insert.

FAQ

Related

Hash tables Complexity and Big-O in practice

Last refreshed 2026-09-18.