Arrays vs Linked Lists

Arrays and linked lists are two answers to the same plain question: how do you keep an ordered run of items in memory?

The answer you pick reshapes the cost of every operation that follows — reading, inserting, deleting. Neither is better in the abstract. The right one depends entirely on what you do most.

Two pictures

Think of an array as a row of numbered lockers, all the same size, bolted to the wall side by side. Want locker 47? Multiply the locker width by 47, add the starting address, and arrive in a single step — that is O(1) access to any index. But to squeeze a new locker between 12 and 13, every locker from 13 onward has to shuffle one place over to open a gap. That shuffling is O(n).

Think of a linked list as a treasure hunt. Each node holds a value and a slip of paper saying “the next item is over at this address.” You start at the head and follow the slips. Want the fifth item? Follow four slips to get there — O(n). But once you are holding the right slip, slipping a new node into the chain is trivial: write one new note, rewire two pointers — O(1), with nothing to shuffle.

Cache locality — the cost Big-O drops

There is a real difference here that Big-O never mentions: cache locality.

Array elements sit at consecutive addresses, with nothing between them. When the CPU fetches element 2, the cache line it pulls in also carries 3, 4, and 5 — so the next few reads are almost free. Linked-list nodes can live anywhere on the heap, so following each pointer is likely a fresh trip to main memory, and those trips are slow. This is why an O(n) scan of a packed array often beats an O(log n) walk through a pointer-chasing tree: the array stays hot in cache, while the tree keeps missing. The linked list’s lovely O(1) splice carries a hidden constant that grows with how scattered its nodes are.

Python’s list is a dynamic array

A common surprise: Python’s list is not a linked list. It is a dynamic array — a contiguous block of pointers.

nums = [10, 20, 30]
nums[1]            # O(1) — direct index arithmetic
nums.append(40)    # O(1) amortised — usually spare room at the end
nums.insert(0, 5)  # O(n) — every element shifts one slot right

Indexing is instant. Appending is amortised O(1): there is normally spare capacity at the end, and when there is not, the list copies itself into a block about 1.125× larger — an O(n) step that happens so rarely the average append stays O(1). Inserting at the front, though, shifts every element, so it is O(n) every time.

The practical linked structure: collections.deque

You will rarely build a raw linked list in Python. When you genuinely need O(1) work at both ends, the standard library hands you collections.deque, a doubly-linked list of small blocks:

from collections import deque

q = deque([1, 2, 3])
q.appendleft(0)   # O(1) at the front
q.append(4)       # O(1) at the back
q.popleft()       # O(1) from the front

The rule of thumb is short:

Most Python code uses list. You reach for deque the moment you catch yourself writing list.insert(0, …) or list.pop(0) inside a loop — the silent O(n²) trap from the built-ins lesson.

Practice