What a Singly Linked List Is Good and Bad At
Chapter Twenty-One
Syllabus topic Module 1, "Linked Structures: Advantages & Disadvantages, Singly Linked List"
Pages 62 to 64 of 411
In one line
A singly linked list buys cheap insertion and deletion anywhere, and unlimited growth, by giving up computed access, extra memory per item, and any ability to look backwards.
The advantages
1. Insertion and deletion cost nothing, given the position. Two assignments, whatever the length. Chapter 17 counted exactly 2 per node from 100 to 100,000. The array moved every item.
2. The size is not fixed. No maximum is declared and no block is reserved. The list grows while memory lasts and shrinks node by node. An array must either guess its size in advance or be rebuilt.
3. No memory is wasted on unused capacity. An array sized for 10,000 that holds 12 items keeps 9,988 empty cells. A linked list of 12 items holds 12 nodes.
4. No large contiguous block is needed. A machine whose memory is fragmented may be unable to provide one block of 10,000 cells while easily providing 10,000 scattered nodes.
5. Several structures fall out of it almost free. The stack, the queue and the deque of this module are all a linked list with the operations restricted.
The disadvantages
1. No computed access. Reaching item i costs i steps. The array computed the address. This is the big one, and it is what rules the linked list out whenever the work is indexing.
2. Extra memory per item. Every node carries an address beside its value. On a 64 bit machine that is 8 bytes per item, plus whatever the language's object header costs, which in Python is a great deal more.
3. No way to look backwards. Deletion needs the predecessor, so it is tracked on the way in; there is no reaching back. Chapter 26 pays for a backward link and chapter 29 measures what it costs.
4. Poor cache behaviour. Memory is fetched in blocks, so an array's next item is usually already there. A linked list's next node may be anywhere, so each step may be a fresh fetch. This is invisible to the counting and very visible on a real machine, which is the whole of chapter 22.
5. No binary search, even when sorted. Chapter 16 measured this: the comparisons drop to about ten and the pointer steps rise to ten times the length of the list.
The table
| Operation | Array | Singly linked list |
|---|---|---|
| Read or write item i | O(1) | O(n) |
| Insert at the front | O(n) | O(1) |
| Insert at the end | O(1) amortised | O(n), or O(1) with a tail |
| Insert in the middle, position known | O(n) | O(1) |
| Delete at the front | O(n) | O(1) |
| Delete at the end | O(1) | O(n), even with a tail |
| Search, unsorted | O(n) | O(n) |
| Search, sorted | O(log n) | O(n) |
| Memory per item | the value | the value plus an address |
| Growth | new block, full copy | one node |
What a Singly Linked List Is Good and Bad At
Read the first two rows together, because they are the whole bargain: the array wins the first, the list wins the second, and no structure in Module 1 wins both.
The sentence that is almost always wrong
"Linked lists are better than arrays for insertion."
It needs a condition, and without it examiners mark it down. Inserting into a linked list is O(1) once you are standing at the right place. Getting there is O(n). So inserting into a linked list by position is O(n) overall, exactly like the array.
The linked list wins when the position is already known: while traversing, at the front, at a node you already hold. That is why chapter 104 uses a linked list for hash table chains, where insertion is always at the front, and why the stack and the queue are built on one.
When to choose which, as a rule
| If the work is mostly | Choose |
|---|---|
| reading item i, or binary search | array |
| inserting and deleting at the front | linked list |
| inserting and deleting while traversing | linked list |
| appending and reading | array |
| unpredictable size, no indexing | linked list |
| small data, in a tight loop | array, for the cache |
Quick revision
- Advantages: O(1) insertion and deletion given the position; no fixed size; no wasted capacity; no
large contiguous block needed; stacks, queues and deques build on it.
- Disadvantages: O(n) access to item i; an address of memory per item; no backward link; poor cache
behaviour; no binary search even when sorted.
- The array wins access; the list wins insertion; neither wins both.
- "Better for insertion" is only true when the position is already known, because reaching a position
is O(n).
- Deleting the last node is O(n) even with a tail pointer.
Test yourself
1. Give three advantages of a singly linked list over an array. Insertion and deletion at a known position are O(1); the size is not fixed and no capacity is wasted; and it needs no single large contiguous block of memory.
2. Give three disadvantages. Access to item i is O(n); every node costs an extra address of memory; and there is no backward link, so deletion needs the predecessor tracked on the way in. Cache behaviour and the loss of binary search are two more.
3. Why is "linked lists are better for insertion" incomplete? Because insertion is O(1) only once you are at the position. Reaching position k is O(n), so insertion by position costs the same as the array's.
4. Name two places in this paper where the linked list's insertion advantage is genuinely realised. Hash table chaining, where insertion is always at the front of a bucket; and the stack, where every operation is at one end. The queue with a tail pointer is a third.
What a Singly Linked List Is Good and Bad At
5. Which operation is O(n) on a linked list even with a tail pointer, and why? Deleting the last node, because the node before it must be modified and only a forward walk can find it.
6. A program stores a few thousand integers and mostly reads them by index in a tight loop. Which structure and why? The array. Indexing is O(1) against O(n), and the contiguous layout uses the cache well, which matters more than the counting suggests.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.