Card 06/ 09
Linked List vs Dynamic Array
Rewiring beats shifting only when you already hold the node you want to change.
A dynamic array and a linked list both hold a sequence, and each is cheap exactly where the other is expensive. This card covers the two side by side, operation by operation, and the condition under which each one wins.
A dynamic array keeps its elements in one block of adjacent cells and grows by copying them into a block twice the size, so an append is O(1) amortised, meaning on average over many appends, and the element at index i is found by arithmetic. A linked list keeps each element in its own node with a reference to the next node, and a doubly linked list adds a reference to the previous one, so finding position i means following references from the head.
Three axes decide between them: the cost of reaching a position, the cost of a change once there, and the memory each element carries. The table puts every common operation against all three structures, each list keeping head and tail references.
| Operation | Dynamic array | Singly linked list | Doubly linked list |
|---|---|---|---|
| Read the element at position i | O(1) | O(n) | O(n) |
| Search for a value | O(n) | O(n) | O(n) |
| Binary search a sorted sequence | O(log n) | O(n) | O(n) |
| Insert or delete at the front | O(n) | O(1) | O(1) |
| Append at the end | O(1) amortised | O(1) | O(1) |
| Delete the last element | O(1) | O(n) | O(1) |
| Insert or delete at position i | O(n) | O(n) | O(n) |
| Insert after a node you hold | Not applicable | O(1) | O(1) |
| Delete a node you hold | Not applicable | O(n) | O(1) |
| Extra memory per element | None | One reference | Two references |
Two rows hide the usual mistakes. Inserting at position i is O(n) in every column: the array shifts the elements after i, and the list walks i nodes to reach the place before it relinks in O(1). The O(1) rewire only pays when the program already holds the node, from a search it needed anyway or from a map of its nodes. Binary search, which halves a sorted range by looking at its middle element, needs to reach any middle in O(1). On a list each middle is a walk of half the remaining nodes, and those walks add up to O(n), no better than checking every node in turn.
The array has a further advantage the table does not show: its cells sit next to each other, and the processor fetches neighbouring memory together, so walking an array is faster in practice than following references to nodes scattered across memory.
The decision rule: use a dynamic array by default, and above all when the program reads by position or searches a sorted sequence. Use a linked list when the program changes the sequence at nodes it already holds, at the front or in the middle, so it never pays the walk; and make it doubly linked when it also deletes those nodes or works from the back.
← → move through sections and cards