Introduction to Computer Science: Harvard CS50 · Course book
Chapter 5: Arranging Data for Speed
An array is a fine way to store a list whose size you know in advance. Real data rarely cooperates: a contact list grows, a dictionary of words must be searched quickly, a queue of tasks changes constantly. A data structure is a way of arranging values in memory so that the operations a program needs most, such as adding, finding or removing, are fast. This chapter builds four of the most important from the pointers of Chapter 4: resizable arrays, linked lists, trees and hash tables, with a brief look at a fifth, the trie. Each is a different trade-off between speed and memory, and choosing well is a large part of writing good software.
The trouble with arrays
An array's elements sit next to each other in memory. That is what makes reaching element i instant: its address is simply the start plus i times the size of an element. But it also means an array cannot simply grow. The memory just after it may already be in use by something else.
To add an element to a full array, a program must ask for a new, larger block, copy every existing element across, and free the old block. C provides a function, realloc, that does exactly this. The cost lies in the copying, and it depends heavily on how much bigger the new block is.
Suppose a program adds 40 items one at a time. If it grows the array by just one slot each time, it copies 1 element, then 2, then 3, and so on, 1 + 2 + … + 39 = 780 copies in all. If instead it doubles the size whenever the array is full, copies happen only at sizes 1, 2, 4, 8, 16 and 32, totalling 63. For 1,000 items the difference is 499,500 copies against 1,023.
Doubling is how resizable arrays in most modern languages work, including Python's lists. Even so, inserting an item in the middle of an array means shifting every later element along, and any resizing needs a moment of double the memory. Other structures avoid these costs.
Linked lists
A linked list stores each value in its own small block of memory, called a node, which also holds a pointer to the next node. The nodes can be scattered anywhere; the pointers string them together. The last node's pointer is NULL, marking the end, and the program keeps one pointer, often called the head, to the first node.
In C a node is defined with a struct, which groups several values into one type:
typedef struct node
{
int number;
struct node *next;
}
node;
Adding a value is cheap. To insert at the front, allocate a node with malloc, set its next pointer to the current head, and make the head point to the new node. Nothing else moves, however long the list. The order of those steps matters: if the head were changed first, the rest of the list would be lost, with nothing pointing to it.
Freeing a linked list needs the same care. A loop walks from the head, but before freeing each node it must save that node’s next pointer in a temporary variable; once a node is freed its contents can no longer be trusted, so reading next afterwards would follow a pointer into memory that no longer belongs to the program. The pattern is: remember the next node, free the current one, move to the remembered one, and repeat until reaching NULL.
The price is searching. There is no way to jump to the middle of a linked list; you must start at the head and follow pointers one by one, so finding a value takes up to n steps, and binary search is impossible. Each node also needs extra memory for its pointer, 8 bytes on a 64-bit computer, so a list of ints uses three times the memory of an array of ints.
Trees
A binary search tree gives each node two pointers, to a left and a right child, and keeps one rule: everything in a node's left branch is smaller than it, and everything in its right branch is larger. To find a value, start at the top, the root, and go left or right at each node depending on whether the target is smaller or larger.
A balanced tree of n values has about log₂ n levels, so searching, inserting and deleting all take about log n steps: around 20 for a million values. The tree combines the fast searching of a sorted array with the cheap insertion of a linked list. The catch is balance. Insert values already in order, 1 then 2 then 3, and every node goes to the right, producing a long chain that is no better than a linked list. Practical trees rearrange themselves as they grow to stay balanced.
Hash tables and tries
A hash table aims for something even better: finding a value in roughly constant time, whatever the amount of data. It combines an array with linked lists. A hash function turns each value into an index; the value is stored in the list at that index of the array, called a bucket.
A simple hash function for names uses the first letter: names beginning with A go to bucket 0, B to bucket 1, and so on to Z at bucket 25. To look up "Hannah", go straight to bucket 7 and search only its short list. Two names in one bucket, such as "Henry" and "Hugo", are a collision, handled by chaining them in that bucket's linked list.
The weakness is the hash function. With 26 buckets and many thousands of names, each list is still long, and real names cluster on some letters. Better hash functions mix all the characters of the value and use many more buckets, spreading values evenly. With a good function and enough buckets, each list holds only a few items and lookups are nearly instant. In the worst case, though, if everything lands in one bucket, a hash table degrades to a single linked list.
A trie, from the word retrieval, takes a different route for words. It is a tree in which each node is an array of 26 pointers, one per letter. Storing "cat" means following the pointer for c from the root, then a, then t, and marking the final node as the end of a word. Looking up a word takes as many steps as it has letters, no matter how many words are stored. The price is memory: every node holds 26 pointers, most of them NULL.
| Structure | Search | Insert | Main strength | Main cost |
|---|---|---|---|---|
| Array (sorted) | log n | n | Instant access by index; binary search | Resizing and shifting elements |
| Linked list | n | 1 (at the front) | Grows without copying | Slow search; extra pointer per value |
| Balanced binary search tree | log n | log n | Fast search and insertion, values kept in order | Two pointers per value; must stay balanced |
| Hash table | About 1 on average | About 1 on average | Very fast lookups | Depends on a good hash function; no ordering |
| Trie | Length of the word | Length of the word | Lookup time independent of how many words are stored | A great deal of memory |
Real programs often combine structures. A hash table whose buckets are linked lists is one example; another is a hash table of tries, or an array of trees. The question to ask is always which operations the program performs most often, and how much memory it can afford.
There are also abstract structures defined by behaviour rather than layout. A queue is first in, first out, like a line at a shop; a stack is last in, first out, like a pile of trays. Either can be built from an array or a linked list. What matters to the program using it is only the rule for adding and removing.
Check your understanding
- Why can an array not simply grow into the memory just after it?
- How many elements are copied when 10 items are added one at a time to an array that grows by one slot? (Answer: 1 + 2 + … + 9 = 45.)
- When inserting at the front of a linked list, why must the new node point to the old head before the head is changed?
- In the tree of Figure 5.2, which nodes are visited when searching for 3? (Answer: 4, 2, 3.)
- About how many levels does a balanced binary search tree of 1,000 values have? (Answer: about 10.)
- Using the first-letter hash function, which bucket does "Rosa" go in? (Answer: R is the 18th letter, so bucket 17.)
- Why does a trie's lookup time not depend on the number of words stored?
This course book is available to read online only at tech-academy.chrysolites.org.