Skip to content

06 The Doubly Linked List

1. The Concept & Purpose

What is it? A list where every node has two pointers: 1. next: Points forward. 2. prev: Points backward.

Why introduce it? (The Logic) 1. Bidirectional Traversal: You can iterate from Head to Tail OR Tail to Head. 2. The "Self-Deletion" Power: This is the massive advantage. In a Singly list, to delete node X, you need a pointer to the node before X. In a Doubly list, if you hold X, you can delete it immediately because X knows who is before it (X->prev). * Complexity: Deletion becomes \(O(1)\) (assuming you already have the pointer to the target).

2. Modifications Required

A. Struct Definition

typedef struct DNode {
    int data;
    struct DNode* prev; // New Pointer
    struct DNode* next;
} DNode;

B. Insertion (The "Four-Step Dance")

  • Change: When inserting a node New between A and B, you must update four pointers, not two. Order is critical to avoid losing connections.
// Insert 'newNode' after 'A'
void insertAfter(DNode* A, DNode* newNode) {
    DNode* B = A->next; // B is the node originally after A

    // 1. Link NewNode to neighbors
    newNode->prev = A;
    newNode->next = B;

    // 2. Link neighbors to NewNode
    A->next = newNode;
    if (B != NULL) { // Check required unless using Double Sentinels
        B->prev = newNode; 
    }
}

C. Deletion (deleteNode)

  • Change: We no longer need the "Look-Ahead" (p->next) strategy. We can look directly at the target.
// Delete node 'p' directly
void deleteNode(DNode* p) {
    DNode* before = p->prev;
    DNode* after = p->next;

    // Bypass 'p'
    if (before != NULL) before->next = after;
    if (after != NULL)  after->prev = before;

    free(p);
}

3. Unique Precautions (Gotchas)

  1. Memory Overhead: Each node requires extra memory (4 or 8 bytes) for the prev pointer. On embedded systems, this adds up.
  2. Maintenance Complexity:
    • In a Singly list, forgetting to update a pointer might break the list.
    • In a Doubly list, forgetting to update a prev pointer might create a subtle bug where traversing forward works fine, but traversing backward crashes or goes to the wrong place.
  3. The "Double Sentinel" Recommendation:
    • To avoid checking if (B != NULL) or if (before != NULL) constantly, Doubly Linked Lists are best implemented with Two Sentinels: a HeadDummy and a TailDummy. This ensures every data node always has a valid prev and next.