07 The Doubly Linked List with Double Sentinels

1. The Concept & Purpose

What is it? A Doubly Linked List that has two dummy nodes: 1. Head Sentinel: Guards the front. 2. Tail Sentinel: Guards the back.

Visual Model (The Sandwich):

[Head Dummy] \(\leftrightarrow\) [Data A] \(\leftrightarrow\) [Data B] \(\leftrightarrow\) [Tail Dummy]

Why introduce it? (The Logic) In a standard Doubly Linked List, you still have to check for NULL at the boundaries. * Standard: If I delete the last node, I must update tail. If I insert into an empty list, I must update head AND tail. * With Double Sentinels: * The list is never empty (it always has at least the two sentinels). * Every data node is guaranteed to have a non-NULL prev and a non-NULL next. * Result: We eliminate ALL boundary checks (if head == NULL, if tail == NULL). One generic logic handles insertion/deletion anywhere.

---

2. Modifications Required

A. Initialization (createList)

We must allocate two nodes immediately and link them together.

typedef struct DList {
    DNode* head; // Points to Head Dummy
    DNode* tail; // Points to Tail Dummy
} DList;

DList* createList() {
    DList* list = (DList*)malloc(sizeof(DList));

    // 1. Create the two sentinels
    list->head = (DNode*)malloc(sizeof(DNode));
    list->tail = (DNode*)malloc(sizeof(DNode));

    // 2. Link them to each other (The Empty State)
    list->head->next = list->tail; // Head points to Tail
    list->tail->prev = list->head; // Tail points to Head

    // 3. Seal the outer boundaries
    list->head->prev = NULL;
    list->tail->next = NULL;

    return list;
}

B. The "Universal" Insertion (insertBetween)

Instead of writing separate logic for pushFront and pushBack, we write one private helper function. * Logic: Insert a node between any two existing nodes A and B.

// Private Helper: Inserts 'val' between node 'before' and node 'after'
void _insertBetween(DNode* before, DNode* after, int val) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = val;

    // The 4-Pointer Update (Standard Double Link Logic)
    newNode->prev = before;
    newNode->next = after;
    before->next = newNode;
    after->prev = newNode;
}

// Public Wrappers are now trivial:
void pushFront(DList* list, int val) {
    // Insert between HeadDummy and the first actual node
    _insertBetween(list->head, list->head->next, val);
}

void pushBack(DList* list, int val) {
    // Insert between the last actual node and TailDummy
    _insertBetween(list->tail->prev, list->tail, val);
}

C. The "Universal" Deletion (removeNode)

Similarly, deleting a node never requires checking if it is the first or last node.

void removeNode(DNode* target) {
    // We don't need to check if target->prev is NULL, 
    // because Sentinels guarantee neighbors exist.
    DNode* before = target->prev;
    DNode* after = target->next;

    before->next = after;
    after->prev = before;

    free(target);
}

D. Traversal (The Loop Condition)

• Change: We start after the Head Sentinel and stop before the Tail Sentinel.

void printList(DList* list) {
    // Start at the first real data node
    DNode* curr = list->head->next;

    // Stop when we hit the Tail Sentinel (NOT NULL)
    while (curr != list->tail) {
        printf("%d <-> ", curr->data);
        curr = curr->next;
    }
    printf("END\n");
}

---

3. Summary of the Evolution

Version	Main Pain Point	Solution
No Sentinel	head variable changes; strict NULL checks.	Use Node** or if/else.
Single Sentinel	Modifying index 0 is special.	Add Head Dummy.
Tail Pointer	Inserting at the end is \(O(N)\).	Add Tail Variable.
Double Sentinel	Inserting at the end still requires if(tail==NULL) logic.	Add Tail Dummy.

Verdict: The Doubly Linked List with Double Sentinels requires slightly more memory (2 extra nodes) but provides the cleanest, most bug-resistant code for complex applications.