Linked Lists

Ten pieces building a linked list completely by hand — the node struct, all the basic operations, and the pointer-manipulation tricks that come up constantly once the list itself is second nature.

struct node {
    int data;
    struct node *next;
};

void insert_head(struct node **head, int val) {
    struct node *n = malloc(sizeof(struct node));
    n->data = val;
    n->next = *head;
    *head = n;
}

insert_head needs struct node **head, not struct node *head — exactly the double-pointer pattern from 1.2.E, because the function has to change what the caller's head variable points to, not just read it.

Reversing a list in place

struct node *reverse(struct node *head) {
    struct node *prev = NULL;
    while (head != NULL) {
        struct node *next = head->next;  /* save before overwriting */
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;   /* the new head */
}

Finding the middle and detecting a cycle

Both use the same fast/slow pointer trick: one pointer advances one node per step, the other advances two. When the fast pointer reaches the end, the slow one is sitting at the middle. If the list has a cycle instead, the fast pointer eventually laps the slow one and they meet — which is impossible on a list that actually terminates in NULL. Free-all and search are the straightforward ones: walk next until NULL, doing the work (or freeing the node) at each step.