Pointer Surgery

Last lesson's list could grow in exactly one place, the front, and die all at once. Real list work is editing: append at the end so input keeps its order, splice into the middle so a sorted list stays sorted, remove one node and close the gap behind it. Every operation in this lesson is one walk plus one or two pointer assignments, and each has a single detail that decides between a working list and a corrupted one: an assignment order, a missing-predecessor special case at the head, a free that must come last. Those details are the lesson.

Insertion at the Tail

To append, walk to the last node, the one whose next is NULL, and aim that next at the new node. The walk is not quite the canonical one: the loop condition is last->next != NULL, not last != NULL, because the walk must stop on the final node in order to modify it, where the canonical walk would step off the end and leave you holding NULL. And one list has no last node to stop on, the empty one, so head == NULL gets its own branch in which the new node simply becomes the list:

node->value = value;
node->next = NULL;              /* the new node is the new end */
if (head == NULL) {
    return node;                /* empty list: no last node to walk to */
}
last = head;
while (last->next != NULL) {    /* stop ON the last node, not past it */
    last = last->next;
}
last->next = node;
return head;

Who Updates head?

That return node; raises a question the whole lesson hangs on. Chapter 8 taught that parameters are copies: a function receiving struct Node *head can rewire nodes through it, but assigning to head itself changes only the copy, and the caller's list pointer never hears about it. Yet tail insertion into an empty list, head insertion, and deleting the first node all must change which node is first. C has two idioms for this: pass the head's address as a struct Node ** and write through it, or return the new head and have the caller assign it back. This course uses the return style: head = deleteValue(head, target); reads exactly like the return-and-assign calls you have written since chapter 8, and it postpones pointer-to-pointer machinery you do not need yet. It also gives allocation failure a clean signal, NULL, which can never be confused with a real result because a list that just gained a node is never empty; the caller catches the result in a temporary before overwriting head, precisely the realloc idiom from two lessons ago.

The Two-Assignment Splice

Inserting between two nodes needs the node before the insertion point, the predecessor, because the only pointer that must change lives inside it. The splice itself is two assignments whose order is everything:

       pred                          the rest
     +-----+----+                  +------+-----+
 ...>|  7  |  --+----------------->|  19  | ... |
     +-----+----+                  +------+-----+
                    +------+----+
              node  |  12  |  ? |
                    +------+----+

 step 1   node->next = pred->next;   /* 12 aims at 19 */
 step 2   pred->next = node;         /* 7 aims at 12 */

     +-----+----+   +------+----+   +------+-----+
 ...>|  7  |  --+-->|  12  |  --+-->|  19  | ... |
     +-----+----+   +------+----+   +------+-----+

Step 1 must run first because pred->next is, at that moment, the only pointer to the rest of the list. Reverse the order and pred->next = node destroys that pointer before anyone has copied it; the next line, node->next = pred->next, then reads back the updated field, which is node's own address. The new node points at itself, and every node from 19 onward is unreachable, lost, and leaked. Same two lines, opposite order, dead list.

Sorted Insertion

The splice's classic application is keeping a list in ascending order no matter what order values arrive in. Find the predecessor by walking while pred->next->value < value, guarded by pred->next != NULL so the walk can also stop at the tail; if the list is empty or the value belongs before the current first node, there is no predecessor and the job collapses to last lesson's head insertion. Watch an unsorted sequence come out ordered, one insertion per line:

42 -> NULL
7 -> 42 -> NULL
7 -> 19 -> 42 -> NULL
3 -> 7 -> 19 -> 42 -> NULL
3 -> 7 -> 19 -> 25 -> 42 -> NULL

Every path through the function is on display: 42 lands in an empty list, 7 and 3 belong before the head, 19 and 25 are spliced mid-list by the two assignments. Note the caller's shape, newHead = insertSorted(head, ...), check, then head = newHead: on failure the old head is still intact for freeList, exactly like catching realloc's result in a temporary.

Deletion by Value: Unlink First, Free Second

Deleting a node is the splice run backward, and it needs the predecessor for the same reason: the pointer that must change, the one aiming at the doomed node, lives in the node before it. So the search walks pred while pred->next->value != target, keeping the predecessor and the victim in view at once. Then two steps, in fixed order:

     +-----+----+   +--------+----+   +------+-----+
 ...>|  7  |  --+-->| doomed |  --+-->|  19  | ... |
     +-----+----+   +--------+----+   +------+-----+

 pred->next = doomed->next;    /* unlink: 7 bypasses doomed, aims at 19 */
 free(doomed);                 /* only after the list has let go */

The order is the freed-node rule: unlink first, free second, and never touch the node after free. The unlink reads doomed->next, and that read is only legal while the node is alive; after free(doomed) the bytes are not yours, and reading a pointer out of them is the use-after-free from two lessons back, undefined behaviour and an instant ASan abort here. The special case is the head, which has no predecessor: deleting it is head = head->next followed by freeing the old first node, and it is the reason deleteValue returns the new head:

10 -> 20 -> 30 -> NULL
10 -> 30 -> NULL
30 -> NULL
30 -> NULL

Deleting 20 is the ordinary case, predecessor found mid-list. Deleting 10 exercises the head branch, and the caller's head = deleteValue(head, 10) is what actually moves the list forward, the return-the-new-head convention earning its keep. Deleting 99 finds pred at the tail with pred->next == NULL and changes nothing, no crash, no special code.

Freeing the Whole List

freeList has now appeared in every program of this chapter, and it is worth seeing it as this lesson's deletion discipline applied wholesale: each iteration saves the successor while the node is alive, frees, then steps, which is unlink-before-free with the whole remainder of the list playing the part of doomed->next. One malloc per node in, exactly one free per node out, on the success path and on every failure path, and the chapter's leak checker holds you to it.

Key Takeaways

  • Tail insertion walks with last->next != NULL to stop on the last node, and the empty list is its special case: no last node exists, so the new node becomes the head.
  • Functions that may change which node is first return the new head and the caller assigns it back, head = deleteValue(head, target); — the course convention, matching return-and-assign and needing no pointer-to-pointer yet.
  • The splice is node->next = pred->next; then pred->next = node; in that order; reversed, the only pointer to the rest of the list is overwritten first, the new node ends up pointing at itself, and the tail is leaked.
  • Sorted insertion finds the predecessor with pred->next != NULL && pred->next->value < value, falling back to plain head insertion when the list is empty or the value belongs first.
  • Deletion needs the predecessor because the pointer to rewrite, pred->next, lives inside it; the head has no predecessor and is handled as head = head->next before freeing the old head.
  • Unlink first, free second, never touch after: pred->next = doomed->next; must read the doomed node while it is alive, because reading it after free is use-after-free, undefined behaviour.
  • Catch an inserting function's result in a temporary before overwriting head, the realloc idiom again, so allocation failure leaves the old list reachable and freeable.