Doubly Linked Lists (CS50) — Insertions, Deletions, and Safe Memory

If you remember the chaos of singly linked lists, think of doubly linked lists as giving each node a tiny steering wheel — now they can go forward and back. Much more control. Slightly more responsibility.

You already know nodes, pointers, and how memory works from "Linked Lists: Nodes and Pointers" and the low-level tricks from "Memory, Pointers, and File I/O." We won't re-teach what a pointer is; instead we'll stack on that knowledge and show how adding a prev pointer changes insertion, deletion, traversal, and memory safety.

---

What is a doubly linked list (brief)?

• A doubly linked list is like a singly linked list but each node has two pointers: next (to the following node) and prev (to the previous node).
• This enables O(1) insertion or deletion when you already have a pointer to the node to modify, and easy backward traversal.

Why care? Real-world uses:

• Implementing undo/redo stacks
• Browser history (go back and forth)
• Some LRU cache implementations

---

The node structure in C

Here's the canonical node you learned to assemble, upgraded with prev:

typedef struct node {
    int value;
    struct node *prev; // pointer to previous node
    struct node *next; // pointer to next node
} node;

node *create_node(int v) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return NULL; // always check!
    n->value = v;
    n->prev = NULL;
    n->next = NULL;
    return n;
}

Note: allocation and NULL checks are the same responsibilities you practiced in CS50's memory exercises.

---

Traversal: forward and backward

Forward traversal (like singly linked):

for (node *cur = head; cur != NULL; cur = cur->next) {
    printf("%d ", cur->value);
}

Backward traversal requires a tail pointer or walking to the end first:

// assuming tail points to last node
for (node *cur = tail; cur != NULL; cur = cur->prev) {
    printf("%d ", cur->value);
}

Tip: maintain both head and tail pointers for O(1) access to both ends.

---

Insertion patterns (the juicy part)

Because nodes know their neighbors, insertion logic splits neatly into cases.

1) Insert at head

• Old head's prev must point to new node.
• New node's next should point to old head.
• Update head pointer.

void insert_head(node **head, node **tail, node *n) {
    if (n == NULL) return;
    n->next = *head;
    n->prev = NULL;
    if (*head != NULL) (*head)->prev = n;
    *head = n;
    if (*tail == NULL) *tail = n; // list was empty
}

2) Insert at tail (O(1) if tail known)

void insert_tail(node **head, node **tail, node *n) {
    if (n == NULL) return;
    n->next = NULL;
    n->prev = *tail;
    if (*tail != NULL) (*tail)->next = n;
    *tail = n;
    if (*head == NULL) *head = n; // list was empty
}

3) Insert after a given node (constant time)

void insert_after(node *pos, node *n) {
    if (pos == NULL || n == NULL) return;
    n->prev = pos;
    n->next = pos->next;
    if (pos->next != NULL) pos->next->prev = n;
    pos->next = n;
}

This is the magical O(1) operation people rave about: you don't need to walk the list if you already have pos.

---

Deletion: free safely and avoid dangling pointers

Deleting a node must reconnect neighbors and free memory.

void delete_node(node **head, node **tail, node *to_delete) {
    if (to_delete == NULL) return;

    if (to_delete->prev != NULL)
        to_delete->prev->next = to_delete->next;
    else
        *head = to_delete->next; // was head

    if (to_delete->next != NULL)
        to_delete->next->prev = to_delete->prev;
    else
        *tail = to_delete->prev; // was tail

    free(to_delete);
    // Do not try to use to_delete after free; set external pointers to NULL if needed
}

Common pitfalls:

• Forgetting to update head or tail when deleting ends — leads to broken list.
• Using a pointer after freeing it (dangling pointer). After freeing, never dereference the node.
• Double-free: free only once per allocation.

---

Memory safety checklist (builds on "Memory, Pointers, and File I/O")

• Always check malloc's return value.
• After free(ptr), if you still hold the variable, set it to NULL to avoid accidental reuse.
• Avoid double-free by ensuring ownership: the function that frees must know nobody else will free it.
• When manipulating neighbors, update them before freeing the node.

"This is the moment where the concept finally clicks: updating two neighbors is just bookkeeping — but skipping one line is catastrophic."

---

Singly vs Doubly — quick comparison

Feature	Singly Linked List	Doubly Linked List
Memory per node	smaller (1 pointer)	larger (2 pointers)
Backward traversal	O(n) (must walk from head)	O(1) (via prev/tail)
Delete given node (if you have only head)	O(n) to find prev	O(1) if you have pointer to node
Implementation complexity	simpler	slightly more bookkeeping

So doubly linked lists cost more memory but give you flexibility and faster operations when you need bidirectional navigation.

---

Complexity summary

• Insert/delete at head/tail: O(1)
• Insert/delete after known node: O(1)
• Searching for a value: O(n)
• Traversal forward/backward: O(n)

Why engineers obsess: the right list type is a tradeoff between memory and needed operations. If you need back-and-forth or cheap removal given a node, doubly linked is your friend.

---

Quick debugging prompts (when things break)

• Is head or tail NULL unexpectedly? Maybe you forgot to update it when deleting/inserting.
• Are neighbor pointers set before freeing? Check order of operations.
• Do you have a stray pointer that still points to freed memory? Use tools like Valgrind (or sanitize with AddressSanitizer) to find leaks and invalid accesses.

Imagine your list as a conga line. If someone leaves without whispering to their left and right neighbors, you get chaos. Your job in C: be that whisper.

---

Key takeaways

• Doubly linked lists add a prev pointer to each node — small cost, big flexibility.
• Insert/delete near a known node is O(1); maintain head and tail for best performance.
• Mind your memory: allocate carefully, update neighbors before freeing, and avoid dangling pointers.

Final memory-hack: whenever you're changing pointers, imagine the sequence of pointer updates and write them down in comments — it's cheap and saves debugging hours.

Tags: CS50, linked lists, pointers, memory safety