CS210 · Block 4 · Lesson 30

Linked Lists II: Deletion

Removing nodes · The prev/curr splice · Edge cases · Freeing in order · No leaks
At a glance: Last lesson you built the playlist. Today you take it apart. Removing a node means rewiring the chain around it with a two-pointer walk, then freeing the node's two heap allocations in the right order. The traps are all about edges and memory: the empty list, the single node, the head, the tail, and the double free. You practice every case in the deletion walkthrough in Section 5, then add three delete functions to your Lesson 29 code in the lab.
Contents
  1. Lesson Objectives
  2. Assigned Readings
  3. Pre-Class Work
  4. Lesson Materials and Overview
  5. In-Class Work
  6. After Class
1. Lesson Objectives

By the end of this lesson, cadets will be able to:

  1. Remove a node from a singly-linked list using the prev/curr two-pointer splice. (Outcome 2)
  2. Handle deletion's edge cases correctly: empty list, single node, deleting the head, and deleting the tail. (Outcomes 1, 2)
  3. Free a removed node's two heap allocations in the correct order (title before node) with no leaks and no double frees. (Outcome 3)
  4. Explain free_list as the per-node delete pattern applied to every node in a loop. (Outcome 1)
2. Assigned Readings

Complete before class. The supplementary notes are the primary reading; they carry the deletion mechanics this lesson is built on.

Source What Why
Lesson 30 Supplementary Notes (instructor-written) Deletion: the two-pointer splice, edge cases, freeing in order The core mechanics you will use in the walkthrough and the lab
Your Lesson 29 notes and code Review node structure, traversal, and free_list You build directly on last lesson's playlist
3. Pre-Class Work
Do this first
Plan on about 30 minutes. The deletion mechanics are short but precise; the order of operations is the whole game. Come ready to type in the walkthrough.

Pre-Class Checklist

1
Read the Lesson 30 supplementary notes
Pay attention to four ideas you will use immediately:
  • The prev/curr two-pointer walk
  • The splice: prev->next = curr->next;
  • Freeing both allocations, title before node
  • The edge cases: empty list, single node, head, tail
2
Make sure your Lesson 29 playlist still builds
This lab starts from your Lesson 29 playlist.c. Confirm it compiles cleanly before class so you can spend class time on deletion, not on fixing last lesson's code.
$ gcc -Wall -Werror -std=c99 main.c playlist.c -o playlist
$ ./playlist
If your Lesson 29 code has problems, schedule EI before class. You need a working playlist to build on.
3
Skim the In-Class section below
You will see an interactive deletion walkthrough that starts with a three-song playlist already built. No need to use it yet; just know it is there.
4. Lesson Materials and Overview

Deletion is where the pointer discipline from last lesson earns its keep. Inserting only ever added links; deletion removes them, and a removed node also owns memory that has to be returned. Get the order of operations wrong and you either leak memory or read memory you have already freed. The reference material below walks each piece you will see in lecture and practice in the walkthrough.

Jump to
Slides The Deletion Problem prev/curr Walk The Splice Freeing in Order Edge Cases free_list Revisited

Slides

The Lesson 30 deck covers the deletion problem, the prev/curr walk, the splice, freeing in the right order, the four edge cases, and how free_list is just deletion in a loop. The slides anchor the lecture; the walkthrough is where you practice each move hands-on.

Open Lesson 30 slides →

The deletion problem

To remove a node from the middle of a chain, you have to make the node before it point to the node after it, so nothing in the list still routes through the one you are removing. In a singly-linked list each node only points forward, so a node has no way to find the one ahead of it. That single fact drives everything about deletion: you must arrive at the victim already holding a pointer to its predecessor.

The prev/curr two-pointer walk

The fix is to walk the list with two pointers instead of one. curr finds the node you want; prev trails exactly one step behind it. When curr lands on the target, prev is already sitting on the predecessor, which is the node whose next you need to rewire.

song_t *prev = NULL;
song_t *curr = head;
while (curr != NULL && strcmp(curr->title, target) != 0) {
  prev = curr;
  curr = curr->next;
}
// curr is the victim (or NULL); prev is the node before it

The splice

With prev on the predecessor and curr on the victim, one assignment removes the node from the chain:

prev->next = curr->next;  // route around curr

This one line handles the tail case for free: if curr is the last node, curr->next is already NULL, so prev->next becomes NULL and the list ends correctly.

Freeing in the right order

A node owns two heap allocations: the node struct, and the title string it points to. After you unlink the node you must free both. Order matters:

free(curr->title);  // title first...
free(curr);        // ...then the node

If you free the node first, curr->title is unreachable: the string leaks and the read itself is a use-after-free. free never follows pointers inside a struct for you, so it will not free the title on its own.

The four edge cases

Case What is different
Empty list Nothing to delete. Return NULL immediately; never dereference a NULL head.
Deleting the head The head has no predecessor. Move head forward first, then free the old node, and return the new head.
Single node Deleting the only node empties the list. The list collapses to NULL.
Deleting the tail No node names the tail, so walk prev/curr until curr->next == NULL. The general splice handles it.

free_list, revisited

In Lesson 29 you were handed free_list and told to take it on faith. Now you can read it for what it is: the per-node delete you just learned (save the next pointer, free the title, free the node) applied to every node in a loop. It walks the chain once, freeing both allocations of each node in order, until it runs off the end at NULL. free_list stays provided in the lab; you do not rewrite it. Your job is the three single-node delete functions.

5. In-Class Work

Three things to do in class. Use the checklist to track your progress.

  • Work through the deletion walkthrough below. Fourteen guided tasks: splice a middle node out, delete the head, and empty the list, freeing memory at every step. About 25 minutes.
  • Take the deletion self-check. Six questions on the splice, the prev/curr pair, free order, and the edge cases. About 10 minutes.
  • Complete Lab 30: Playlist Deletion. Add delete_head, delete_tail, and delete_by_title to your Lesson 29 code. Auto-graded through GitHub Classroom.

Deletion Walkthrough

Fourteen tasks across three sections. The playlist starts with three songs already built. Type each C statement at the prompt; the terminal narrates what happened and the diagram shows the chain, the prev/curr walkers, and any node you have freed.

Before you begin

Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Lesson 30 reflection.

CS210 Lesson 30 · Linked List Deletion

Fourteen tasks across three sections. Remove songs from the playlist you built last lesson without leaking memory or breaking the chain. The terminal shows what the simulator did; the diagram pane shows the chain, the head pointer, the prev and curr walkers, and any node you have freed.
Task 0 of 14
Section 1: The two-pointer dance
Current task
Loading...
Playlist
Loading the playlist...
listsim>
How this works: This is not a Linux terminal. It is a teaching tool that simulates a singly-linked list of song nodes. The playlist starts with three songs already built. The task card tells you what to type; in walkthrough mode only the expected command advances. Mistype twice and the hint button will pulse. After all tasks are complete, free mode unlocks so you can delete from the tail, break the splice on purpose, or trigger a double free and see what the diagram does.

Deletion Self-Check

Six questions. Answer each one and submit to see how you did. The final summary gives you a completion code and tells you whether you are ready for the lab or should replay the walkthrough first.

Before you begin

Enter your name. It will appear on the score card so you can include it in your screenshot for the Lesson 30 reflection.

CS210 Lesson 30 · Linked List Deletion Self-Check

Six questions on the two-pointer splice, free ordering, and deletion edge cases. Pass at 70% or above; below that, take it again after reviewing.
How this works: One question per card. Pick or type your answer and click Submit. Feedback appears, then click Next to move on. Answers lock once submitted, so think before you submit. After all six, you get a score, a completion code, and a per-question recap.
6. After Class
  • Finish Lab 30 if you did not complete it in class. Submit through GitHub Classroom before Lesson 31.
  • Submit the Lesson 30 reflection in Blackboard: your widget completion codes and the short reflection prompt.
  • Replay the walkthrough in free mode. Delete the tail, then try to break it on purpose: free a node before splicing, or free the same node twice, and watch what the diagram does.
  • Read the Lesson 31 supplementary notes (stacks and queues built on linked lists) for next class.
  • Heads up: Quiz 9 at Lesson 31 covers Lessons 29 through 31 (linked lists, including deletion).
Need help? Schedule EI with your instructor. Bring your code, a screenshot of the walkthrough diagram at the point you got stuck, and the exact error message or valgrind output you do not understand. Specific questions get unstuck quickly.