The Array Against the Linked List, Measured
Chapter Twenty-Two
Syllabus topic Computer Science Practical 3, Module 2, "Compare static (array) vs dynamic (linked) approaches"
Pages 65 to 67 of 411
In one line
Counted head to head, the array wins access by a factor of the list's length, the linked list wins front insertion by the same factor, and each is useless at what the other is good at.
Both structures, the same operations
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
class LinkedSeq:
"""A singly linked list, counting every pointer step and assignment."""
def __init__(self):
self.head = None
self.n = 0
def prepend(self, value):
self.head = Node(value, self.head)
self.n += 1
return 2 # two assignments
def get(self, i):
walk, steps = self.head, 0
while i > 0:
walk = walk.next
steps += 1
i -= 1
return walk.data, steps + 1
class ArraySeq:
"""A fixed array, counting every element moved and every index computed."""
def __init__(self, capacity):
self.cells = [None] * capacity
self.n = 0
def prepend(self, value):
moves = 0
for i in range(self.n, 0, -1): # shift everything up one
self.cells[i] = self.cells[i - 1]
moves += 1
self.cells[0] = value
self.n += 1
return moves + 1
def get(self, i):
return self.cells[i], 1 # one address computation
for n in (500, 1000, 2000, 4000):
linked, array = LinkedSeq(), ArraySeq(n)
link_build = sum(linked.prepend(i) for i in range(n))
array_build = sum(array.prepend(i) for i in range(n))
_, link_get = linked.get(n - 1)
_, array_get = array.get(n - 1)
print("n = %4d | build by prepending: array %8d, linked %5d "
"| read the last item: array %d, linked %4d"
% (n, array_build, link_build, array_get, link_get))n = 500 | build by prepending: array 125250, linked 1000 | read the last item: array 1, linked 500
n = 1000 | build by prepending: array 500500, linked 2000 | read the last item: array 1, linked 1000
n = 2000 | build by prepending: array 2001000, linked 4000 | read the last item: array 1, linked 2000
n = 4000 | build by prepending: array 8002000, linked 8000 | read the last item: array 1, linked 4000Both columns of that table are the same fact seen from two sides.
Building by prepending: the array's work quadruples when n doubles, because each of n insertions moves about n items. The list's doubles, because each insertion costs 2 whatever happens. At n = 4000 the array did a thousand times the work.
Reading the last item: the array does 1 unit of work at every size. The list does n. At n = 4000 the list did four thousand times the work.
Neither structure is better. They are opposites.
The thing counting cannot see
There is a real effect that no count above captures, and the practical's comparison is incomplete without it.
Memory is fetched from main memory into cache in blocks, typically 64 bytes at a time. An array's items sit together, so fetching item 0 usually brings items 1 to 15 along with it for free. A linked list's nodes are wherever the allocator put them, so each step may be a fresh fetch from main memory, which is far slower than a cache hit.
The Array Against the Linked List, Measured
The consequence, and it surprises people: an array often beats a linked list at operations the counting says the list should win, once the data is large enough for cache to matter, because the array's 1,000 cheap moves can beat the list's 2 expensive pointer chases.
This book does not print a timing to prove that, for the reason chapter 1 gave. What it does is state it and name it, because an examiner asking "is a linked list always better for insertion" is asking about exactly this.
The comparison, as the practical wants it written
| Static array | Dynamic linked list | |
|---|---|---|
| Size | fixed at creation | grows and shrinks at run time |
| Memory | one contiguous block | scattered nodes |
| Extra memory | unused capacity is wasted | one address per item |
| Access item i | O(1), computed | O(n), walked |
| Insert at front | O(n) | O(1) |
| Insert at end | O(1) | O(n), or O(1) with a tail |
| Insert at a known position | O(n) | O(1) |
| Delete at front | O(n) | O(1) |
| Delete at end | O(1) | O(n) |
| Search unsorted | O(n) | O(n) |
| Search sorted | O(log n) | O(n) |
| Cache behaviour | good | poor |
| Needs contiguous memory | yes | no |
Choosing between them, as one sentence
If the work is dominated by reaching items by position, use the array. If it is dominated by inserting and removing at positions you are already standing at, use the linked list. If it is both, you need a structure from Module 2.
That last clause is the bridge. Every structure in Module 2 exists because Module 1's two structures each fail at half the job.
Quick revision
- Counted head to head: building 4,000 items by prepending cost the array 8,002,000 moves and the list
8,000 assignments; reading the last item cost the array 1 and the list 4,000.
- The array's prepending work quadruples when n doubles; the list's doubles.
- They are opposites, not better and worse.
- Counting cannot see cache: an array's items are fetched together in blocks, a list's nodes are
scattered, so an array often wins in practice even where the count says otherwise.
- Array: fixed size, contiguous, O(1) access, expensive insertion except at the end.
- Linked list: grows at run time, scattered, O(n) access, O(1) insertion at a known position.
- If the work needs both cheap access and cheap insertion, neither is enough, and that is why Module 2
exists.
Test yourself
1. At n = 4000, what did building by prepending cost each structure, and why do they differ so much? The array did 8,002,000 moves and the list 8,000 assignments. Each array insertion shifts about n items while each list insertion costs two assignments whatever the length.
The Array Against the Linked List, Measured
2. At the same size, what did reading the last item cost each? The array 1 unit, the list 4,000. The array computes the address; the list must walk.
3. What effect does counting fail to capture, and which structure does it favour? Cache behaviour. Memory is fetched in blocks, so an array's neighbouring items come along for free while a linked list's scattered nodes may each need a fresh fetch. It favours the array.
4. Give the four rows of the comparison that concern memory. The array is a fixed contiguous block and wastes unused capacity; the list is scattered nodes and costs one address per item.
5. State in one sentence when to choose each. The array when the work is reaching items by position; the linked list when the work is inserting and removing at positions you are already at.
6. Why does this comparison point forward to Module 2? Because each structure fails at half the job, and a problem needing both cheap access and cheap insertion cannot be solved by either. Trees and hash tables are the answers.
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.