List Insertion and Deletion in C — The Moveable Feast of Linked Lists

"If pointers are the secret handshake of C, inserting and deleting nodes is the part where you learn the dance steps — and occasionally step on memory's toes."

You're coming in hot from "Nodes and Pointers" (so I won't re-explain what a node is), and you've already wrestled with malloc, free, and pointer arithmetic in "Memory, Pointers, and File I/O." Perfect — now we combine those muscles and learn how to add and remove list elements safely, efficiently, and without leaking your dignity (or memory).

---

Why this matters (and where you'll see it)

• Linked lists are the classic dynamic data structure: flexible size, cheap insertions/deletions when you know the spot.
• Real-world uses: building stacks/queues, adjacency lists in graphs, undo histories, or any place where array resizing would be a pain.
• Practically: learning correct insertion/deletion teaches pointer manipulation, lifetime management (malloc/free), and defensive programming — all CS50 essentials.

---

Core operations we'll cover

1. Insert at head
2. Insert at tail
3. Insert after a given node (or by value)
4. Delete head
5. Delete a given node (by pointer or by value)
6. Delete the entire list (free everything)

We'll show canonical C implementations, then explain pitfalls, complexity, and debugging tips.

---

The basic node type (reminder)

typedef struct node {
    int value;
    struct node *next;
} node;

This is the same node you met earlier. Remember: nodes live on the heap (malloc) unless you intentionally make them local. That matters when you free.

---

1) Insert at head — the simplest magical trick

Why: O(1) time. No traversal. Great for stacks.

node *insert_head(node *head, int val) {
    node *n = malloc(sizeof(node));
    if (!n) return head; // malloc failed — leave list unchanged
    n->value = val;
    n->next = head;
    return n; // new head
}

Micro explanation: You create a new node, point it to the old head, and return the new node as head. No loops, no previous-pointer juggling.

---

2) Insert at tail — two common approaches

A) Simple: traverse to end (O(n)).

node *insert_tail(node *head, int val) {
    node *n = malloc(sizeof(node));
    if (!n) return head;
    n->value = val;
    n->next = NULL;
    if (!head) return n; // empty list -> new head

    node *cur = head;
    while (cur->next) cur = cur->next;
    cur->next = n;
    return head;
}

B) Efficient for repeated tails: keep a tail pointer alongside head (amortized O(1) append).

---

3) Insert after a given node (or keep list sorted)

Insert after a specific node pointer:

void insert_after(node *prev, int val) {
    if (!prev) return; // nothing to insert after
    node *n = malloc(sizeof(node));
    if (!n) return;
    n->value = val;
    n->next = prev->next;
    prev->next = n;
}

Insert in sorted order: traverse to find insertion spot and use the same link tweaks.

---

4) Delete head

node *delete_head(node *head) {
    if (!head) return NULL;
    node *next = head->next;
    free(head);
    return next; // new head
}

Micro explanation: Save the pointer to head->next, free the old head, then return the saved pointer as new head. Never access freed memory.

---

5) Delete a node by value (the classic gotcha)

We must keep track of previous node to re-link. Edge case: deleting head.

node *delete_value(node *head, int val) {
    if (!head) return NULL;
    // Special case: head contains value
    if (head->value == val) return delete_head(head);

    node *prev = head;
    node *cur = head->next;
    while (cur) {
        if (cur->value == val) {
            prev->next = cur->next;
            free(cur);
            return head; // head unchanged
        }
        prev = cur;
        cur = cur->next;
    }
    return head; // not found
}

Pro tip: using a pointer-to-pointer (node **) can simplify head handling and reduce duplication.

Pointer-to-pointer deletion example:

void delete_value_pp(node **headp, int val) {
    node **curp = headp;
    while (*curp) {
        node *cur = *curp;
        if (cur->value == val) {
            *curp = cur->next; // unlink
            free(cur);
            return;
        }
        curp = &cur->next;
    }
}

Why this rule is beautiful: it treats head exactly like any other next pointer. No special-case code.

---

6) Free the whole list

void free_list(node *head) {
    node *cur = head;
    while (cur) {
        node *next = cur->next;
        free(cur);
        cur = next;
    }
}

Always free every malloc'd node before your program exits (or before losing the last pointer to them).

---

Complexity & common bugs

• Time:
  • Insert at head: O(1)
  • Insert at tail (no tail pointer): O(n)
  • Search + insert/delete at arbitrary position: O(n)
• Space: each node uses sizeof(node)

Common bugs:

• Forgetting to set new_node->next (leads to garbage pointer)
• Using freed memory (dangling pointer)
• Double-freeing (freeing same node twice)
• Memory leaks (not freeing nodes)
• Not checking malloc result (NULL) on constrained systems

Debugging tools: valgrind (or LeakSanitizer), printing pointer values, and stepping through with a debugger.

---

Quick checklist before running your insertion/deletion code

• Do you handle empty list (head == NULL)?
• Do you update head when needed? (return new head or use node **)
• Do you set next pointers correctly before freeing?
• Do you free every node you allocate?
• Did you check malloc for NULL in realistic environments?

---

Key takeaways — the memorable ones

• Insertion/deletion = pointer surgery. If you tie the wrong knot, the list unravels.
• Use insert at head for O(1) simplicity.
• Use pointer-to-pointer to avoid annoying head special cases.
• Always call free for nodes you created with malloc — valgrind will judge you otherwise.

"If you can picture the pointers in your head, you're 80% there. The rest is careful coding and, occasionally, pleading with your debugger."

---

If you want, I can:

• Show an integrated example program (main) that builds a list, inserts/deletes, and prints results.
• Convert examples to work with strings (remember strdup and free!).
• Walk through a valgrind output and show what an actual leak looks like.

Tags: beginner, C, linked-lists, humorous, computer-science