14 of 32 · 5 min
Linked lists: the opposite trade
An array is contiguous. A linked list is the opposite: each node holds a value and the address of the next one, and they can sit anywhere in memory.
[ 10 | ●─]──> [ 20 | ●─]──> [ 30 | ✗ ]That one change flips every cost from the array page.
| Operation | Array | Linked list |
|---|---|---|
| Index | O(1) | O(n), walk from the head |
| Insert at start | O(n) | O(1) |
| Insert after a known node | O(n) | O(1) |
| Delete a known node | O(n) | O(1) |
| Search | O(n) | O(n) |
| Memory per item | Just the value | Value plus a pointer |
Inserting at the start of an array moves everything. In a linked list it is two assignments, whatever the length.
The reversal, which every interview asks for
def reverse(head):
prev = None
while head:
nxt = head.next # remember where we were going
head.next = prev # turn this arrow around
prev = head # step prev forward
head = nxt # step head forward
return prevFour lines, and the order of them is the entire problem. Set head.next before saving nxt and the rest of the list is unreachable.
Variants
Singly points forward only. Doubly points both ways, which makes deleting a node you are standing on O(1) instead of needing its predecessor, at the cost of another pointer per node. Circular has the last node point at the first, which is how round-robin schedulers are built.
Why arrays usually still win
A linked list has better complexity for insertion and worse real performance for almost everything, because its nodes are scattered and the processor cache cannot predict where the next one is. An array of a million integers is read far faster than a linked list of a million, despite identical O(n).