Arrays vs Linked Lists

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

The answer shapes every single operation — access, insert, delete — differently. Neither is universally better. The right choice depends on what you do most.

The intuition

An array is a row of numbered lockers.

Every locker is the same size, bolted to the wall, side by side. You want locker 47? Multiply the locker width by 47, add the starting address, arrive instantly — that is O(1) random access. But if you want to add a new locker between 12 and 13, every locker from 13 onward has to shuffle one slot to the right to make room. That is O(n) insert.

A linked list is a treasure hunt.

Each node holds a value and a slip of paper that says “the next clue is at memory address 0x3F4A.” You follow the chain from the head. Want the 5th item? Start at the head, follow four pointers — O(n). But once you have the right slip in hand, inserting a new step into the chain is trivial: write a new note, update two pointers — O(1). No shifting required.

Memory layout: why it matters beyond Big-O

The diagram above shows a subtlety Big-O notation drops on the floor: cache locality.

Array elements live in a contiguous block of RAM — contiguous meaning every element is stored at a consecutive address with no gaps between them. When the CPU fetches element [2], the cache line it loads also contains [3], [4], [5], and [6]. The next few reads are essentially free. This is why even an O(n) scan of a large array can be faster in practice than an O(log n) tree traversal that jumps around in memory — each tree hop may be a cache miss.

Linked list nodes can be anywhere on the heap. Following a pointer likely means fetching a fresh cache line each time. For modern CPUs that is expensive. The theoretical O(1) splice comes with a hidden constant that grows with the working set.

Python’s list is a dynamic array

Here is a misconception that catches many Python developers:

numbers = [10, 20, 30]   # this is a dynamic array, not a linked list
numbers[1]               # O(1) — direct index
numbers.append(40)       # amortized O(1) — see below
numbers.insert(0, 5)     # O(n) — every element shifts right

Python’s list is backed by a C array of pointers. Indexing is O(1). Appending is amortized O(1) — usually there is spare capacity at the end, so no reallocation is needed. Inserting at position 0 is O(n) because every existing pointer must move one slot right.

The practical linked structure: collections.deque

Bare linked lists are rare in Python code. The standard library gives you collections.deque — a doubly-linked list of fixed-size blocks — which is the right tool when you need O(1) operations at both ends:

from collections import deque

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

Use a plain list when you need fast random access and mostly append to the right. Use deque when you are implementing a queue (FIFO), a sliding window, or anything that pushes and pops from both ends frequently.

See the difference live

This snippet times list.insert(0, x) (which shifts the whole array) against deque.appendleft(x) (which updates one pointer) over a range of sizes.

As n doubles, the list time should roughly double (O(n)); the deque time should stay flat (O(1)).

When to use each

In practice, the vast majority of Python code uses list. You reach for deque the moment you catch yourself writing list.insert(0, …) or list.pop(0) in a loop.

Quick check