Lecture notes · CS50: Programming in C · Lecture 5

Data Structures

Harvard CS50 Introduction to Computer Science, lecture 5, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: the course website.

Part 1 · 0:00–10:00

This part introduces data structures, using queues and stacks as examples of ways to organize data in a computer's memory.

Key ideas

A data structure is a way to organize data so a program can use memory in clever ways to solve problems. An abstract data type describes what a structure does, and the programmer chooses how to build it. 1:02
A queue is an abstract data type that follows FIFO, meaning first in, first out. Like a line, the first person to join is the first person served. 1:45
A stack follows LIFO, meaning last in, first out. The most recent item added is the first one taken out, like a pile of plates. 5:24
Both a queue and a stack can be built with an array, which is a row of items stored one after another in memory. The array has a fixed size, so it can only hold so many items. 4:17
Adding an item to a queue is called enqueueing, and removing one is called dequeueing. For a stack, adding is called push and removing is called pop. 3:57

Words to know

abstract data type: A description of how a kind of data container behaves, without saying exactly how it is built inside the computer.
queue: A way of holding items where the first one added is the first one taken out, like people standing in line.
FIFO: First in, first out. The first item that goes in is the first item that comes out.
LIFO: Last in, first out. The last item that goes in is the first item that comes out.

Example

Think of a coffee shop line. Customers who join first get served first, which is FIFO and what a queue does. A stack of plates works the other way: you put the newest plate on top and take it off first, which is LIFO.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains why a fixed-size array is hard to grow, and why copying it into a bigger array works but is slow.

Key ideas

An array stores its data in one block of memory, back to back, and its size is fixed when you create it. Each item sits right next to the one before it. 12:25
You cannot just place a new item after the last one, because the memory there may already be used by other data. The computer only gives you the space you asked for. 13:28
One fix is to make a bigger array somewhere else, copy the old items over, add the new one, and free the old memory. This works, but it wastes memory for a while and takes time. 15:15
Copying is slow because you must visit every old item one at a time. The lesson says this takes about big O of n steps, which means the work grows with the number of items. 16:19
The demo uses a plain array of size 3 that prints 1, 2, 3. The lesson then starts to show how to replace it with malloc so the list can grow, but it says the full version will be much shorter later. 19:32

Words to know

contiguous: Stored in one unbroken block, with no gaps, back to back.
garbage value: Leftover junk in memory from earlier use. Its contents do not matter, but you still cannot write over it without asking the system first.
malloc: A function that asks the computer for a chunk of memory while the program runs, so the size does not have to be set in advance.
big O of n: A way to say that the amount of work grows in step with the number of items, n.

Example

Imagine three cars parked in a row with no gaps, and a fourth car arrives. If the spot next to them is already taken by something else, you cannot just squeeze the car in. You would need to find a longer empty row, move all the cars over one by one, and then park the new car, which takes time.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how to ask the computer for a block of memory with malloc, treat that block like an array, and resize it by copying the numbers into a bigger block.

Key ideas

malloc gives you a chunk of memory. You ask for the number of bytes you need by multiplying how many items you want by sizeof(int), which is the size of one int on your computer. 20:00
malloc can fail and return NULL instead of a real address. Always check for NULL, and stop the program if you get it. 20:38
Once you have a malloc'd chunk, you can use square brackets like an array. The computer does the offset math for you, so list[2] lands 2 times the size of an int from the start. 21:21
To make a block bigger, get a new block, copy the old numbers over, and free the old block so its memory is not lost. Forgetting the free causes a memory leak. 25:21
A simpler approach is to allocate extra space at the start and keep track of how much you use. But a large block wastes memory if the program only stores a few numbers. 29:21

Words to know

malloc: A function that asks the computer for a block of memory of a size you choose. It gives you back the address of that block.
NULL: A special address value, 0, that means something went wrong. You should never use memory at this address.
pointer arithmetic: The computer's ability to add or subtract addresses, so that moving from one number in memory to the next is handled for you.
memory leak: Memory that a program got but never gave back. It stays in use and can slow the computer down over time.

Example

Think of renting a storage locker that fits three boxes. When you suddenly need room for four, you rent a bigger locker, move the three boxes over, add the fourth, and give back the old locker so you stop paying for it.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

Instead of storing numbers side by side in one block, this part shows how to link separate chunks of memory together with pointers to form a linked list.

Key ideas

Looping through a list again and again to resize it gets slow, and a bigger list still runs into the same problem. So the lecture looks for a better design. 30:20
An array needs its memory to be contiguous, meaning back to back. A linked structure can use memory wherever free space is found, as long as each piece knows where the next piece is. 30:41
A pointer is a value that holds the address of another chunk of memory, like an arrow pointing to the next place. Linking chunks with pointers is what joins them into a chain. 36:49
Storing pointers takes extra memory, but it saves time because values no longer need to be copied from place to place. This is a trade-off between time and space. 38:41
Each box of memory in the chain is called a node. In a linked list, each node holds a value and the address of the next node. 39:49

Words to know

pointer: A value that stores the address of a place in memory, so it points to where something else is kept.
node: One box or chunk of memory in a chain. In this lesson, each node holds a value and a pointer to the next node.
linked list: A chain of nodes where each node points to the next one. The nodes can sit in scattered places in memory.
contiguous: Lying next to each other with no gaps, like items placed back to back.

Example

Think of a treasure hunt where each clue tells you where to find the next clue. The clues can be hidden in different rooms of the house, but by following each one you still reach the whole chain. A linked list works the same way: each node tells you where the next node is.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains how a linked list works, where each piece of data holds a pointer to the next piece, and how to write one in C.

Key ideas

A linked list stores each value in a node along with a pointer to the next node. The last node's pointer is set to a special null value so it does not point at random memory. 40:00
The main trade-off is extra space for the pointers. The gain is that the data never has to be copied or moved around, which can help with big programs and big data sets. 40:45
A linked list needs only one extra pointer, often called list, to find the first node. The other nodes are found by following the pointers inside each node. 41:49
In C, a node is a struct that holds an int for the number and a pointer to the next node. Writing struct node first lets the struct refer to itself, because C reads code from top to bottom. 43:40
Pointers should start as NULL so they do not hold garbage values. Memory for a new node is requested with malloc, and the arrow operator (->) is used to set its fields. 46:53

Words to know

pointer: A variable that holds the memory address of something else, so you know where to find it.
null: A special value, written as 0x0, that means a pointer points at nothing. It is a safe marker for the end of a list.
metadata: Extra information that helps organize your real data but is not the data you care about, such as the pointers in a linked list.
malloc: A C function that asks the computer for a block of memory of a given size and returns its address.

Example

Think of a line of train cars that are hooked together. Each car holds passengers, and each hitch points to the next car. The last car's hitch is empty, which tells you the train ends there, and you can add or remove cars without moving the passengers in the other cars.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how to build a linked list one node at a time, and why the order of updating pointers matters so you don't lose nodes.

Key ideas

A linked list is a chain of nodes, where each node holds a number and a pointer to the next node. The variable list holds the address of the first node, and the variable n is a temporary pointer used while building the list. 50:18
To keep things simple, each new node is added to the front of the list instead of being put in sorted order. 51:43
If you change list to point at a new node without first saving the old list's address, the old nodes become unreachable. The computer then treats that memory as lost, which is called a memory leak. 53:08
The safe order is to first copy the old list's address into the new node's next field, and only then update list to point at the new node. 53:50
Order of operations is very important when you stitch pointers together. Think about what you are connecting before you change any pointer. 54:37

Words to know

node: One piece of a linked list. It holds a value (here, a number) and a pointer to the next piece.
pointer: A variable that stores the memory address of something, so you know where to find it.
memory leak: Memory that the program still reserves but can no longer reach, because no pointer points to it anymore.
atoi: A function that converts text (a string of characters) into a whole number. The name stands for ASCII to integer.

Example

Imagine a line of people holding hands, where each person knows who is behind them. If you add a new person at the front, you must first have them hold hands with the current front person, and only then tell the group that they are the new front. If you tell the group about the new front first, the old line gets lost because nobody is holding on to its first person anymore.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part shows how to add nodes to the front or the end of a linked list, how to print every node, and why searching a linked list is slower than searching an array.

Key ideas

Before you point the list at a new node, first set the new node's next field to the current list. This keeps the existing nodes connected so none are lost. 1:00:00
To print the whole list, use a temporary pointer that starts at the first node, prints the number there, and then moves to the next node. It keeps going until the pointer becomes null, which means the end has been reached. 1:01:47
Adding a node to the front of the list takes the same few steps no matter how long the list is, so it is constant time, written O(1). The downside is that the numbers can end up in reverse order. 1:04:38
Searching a linked list takes O(n) time in the worst case, because you must visit nodes one at a time from the start. You cannot jump to the middle the way you can with an array, so binary search does not work here. 1:05:43
To add a node at the end, walk through the list until you find the node whose next field is null. Then set that next field to point to the new node. 1:09:39

Words to know

pointer: A variable that holds the location of something in memory, so you can find it and follow it to the next place.
node: One small piece of a linked list that holds a number and a pointer to the next node.
null: A special value that means nothing is there. At the end of a linked list, the last node's next field is null.
prepend: To add something at the very beginning of a list, before all the existing items.

Example

Think of a treasure hunt where each clue tells you where to find the next clue. You can only reach clue number 3 by first finding clues 1 and 2, and you cannot skip ahead by guessing where the middle clue is. That is how a linked list works: you must follow the chain from the start to reach any node.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:20:00

This part explains how to keep a linked list in sorted order, why that makes adding items slower, and why the lecturer then starts to explore tree structures as a way to get the benefits of both arrays and linked lists.

Key ideas

Adding a new node to the end of a linked list is slow once the list is long, because you must walk from the start to find the end. That makes insertion take time that grows with the list size, written as big O of n. 1:10:17
To keep a list sorted when numbers arrive in any order, the code checks three cases: an empty list, a new number that belongs at the front, and a number that belongs in the middle or at the end. The middle and end cases need a walk through the list. 1:11:24
Sorted insertion is still big O of n in the worst case, but it is often faster in practice than always adding to the end. Linked lists give flexible size but cost extra memory for pointers and slow searching, which is why the lecturer goes looking for a better structure. 1:15:46
A binary search tree keeps the halving idea of a sorted array, where the middle is checked, then the middle of each half, and so on. Storing those middles as linked nodes lets the structure grow without copying the whole array. 1:17:56
In a tree, the top node is the root and the nodes at the very bottom are the leaves. Each node holds a value plus pointers to nodes below it, so the structure branches out in two dimensions instead of one line. 1:19:20

Words to know

pointer: A stored memory address that tells the program where another piece of data is located.
node: One small container of data, such as a number, that also holds a pointer to the next node.
traverse: To walk through a list one node at a time, starting from the beginning, to reach a place in it.
big O: A way of describing how much longer a task takes as the amount of data grows. Big O of n means the time grows in step with the number of items.

Example

Imagine a row of books on a shelf where each book has a sticky note saying where the next book is. To put a new book in the right alphabetical spot, you have to walk along the row, checking each book until you find the place. The longer the row, the longer the walk, which is the same slowdown that happens when a linked list grows.

3 checked practice questions for this part are in the app.

Part 9 · 1:20:00–1:30:00

This part explains binary search trees, a way to store numbers in a two-branch tree so you can find any number quickly, and why the tree's shape matters.

Key ideas

In a binary search tree, each node holds a number and two pointers, a left child and a right child. For any node, everything in its left branch is smaller and everything in its right branch is larger. 1:20:43
Each branch of the tree is a smaller tree with the same rules, so the structure is recursive. A big tree is one root node plus two smaller trees. 1:21:04
Searching starts at the root and cuts the work in half at each step, so a balanced tree takes about log n steps instead of n steps. 1:23:35
The search code is short. If the tree is empty (null), return false. If the number you want is smaller, search the left side. If it is larger, search the right side. If it is equal, return true. 1:25:23
A binary search tree does not always stay balanced. If numbers are inserted in order, such as 1, 2, 3, the tree becomes a straight line like a linked list, and searching slows back down to n steps. 1:28:34

Words to know

node: A single box in a data structure that holds a value and points to other boxes.
pointer: A stored memory address that tells the program where to find another node.
binary search tree: A tree where each node has at most two children, with smaller values on the left and larger values on the right.
balanced: Evenly shaped, so the tree is not lopsided and each search can skip about half of the remaining nodes.

Example

Think of a guessing game where someone picks a number from 1 to 100 and you guess. If they say higher or lower, each answer lets you throw away half the possible numbers, just like a binary search tree lets you skip half of the tree at each step. If you guessed 1, 2, 3 in order every time, you would get no help from the answers and would have to check each number one by one, which is like a tree that has become a straight line.

3 checked practice questions for this part are in the app.

Part 10 · 1:30:00–1:40:00

This part explains how a dictionary stores pairs of keys and values, and how hashing and hash tables aim to find items quickly.

Key ideas

A dictionary is a data structure that stores keys and values, like a word and its definition. You look up the key to get the value. 1:30:41
A linked list can grow as needed, but finding an item in one can mean checking every item, which is slow. An array is fast to search, but it has a fixed size. 1:31:48
Hashing is a technique that takes many possible inputs and maps them to a smaller, fixed set of outputs. Sorting cards into four suit piles is an example. 1:34:15
A hash table combines an array with linked lists. The array gives fast access, and each spot can hold a linked list when several items land in the same place. 1:37:10
When two names start with the same letter, they collide in the same array spot. The solution is to string them together in a linked list at that spot. 1:39:35

Words to know

dictionary: A way to store information as pairs, where each key points to one value, like a word and its definition.
hashing: A technique that takes an input, such as a name, and turns it into one of a fixed set of outputs, such as a spot in a list.
hash table: A structure that uses hashing to pick a spot in an array for each key, so the item can be found quickly.
collision: What happens when two different keys are sent to the same spot, such as two friends whose names start with the same letter.

Example

Think of sorting a box of mixed playing cards into four piles by suit. You do not check every card each time you want one. You go straight to the right pile, then look only through that smaller pile. This is the idea behind hashing and hash tables.

3 checked practice questions for this part are in the app.

Part 11 · 1:40:00–1:50:00

This part explains how a hash table stores names in buckets, why crowded buckets can make it slow, and how a bigger table and a hash function help and cost something.

Key ideas

A hash table is an array where each slot holds a linked list. A hash function turns a name into a slot number, and names that land in the same slot are chained together in that list. 1:40:00
A collision happens when two different names map to the same slot. Hash tables expect collisions, and linked lists let the table keep growing when they happen. 1:40:00
In the worst case, every name lands in the same slot, so the table is just one long linked list. Searching it then takes O(n) time, meaning the time grows with the number of names. 1:40:00
Using a bigger array, such as one slot for every three-letter start, reduces collisions and can give constant time. The cost is memory, because many slots sit empty but must still exist. 1:40:00
The hash function in code takes a name and returns a number from 0 to 25 by converting the first letter to uppercase and subtracting 65, the ASCII value of 'A'. 1:40:00

Words to know

hash table: A list of slots where a function decides which slot each item goes into, so the item can be found again quickly.
collision: When two different items are sent to the same slot.
hash function: A rule that takes an input, such as a name, and gives back a slot number.
Big O: A way of describing how the time an algorithm takes grows as the amount of data grows. O(1) means constant time, and O(n) means the time grows with the number of items.

Example

Imagine a coat check where coats are sorted into hooks by the first letter of the owner's last name. If many people have last names starting with the same letter, one hook gets crowded and finding a coat takes longer. Adding more hooks, one for each pair or triple of letters, spreads people out but leaves many hooks empty.

3 checked practice questions for this part are in the app.

Part 12 · 1:50:00–2:02:19

This part explains how hash tables and tries store and find items quickly, and what each one costs.

Key ideas

A hash table splits items into buckets using a hash function. In theory a good hash function makes lookups almost instant, but if many items land in one bucket, the search becomes slow. 1:50:00
Splitting items into 26 buckets makes a search about 26 times faster in real time. Big O notation still calls it big O of n, because it ignores constant factors, but the clock still shows the difference. 1:51:22
A trie is a tree of arrays. Each letter of a name gets its own step down the tree, so finding a name takes about as many steps as the name has letters, no matter how many names are stored. 1:57:49
The trie gives fast lookups but wastes a lot of space. Most of its array slots are empty pointers, because many letter combinations are never used. 1:59:14
Sweetgreen's shelf sorted by first letter is a real-world hash table. It is fast most of the time, but it slows down when many orders share the same first letter. 2:00:43

Words to know

hash function: A rule that turns an input, like a name, into a number that says where to store it.
dictionary: A collection of key and value pairs, like a contact list where each name leads to a phone number and email address.
trie: A tree-shaped way to store words where each letter of a word is a step down the tree.
linked list: A chain of items where each item points to the next one, so you must check them one by one to find something.

Example

Think of a coat check where coats are put on hooks by the first letter of the owner's last name. If coats are spread evenly, you find yours quickly. If one letter gets almost all the coats, you end up searching a long pile, just like a slow hash table.

3 checked practice questions for this part are in the app.

← Week 4: Memory

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. Harvard CS50 · CC BY-NC-SA 4.0 · not affiliated with or endorsed by Harvard. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York