Doubly Linked List

A singly linked list can only move forward: reaching the node before a given one means walking from HEAD all over again, since nothing points backward. A doubly linked list fixes this by giving every node a second pointer, back to the node before it, at the cost of one extra field per node.

Node structure

Reading the diagram: the top arrows point forward (NEXT), the bottom arrows point backward (PREV). HEAD's PREV is NULL, matching the last node's NEXT being NULL, the list is bounded on both ends.

In C, a node is written as:

struct node {
    struct node *prev;
    int data;
    struct node *next;
};

Insertion at the beginning

Inserting a new node before the current head means wiring both its NEXT (to the old head) and the old head's PREV (back to the new node).

INSERT_BEGIN(HEAD, ITEM)
 
1. Create NEW
2. NEW->data = ITEM
3. NEW->prev = NULL
4. NEW->next = HEAD
5. If HEAD != NULL
       HEAD->prev = NEW
6. HEAD = NEW
7. Return HEAD

Example 1: inserting into an empty list. Inserting 10 when HEAD == NULL. Step 5 skips the HEAD->prev = NEW line, since there's no existing head node to update, HEAD was NULL to begin with. The list becomes a single node, 10, with both PREV and NEXT set to NULL.

Example 2: inserting into a non-empty list. Inserting 5 at the beginning of 10 → 20. Before anything changes:

NEW is created and filled, not yet linked. Step 4 sets NEW->next = HEAD, and step 5 sets the old head's PREV back to NEW, wiring both directions before HEAD itself moves:

Step 6 moves HEAD onto NEW, and the list is 5 ⇄ 10 ⇄ 20:

Deletion of a node

This is the operation where a doubly linked list's second pointer pays off directly: since a node already knows the node before it, deleting it needs no separate walk from HEAD to find that predecessor, the way a singly linked list's delete-a-specific-node does.

DELETE_NODE(HEAD, PTR)
 
1. If PTR == NULL
       Return HEAD
2. If PTR->prev != NULL
       PTR->prev->next = PTR->next
   Else
       HEAD = PTR->next
3. If PTR->next != NULL
       PTR->next->prev = PTR->prev
4. free(PTR)
5. Return HEAD

Example 1: PTR is NULL. Deleting a node that wasn't found (PTR == NULL). Step 1 catches this immediately and returns the list unchanged.

Example 2: deleting the head node. Deleting the node holding 10 from 10 ⇄ 20 ⇄ 30 (PTR at that node, PTR->prev == NULL):

Step 2's Else branch fires, since PTR->prev is NULL: HEAD moves directly to PTR->next (the node holding 20). Step 3 then sets that node's PREV to PTR->prev, which is NULL, correctly making it the new head with no predecessor. After freeing PTR, the list is 20 ⇄ 30:

Example 3: deleting a middle node. Deleting the node holding 20 from 10 ⇄ 20 ⇄ 30 (PTR at that node):

Step 2's main branch fires: PTR->prev->next (the node holding 10's NEXT) is set to PTR->next (the node holding 30), skipping over PTR from the front. Step 3 sets PTR->next->prev (the node holding 30's PREV) back to PTR->prev (the node holding 10), skipping over PTR from the back too. Both directions are re-linked before PTR is freed, leaving 10 ⇄ 30:

Example 4: deleting the tail node. Deleting the node holding 30 from 10 ⇄ 20 ⇄ 30 (PTR at that node, PTR->next == NULL). Step 2 fires normally (PTR->prev->next = PTR->next, which is NULL), but step 3 is skipped, since PTR->next is already NULL, there's no node after PTR whose PREV needs updating. The list becomes 10 ⇄ 20, with the node holding 20 now correctly having NEXT == NULL.

Both directions have to be checked independently, PTR->prev for whether PTR is the head, PTR->next for whether PTR is the tail, since a doubly linked list can lose either neighbor without losing the other. Deleting a doubly linked list node is O(1) once PTR is known, exactly like a singly linked list, but doesn't need a separate PREV pointer walk to find the node before it, that pointer is already stored in the node itself.

Traversal in both directions

The entire reason for the extra PREV field: a doubly linked list can be walked backward as easily as forward.

TRAVERSE_FORWARD(HEAD)
 
1. PTR = HEAD
2. While PTR != NULL
       Print PTR->data
       PTR = PTR->next
3. Stop

TRAVERSE_BACKWARD(TAIL)
 
1. PTR = TAIL
2. While PTR != NULL
       Print PTR->data
       PTR = PTR->prev
3. Stop

Forward traversal needs HEAD; backward traversal needs a pointer to the last node, TAIL, since there's no way to reach the end of the list without walking there first otherwise. A program that needs frequent backward traversal typically keeps a TAIL pointer up to date alongside HEAD, the same way a linked-list queue keeps a REAR pointer instead of walking from the front every time.

Why the extra pointer is worth it

Quick recall

• Each node stores PREV, DATA, and NEXT; the head's PREV and the tail's NEXT are both NULL.
• Inserting or deleting a node means updating pointers on both sides, the node before and the node after, not just one, since links run in both directions.
• Deleting a known node is O(1) with no predecessor walk needed, since PTR->prev already points to it, unlike a singly linked list.
• Checking PTR->prev (is this the head?) and PTR->next (is this the tail?) independently handles all four insertion/deletion cases: beginning, end, middle, and empty list.
• Traversal works in both directions: forward from HEAD via NEXT, backward from TAIL via PREV, both O(n).