CS50 Week 5 Explained: Linked Lists, Hash Tables and Tries

Week 5 takes the pointers from Week 4 and uses them to build structures that arrays can't manage. Every structure here makes a trade-off between speed, memory and simplicity. By the end you'll understand what sits behind a Python dictionary or a JavaScript object, and you'll build a spell checker that races against everyone else's.

▶

Watch the lecture

CS50x 2026, Lecture 5: Data Structures

2 h 4 min · Harvard University · CS50 on YouTube

Watch on YouTube ↗Week page ↗Harvard's notes ↗

Jump to the key moments

1. 0:43Jack Learns the Facts
2. 3:35Stacks and queues
3. 12:26Resizing arrays
4. 27:16realloc
5. 33:03Linked lists
6. 1:22:04Trees
7. 1:36:47Hashing and hash tables
8. 1:53:51Tries

Abstract data types: stacks and queues

Some structures are defined by how they behave rather than how they're built. 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 (or your email inbox, if you always read the newest first). You can build either on top of an array or a linked list.

Why arrays get awkward

An array has a fixed size. To add one more item, you often have to allocate a bigger block, copy everything across and free the old one, which is O(n) work every time it grows. realloc tidies up the code but not the underlying cost. That's the problem the rest of the lecture solves.

Linked lists

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node, and the last one points to NULL. Adding at the front is O(1): make a node and point it at the old first node. The cost is that finding an item is back to O(n), because you can't jump to the middle as you can with binary search. Each node also uses extra memory for its pointer.

Trees

A binary search tree gives each node two pointers: smaller values go left and larger values go right. Searching halves the options at every step, so it's O(log n), as long as the tree stays balanced. Insert sorted data into a naive tree and it degrades into a long, thin linked list.

Hash tables

A hash table is an array of "buckets", where each bucket is a linked list. A hash function turns a key (say, a word) into a bucket number, so you look in one small bucket instead of the whole collection. With a good hash function and enough buckets, lookups are close to O(1) on average. With a bad one, everything lands in the same bucket and you're back to a linked list.

Tries

A trie is a tree where each level is one letter of a word. Looking up a word takes as many steps as the word has letters, however many words are stored: constant time in practice. The trade-off is memory, because every node carries a slot for every possible letter.

Problem Set 5: what it asks

• Inheritance: build a family tree of blood-type alleles across three generations, then free it all. It's good practice in structs, pointers and recursion.
• Speller: implement the dictionary part of a spell checker (loading, hashing, checking, counting and unloading words) using a hash table. Your version is timed, so design choices show up in the numbers.

Where people get stuck

• Speller correctness first, speed second: get it working with a simple hash function and few buckets, run the tests, then improve the hash function and add buckets. Optimising broken code is a waste of an evening.
• Case: dictionary words are lowercase, but the texts you check aren't. Checking must be case-insensitive, and your hash function must give "Apple" and "apple" the same bucket.
• Unloading: free each node only after you've saved its next pointer. Otherwise you lose the rest of the list. Run Valgrind until it reports zero leaks.
• Inheritance's recursion: a person with no parents to generate is your base case. Everyone else gets two parents built by the same function, one generation down.

Check yourself