By the end of this lesson, cadets will be able to:
Complete before class. There is no Beej chapter for linked lists; the supplementary notes are the spine.
| Source | Sections | Why |
|---|---|---|
| Lesson 29 Supplementary Notes | All of it (roughly 15 minutes of reading) | Self-referential structs, the node concept, traversal idiom, and head/tail insertion mechanics. The vocabulary for the rest of Block 4. |
| Beej-C | Chapter 8 (Structs) revisit | Optional. Beej does not cover linked lists directly, but a quick re-skim of struct definitions and the arrow operator helps if those feel rusty from L18-L19. |
struct song { ...; struct song *next; })malloc → initialize → wirewhile (curr != NULL) { ...; curr = curr->next; })head → A → B → C → NULL and this code:A, then B, then C, each on its own line, then exits when curr becomes NULL. head is never touched — only the local walking pointer moves.
Up to now your data has lived in arrays and structs of fixed size. A linked list breaks that contract: the data lives in nodes scattered across the heap, connected by pointers. The reference material below covers the four ideas you will see in lecture and use in the listbuild walkthrough.
The Lesson 29 deck covers why linked lists exist, the node anatomy, the traversal idiom, and the two insertion patterns. The listbuild walkthrough in Section 5 is where you practice each concept hands-on.
From CS110 onward you have stored sequences in arrays: contiguous memory, fixed size, indexed access in constant time. Arrays are excellent when you know how many elements you have and the elements rarely shift. Two problems arise when you do not.
Unknown length. When you read a stream of songs from a file or accept names from the user, you do not know how long the sequence is until it ends. Dynamic arrays (L19) handled this by reallocating with a larger buffer and copying, but every reallocation moves the data and invalidates any pointers into the old storage.
Cheap insertion at the front or middle. Inserting at the front of an array of length n requires shifting all n elements one slot to the right. A linked list inserts at the front in three pointer writes regardless of length. The trade is that random access (the equivalent of arr[5]) becomes a walk from the head instead of a constant-time lookup. Whether the trade is worth it depends on the workload.
A node is a struct with two responsibilities: hold one element's data, and hold a pointer to the next node in the chain. The pointer is the same type as the struct itself — self-referential.
The reason the inner self-reference says struct song *next and not song_t *next is sequencing: inside the struct body the typedef name does not exist yet. Once the closing brace and song_t are written, the typedef is in scope everywhere else.
Why a pointer and not the node itself? A node containing another whole node would have infinite size. A node containing a pointer to another node has fixed size — the pointer is just 8 bytes on a 64-bit machine, no matter how long the chain becomes.
Each node lives on the heap, allocated with malloc. After allocation, both fields contain garbage until you set them. The lifecycle is always allocate → initialize all fields → wire into the chain.
An empty list is the convention head == NULL. Functions that act on lists must handle this case first; reading a field through a NULL pointer is undefined behavior. NULL is also what marks the end of every non-empty chain — the last node's next is always NULL.
Every node you allocate must eventually be freed. We are deferring the safe-cleanup mechanics to Lesson 30; for this lesson, your lab includes a free_list function provided for you. Call it before main returns. The DFCS C Programming Standard, section 8.5, requires that dynamically allocated memory be freed; the rule was introduced at Lesson 15 and is in force for the rest of the course. See the Resources section for the full standard.
Visiting every node in the chain uses a walking pointer that starts at the head and steps along the next pointers until it falls off the end. The shape of the loop is identical whether you are printing, counting, summing, or searching.
Two things to internalize. First, head never moves — only the local curr does. If you walk head instead of a copy, you lose the list. Second, the check happens BEFORE the body, so an empty list (curr == NULL on entry) executes the body zero times — the right behavior.
Insertion at the head is three writes and does not depend on the list's length. Allocate the new node, point its next at the current head, then move head.
The order matters. If you reassign head first, the old chain becomes unreachable — every node after the original head is now an orphan.
Insertion at the tail is more involved because we do not name the last node. To find it, walk from the head until curr->next == NULL; that node is the tail. Then point its next at the new node.
Notice the loop condition: curr->next != NULL, not curr != NULL. We want to stop AT the tail, not walk past it. And if the list was empty on entry (head == NULL), this code dereferences NULL on the first line. The caller has to check for empty before calling the traversal, or the function checks first and reassigns head itself. The empty case is half of the work; the lab will surface this.
Three things to do in class. Use the checklist to track your progress.
Fourteen tasks across four sections. Build a three-song playlist node by node, walk it with a curr pointer, and insert a new song at the head. The diagram pane shows nodes as boxes with explicit addresses and drawn next-arrows; pointer variables appear above the nodes they target.
Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Lesson 29 reflection.
Six questions covering self-referential structs, the empty-list convention, traversal counting, head-insertion order, and the pass-by-value trap with linked-list functions. Pass at 70% or above; below that, replay the walkthrough and take the quiz again.
Enter your name. It will appear on the score card so you can include it in your screenshot for the Lesson 29 reflection.