The Fundamental Trade-off
An array gives you arr[500] in O(1) because the address is pure arithmetic: start + 500 × itemsize. A linked list has no such shortcut — you must start at the head and follow 500 pointers. That is O(n).
In exchange, inserting into the middle of an array costs O(n) because everything after the insertion point must shift up. In a linked list, once you are at the right place, insertion is O(1): create the node and rewire two pointers. Nothing moves.
Watch the cost table as you insert at position 0 versus the end — the traversal is where the time goes, never the insertion itself.
Rewiring, Step by Step
To insert node N after node P:
// N points to the rest of the list// P now points to N Order matters absolutely. Do those two lines the other way round and you overwrite
P.next before reading it — the remainder of the list becomes unreachable and is lost. This is the classic linked-list bug.
Singly vs Doubly Linked
- Singly linked — one pointer per node. Less memory, but you can only travel forward, and deleting a node requires knowing its predecessor.
- Doubly linked — next and prev. Costs more memory but allows backward traversal and O(1) deletion given only the node itself.
That last property is why LRU caches use a doubly linked list: when a hash lookup hands you a node, you can unlink and re-insert it at the front in constant time.
Why Arrays Often Win Anyway
Big-O says linked lists should beat arrays for insertion-heavy work. In practice arrays frequently win regardless, because of cache locality. Array elements sit contiguously in memory, so the CPU loads many at once. Linked-list nodes are scattered, and each pointer hop risks a cache miss costing hundreds of cycles.
This is a good reminder that Big-O counts operations, not time. Modern advice: reach for a dynamic array by default, and a linked list when you specifically need O(1) splicing with a node reference already in hand.
Nodes joined by references
A linked list stores each element in a node that holds a value and a reference to the next node. Nothing is contiguous in memory, and there is no index.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
# 1 -> 2 -> 3 -> None
head = Node(1, Node(2, Node(3)))
That single design difference from an array produces every trade-off:
| Operation | Linked list | Array / Python list |
|---|
| Access by index | O(n) — must walk | O(1) |
| Insert at front | O(1) | O(n) — shifts everything |
| Insert after a known node | O(1) | O(n) |
| Insert at end | O(1) with a tail pointer | O(1) amortised |
| Delete a known node | O(1) | O(n) |
| Search | O(n) | O(n) |
| Memory per element | Value plus a pointer | Value only |
| Cache behaviour | Poor | Excellent |
The last two rows are why Python's list is used almost everywhere despite the theoretical advantages above. A pointer per element is substantial overhead, and following pointers to scattered memory addresses defeats the CPU cache — frequently making an O(n) array scan faster in practice than an O(n) list walk.
Why insertion is O(1) only if you are already there
The advertised advantage — O(1) insertion and deletion — has a precondition that is easy to gloss over: you must already hold a reference to the relevant node.
Inserting after a node you have is three assignments. Inserting at position 500 means walking 500 nodes first, so the operation is O(n) overall.
That is why linked lists win in specific situations rather than generally: when you are already traversing, when you hold node references from elsewhere, or when you only ever touch the ends.
def insert_after(node, value):
node.next = Node(value, node.next) # O(1), given the node
def delete_after(node):
if node.next:
node.next = node.next.next # O(1), and the node is orphaned
For deleting a node you hold in a singly linked list, you need its predecessor — which you do not have. That is what doubly linked lists solve.
Singly, doubly, circular
| Type | Each node holds | Enables |
|---|
| Singly linked | next | Minimal memory; forward traversal only |
| Doubly linked | next and prev | Backwards traversal; O(1) delete given the node |
| Circular | Last points to first | Round-robin iteration |
Doubly linked is the practically important variant, because O(1) deletion given only the node is exactly what an LRU cache needs: a hash table maps keys to nodes, and the node can be unlinked and moved to the front in constant time.
That combination — hash table plus doubly linked list &mdash} is the standard LRU implementation, and it is the clearest example of a linked list being the right tool.
Circular lists suit round-robin scheduling and buffers where there is no natural end.
The sentinel or dummy-head trick is worth knowing: allocate one node before the real head, so insertion and deletion never need a special case for the first element. It removes most of the null checks that make linked-list code error-prone.
The trade, measured on both sides
Linked lists are taught as the alternative to arrays and then almost never used. Both halves of that are justified, and the reasons are opposite: the linked list wins the operation it is famous for and loses everything else, including some things by a much larger margin than the complexity table suggests.
Try it yourself
- Insert at position 0. Zero traversal steps — genuinely O(1), the linked list's best case.
- Insert at the end. The cost table shows the traversal dominating; the rewiring is still just two assignments.
- Delete from the middle and watch the pointer of the previous node jump over the removed one. Nothing else in the list moves.
- Search for a value. Every node must be checked in order — no binary search is possible, because you cannot jump to the middle.
- Switch to doubly linked and note the backward arrows, plus the extra pointer each node now has to store.
Where that leaves you
Linked lists make insertion and deletion cheap and access expensive — the exact opposite of arrays. Use them when you hold a reference to the node you need and are splicing constantly; otherwise an array's cache behaviour usually beats the theory.
The classic manipulations
Reversal is the canonical exercise, and the three-pointer form is worth knowing by heart:
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
Each step redirects one node's pointer backwards. The tuple assignment does it without a temporary, and the order matters: head.next is read on the right before being overwritten.
Finding the middle in one pass, with fast and slow pointers:
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow
Cycle detection (Floyd's algorithm) uses the same pointers and checks whether they meet. Resetting one to the head after they meet and advancing both by one finds the cycle's entry point.
Merging two sorted lists requires only pointer rearrangement and no extra allocation, which is why merge sort on a linked list uses O(1) extra space where merge sort on an array uses O(n).
Those four cover most linked-list problems, and all four are single-pass with constant extra memory.
When to actually use one
Genuinely good uses:
- LRU caches — doubly linked list plus hash map.
- Queues and deques — though
collections.deque uses a block-based structure that is better than a pure linked list. - Adjacency lists in some graph representations.
- Free lists in memory allocators.
- Undo stacks and version chains where nodes are held by reference.
- Immutable and persistent lists in functional languages, where sharing a tail between versions is free.
Poor uses:
- Anything needing indexed access.
- Anything where a Python
list would do, which is most application code. - Large collections traversed frequently — the cache penalty is real and often decisive.
In Python specifically, you will rarely implement one. list covers dynamic arrays, collections.deque covers double-ended queues efficiently. Linked lists appear as interview material and inside libraries rather than in ordinary code — which does not make them unimportant, because the pointer-manipulation reasoning transfers to trees and graphs.
Common mistakes
- Losing the head reference while traversing, so the list becomes unreachable.
- Not handling the empty list or single node. Most linked-list bugs live at these boundaries; a sentinel node removes them.
- Assigning pointers in the wrong order, orphaning the rest of the list. Read what you need before overwriting it.
- Forgetting to update the tail pointer when appending or deleting at the end.
- Creating a cycle accidentally, which turns any traversal into an infinite loop.
- Deleting a node in a singly linked list without its predecessor, which cannot be done properly — the usual hack copies the next node's value and deletes that node instead, and it fails on the last node.
Questions people ask
Why use a linked list when arrays are faster? For O(1) insertion and deletion at a held reference, and when there is no capacity to resize. Those cases are narrower than textbooks suggest.
Is a Python list a linked list? No — it is a dynamic array of pointers, contiguous, with O(1) indexing.
How do I find the length? Walk it: O(n). Maintain a counter if the length is needed often.
Singly or doubly linked? Doubly if you need backwards traversal or O(1) deletion given a node; singly to save the pointer.
Why is collections.deque fast? It is a doubly linked list of fixed-size blocks, so it gets O(1) ends with much better cache behaviour than one node per element.
Are linked lists still relevant? As a data structure in application code, rarely. As the reasoning behind trees, graphs, allocators and persistent structures, very.
Recap in one screen
- Each node holds a value and a reference; nothing is contiguous and there is no index.
- O(1) insertion and deletion — but only at a node you already hold; reaching position k is O(n).
- Doubly linked lists enable O(1) deletion given the node, which is what LRU caches rely on.
- Poor cache behaviour and a pointer per element make arrays faster in practice for most work.
- Use a sentinel head to remove the empty-list and first-element special cases that cause most bugs.