Mental Model

A doubly linked list lets you move forward and backward easily, unlike a singly linked list which only moves forward.

Analogy: Think of a train with cars connected both ways so you can walk forward or backward between cars, versus a train where you can only walk forward.

Singly Linked List:
head -> [1] -> [2] -> [3] -> null

Doubly Linked List:
null ← [1] ↔ [2] ↔ [3] -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, delete node 2

Goal: Show how deleting a middle node is easier with a doubly linked list than with a singly linked list

Step 1: In singly linked list, find node before 2 (node 1) to delete node 2

head -> [1] -> [2] -> [3] -> null

Why: We need the previous node to change its next pointer to skip node 2

Step 2: Change node 1's next pointer to node 3, skipping node 2

head -> [1] -> [3] -> null

Why: This removes node 2 from the chain

Step 3: In doubly linked list, directly access node 2 and update pointers

null ← [1] ↔ [2] ↔ [3] -> null

Why: Node 2 has pointers to both previous and next nodes

Step 4: Set node 1's next to node 3 and node 3's prev to node 1, removing node 2

null ← [1] ↔ [3] -> null

Why: Both forward and backward links are updated easily without traversal

Result:

Singly Linked List after deletion:
head -> [1] -> [3] -> null

Doubly Linked List after deletion:
null ← [1] ↔ [3] -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Singly linked list node
typedef struct SNode {
    int data;
    struct SNode* next;
} SNode;

// Doubly linked list node
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

// Create singly linked list 1->2->3
SNode* create_singly_list() {
    SNode* head = malloc(sizeof(SNode));
    head->data = 1;
    head->next = malloc(sizeof(SNode));
    head->next->data = 2;
    head->next->next = malloc(sizeof(SNode));
    head->next->next->data = 3;
    head->next->next->next = NULL;
    return head;
}

// Create doubly linked list 1<->2<->3
DNode* create_doubly_list() {
    DNode* n1 = malloc(sizeof(DNode));
    DNode* n2 = malloc(sizeof(DNode));
    DNode* n3 = malloc(sizeof(DNode));
    n1->data = 1; n1->prev = NULL; n1->next = n2;
    n2->data = 2; n2->prev = n1; n2->next = n3;
    n3->data = 3; n3->prev = n2; n3->next = NULL;
    return n1;
}

// Delete node with value 2 from singly linked list
void delete_singly(SNode** head_ref, int val) {
    SNode* curr = *head_ref;
    SNode* prev = NULL;
    while (curr && curr->data != val) {
        prev = curr; // move prev forward
        curr = curr->next; // move curr forward
    }
    if (!curr) return; // not found
    if (!prev) { // deleting head
        *head_ref = curr->next;
    } else {
        prev->next = curr->next; // bypass curr
    }
    free(curr);
}

// Delete node with value 2 from doubly linked list
void delete_doubly(DNode** head_ref, int val) {
    DNode* curr = *head_ref;
    while (curr && curr->data != val) {
        curr = curr->next; // move curr forward
    }
    if (!curr) return; // not found
    if (curr->prev) {
        curr->prev->next = curr->next; // link prev to next
    } else {
        *head_ref = curr->next; // deleting head
    }
    if (curr->next) {
        curr->next->prev = curr->prev; // link next to prev
    }
    free(curr);
}

// Print singly linked list
void print_singly(SNode* head) {
    SNode* curr = head;
    while (curr) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

// Print doubly linked list
void print_doubly(DNode* head) {
    DNode* curr = head;
    while (curr) {
        printf("%d", curr->data);
        if (curr->next) printf(" <-> ");
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // Singly linked list test
    SNode* s_head = create_singly_list();
    printf("Singly Linked List before deletion:\n");
    print_singly(s_head);
    delete_singly(&s_head, 2);
    printf("Singly Linked List after deleting 2:\n");
    print_singly(s_head);

    // Doubly linked list test
    DNode* d_head = create_doubly_list();
    printf("Doubly Linked List before deletion:\n");
    print_doubly(d_head);
    delete_doubly(&d_head, 2);
    printf("Doubly Linked List after deleting 2:\n");
    print_doubly(d_head);

    return 0;
}

while (curr && curr->data != val) {
        prev = curr; // move prev forward
        curr = curr->next; // move curr forward
    }

Traverse singly list to find node to delete and keep track of previous node

if (!prev) { // deleting head
        *head_ref = curr->next;
    } else {
        prev->next = curr->next; // bypass curr
    }

Update previous node's next pointer to skip the deleted node

while (curr && curr->data != val) {
        curr = curr->next; // move curr forward
    }

Traverse doubly list to find node to delete

if (curr->prev) {
        curr->prev->next = curr->next; // link prev to next
    } else {
        *head_ref = curr->next; // deleting head
    }
    if (curr->next) {
        curr->next->prev = curr->prev; // link next to prev
    }

Update both previous and next nodes to bypass the deleted node

OutputSuccess

Singly Linked List before deletion: 1 -> 2 -> 3 -> null Singly Linked List after deleting 2: 1 -> 3 -> null Doubly Linked List before deletion: 1 <-> 2 <-> 3 Doubly Linked List after deleting 2: 1 <-> 3

Complexity Analysis

Time: O(n) because we may need to traverse the list to find the node to delete

Space: O(1) because deletion uses constant extra space

vs Alternative: Doubly linked list allows backward pointer updates without extra traversal, making some operations like deletion easier compared to singly linked list which requires tracking previous node

Edge Cases

Deleting head node

Head pointer is updated to next node correctly

DSA C

if (!prev) { // deleting head
        *head_ref = curr->next;

Deleting tail node

Next pointer of previous node is set to null; doubly list updates prev pointer of next node if exists

DSA C

if (curr->next) {
        curr->next->prev = curr->prev;

Deleting node not found

Function returns without changes

DSA C

if (!curr) return; // not found

When to Use This Pattern

When you need to delete or insert nodes easily from both ends or in the middle without traversing from head, reach for doubly linked list because it has backward pointers.

Common Mistakes

Mistake: In singly linked list deletion, forgetting to track the previous node causes loss of list links.
Fix: Always keep a pointer to the previous node while traversing to update its next pointer.

Mistake: In doubly linked list deletion, forgetting to update both prev and next pointers breaks the list.
Fix: Update both previous node's next and next node's prev pointers to maintain list integrity.

Summary

Doubly linked list allows easy movement and updates in both directions.

Use it when you need efficient backward traversal or easy deletion of nodes without extra traversal.

The key insight is that having pointers both ways removes the need to find previous nodes during operations.