Doubly Linked Lists - Learning Module

Loading content...

0/279

Previous and Next Pointers — The Mechanics of Bidirectional Links

The Two Arrows That Change Everything

In the previous page, we established the structure of doubly linked lists—nodes with dual pointers creating a bidirectional chain. Now we must understand the mechanics: how these pointers actually work, how to manipulate them safely, and how to reason about operations that involve multiple pointer updates.

This is where the rubber meets the road. Pointer manipulation is the core skill of working with linked structures. Master it, and you can implement any linked data structure. Fumble it, and you'll spend hours debugging mysterious crashes and corrupted data.

The good news: pointer manipulation follows predictable patterns. Once you internalize these patterns, operations that seemed complex become routine.

What You Will Learn

By the end of this page, you will understand exactly how prev and next pointers encode relationships between nodes, how to safely update pointers during insertions and deletions, and how to think systematically about pointer manipulation to avoid common bugs. You'll develop the mental discipline that separates reliable implementations from fragile ones.

What Pointers Actually Store

Before diving into manipulation techniques, let's be precise about what prev and next pointers actually contain. This foundational understanding prevents many conceptual errors.

A Pointer is an Address:

At the hardware level, a pointer is simply a memory address—a number that tells the processor where to find another piece of data in memory. When we write node.next = otherNode, we're storing the memory address of otherNode inside the next field of node.

The Abstract View:

In higher-level languages, we don't work with raw memory addresses. Instead, we work with references—abstract handles that the runtime manages for us. But conceptually, the model is the same: a pointer/reference tells us where to find another object.

null vs Valid Pointer:

A pointer can hold either:

A valid address pointing to an existing node
A special value (null, nil, None, nullptr) indicating "points to nothing"

This distinction is critical. Attempting to follow a null pointer (dereferencing null) crashes your program or throws an exception. Every pointer operation must account for the possibility of null.

Null Pointer Dereferencing

The single most common error in linked list implementations is failing to check for null before following a pointer. Always ask: 'Could this pointer be null?' If yes, handle that case explicitly before dereferencing.

pointer-concepts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// What a pointer stores: a reference to another object (or null)
 
class Node<T> {
    data: T;
    next: Node<T> | null;  // Either points to a Node, or is null
    prev: Node<T> | null;  // Either points to a Node, or is null
    
    constructor(data: T) {
        this.data = data;
        this.next = null;  // Initially points to nothing
        this.prev = null;  // Initially points to nothing
    }
}
 
// Creating nodes - at this point, all pointers are null
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");
 
// Now let's establish the relationships:
// We want: null ← A ↔ B ↔ C → null
 
// Step 1: Link node1 to node2 (forward direction)
node1.next = node2;  // node1's next now "points to" node2
 
// Step 2: Link node2 back to node1 (backward direction)
node2.prev = node1;  // node2's prev now "points to" node1
 
// Step 3: Link node2 to node3 (forward)
node2.next = node3;
 
// Step 4: Link node3 back to node2 (backward)
node3.prev = node2;
 
// Now we can traverse:
// Forward:  node1 → node1.next (node2) → node2.next (node3) → node3.next (null)
// Backward: node3 → node3.prev (node2) → node2.prev (node1) → node1.prev (null)
 
// IMPORTANT: Following a null pointer crashes!
// This is WRONG: node3.next.data  // node3.next is null!
// Must check first:
if (node3.next !== null) {
    console.log(node3.next.data);  // Safe - we know next is not null
}

The Bidirectional Relationship

The defining characteristic of doubly linked lists is that every link between adjacent nodes is represented by two pointers that must be kept in sync. This bidirectional consistency is the most critical invariant.

The Fundamental Rule:

For any two adjacent nodes A and B where A comes before B:

A.next must equal B
B.prev must equal A

If either of these is true without the other, the list is corrupted.

Why Both Pointers Are Necessary:

You might wonder: if A.next points to B, can't we just follow links to infer relationships without B.prev? In theory, yes—but at O(n) cost. The power of doubly linked lists comes from the fact that each node independently knows its predecessor, enabling O(1) backward navigation and O(1) deletion.

Think of It as a Contract

When node A's next points to node B, think of this as establishing a contract: 'I (A) am directly before B in the sequence.' For this contract to be valid, node B must acknowledge it by having its prev point back to A. A one-sided contract is a broken data structure.

bidirectional-validation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Validates that the bidirectional invariant holds throughout the list.
 * This is a debugging/testing utility - not for production use.
 */
function validateDoublyLinkedList<T>(head: Node<T> | null): boolean {
    if (head === null) {
        return true; // Empty list is valid
    }
    
    // Head's prev should be null
    if (head.prev !== null) {
        console.error("Corruption: head.prev is not null");
        return false;
    }
    
    let current = head;
    let count = 0;
    const maxIterations = 100000; // Prevent infinite loops from corrupted lists
    
    while (current !== null && count < maxIterations) {
        // If there's a next node, verify the back-link
        if (current.next !== null) {
            if (current.next.prev !== current) {
                console.error(`Corruption at node ${count}: next.prev doesn't point back`);
                console.error(`  current: ${current.data}`);
                console.error(`  current.next: ${current.next.data}`);
                console.error(`  current.next.prev: ${current.next.prev?.data ?? 'null'}`);
                return false;
            }
        }
        
        current = current.next;
        count++;
    }
    
    if (count >= maxIterations) {
        console.error("Corruption: possible cycle detected (too many iterations)");
        return false;
    }
    
    return true;
}
 
// Example usage:
const valid = validateDoublyLinkedList(node1);
console.log(`List is ${valid ? 'valid' : 'corrupted'}`);

Visualizing the Invariant:

CORRECT: Both directions agree
         ┌───────────────┐
         │               ▼
    ┌────┴────┐    ┌──────────┐
    │ Node A  │    │  Node B  │
    │ next: B │───►│ prev: A  │
    └─────────┘    └──────────┘
                         │
         ▲               │
         └───────────────┘


BROKEN: One direction disagrees
    ┌─────────┐    ┌──────────┐
    │ Node A  │    │  Node B  │
    │ next: B │───►│ prev: X  │  ← Points to wrong node!
    └─────────┘    └──────────┘

When you modify a linked list, you must always update both pointers to maintain this invariant. This is non-negotiable.

The Order of Pointer Updates

When inserting or deleting nodes, you must update multiple pointers. The order in which you perform these updates matters enormously—get it wrong, and you lose access to nodes you still need to update.

The Cardinal Rule:

Never overwrite a pointer that you'll need to follow later. Always ensure you have a reference to any node you'll need before modifying pointers that provide access to it.

Safe vs Dangerous Ordering:

Dangerous: Losing References

•Updating A.next before saving a reference to the old A.next
•Updating head pointer before the new head's prev is set
•Deleting a node before its neighbors are reconnected
•Modifying prev/next before you've read all needed values

Safe: Preserving References

•Save references to all nodes you'll need in local variables
•Set up the new node's pointers before modifying existing nodes
•Update existing nodes' pointers in a safe order
•Update list-level pointers (head/tail) last

insertion-order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Insert a new node after a given node.
 * Demonstrates the correct order of pointer updates.
 */
function insertAfter<T>(existingNode: Node<T>, newNode: Node<T>): void {
    // STEP 1: Save reference to the node that will come after newNode
    // We must do this BEFORE modifying existingNode.next!
    const successor = existingNode.next;
    
    // STEP 2: Set up the new node's pointers
    // The new node goes between existingNode and successor
    newNode.prev = existingNode;
    newNode.next = successor;
    
    // STEP 3: Update existingNode to point to newNode
    existingNode.next = newNode;
    
    // STEP 4: Update successor's prev to point to newNode (if successor exists)
    if (successor !== null) {
        successor.prev = newNode;
    }
}
 
/**
 * WRONG ORDER - This would cause data loss!
 */
function insertAfterWRONG<T>(existingNode: Node<T>, newNode: Node<T>): void {
    // DANGER: We modify existingNode.next BEFORE saving the reference!
    existingNode.next = newNode;  // We just lost the reference to the old next!
    
    // Now we can't access the successor to update its prev pointer.
    // The list is broken - we've orphaned all nodes after existingNode.
    
    // This line would fail because we no longer have access to successor:
    // successor.prev = newNode;  // What is successor? We lost it!
}

The 'SPSS' Mnemonic

For insertion operations, remember: Save, Point-new, Point-existing, Succeesor. Save references first, set up the new node's pointers second, update existing nodes third, update successor's back-link last.

Pointer Manipulation: Insertion Patterns

Let's examine all the common insertion scenarios and the precise pointer updates each requires. Understanding these patterns deeply allows you to implement any insertion variant correctly.

Insertion at Head (Empty List): This is the simplest case—the new node becomes both head and tail.

insert-head-empty
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Insert into an empty list.
 * Before: head = null, tail = null
 * After:  head = newNode, tail = newNode
 *         newNode.prev = null, newNode.next = null
 */
function insertIntoEmpty<T>(list: DoublyLinkedList<T>, newNode: Node<T>): void {
    // The new node is the only node, so no prev or next
    newNode.prev = null;
    newNode.next = null;
    
    // It's both head and tail
    list.head = newNode;
    list.tail = newNode;
    list.size = 1;
}

Insertion at Head (Non-Empty List):

insert-head-nonempty
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Insert at the head of a non-empty list.
 * Before: head → [Old Head] ↔ ... ↔ [Tail]
 * After:  head → [New Node] ↔ [Old Head] ↔ ... ↔ [Tail]
 */
function insertAtHead<T>(list: DoublyLinkedList<T>, newNode: Node<T>): void {
    const oldHead = list.head!; // We know list is non-empty
    
    // Set up new node's pointers
    newNode.prev = null;        // New head has no predecessor
    newNode.next = oldHead;     // New head's next is the old head
    
    // Update old head to point back to new node
    oldHead.prev = newNode;
    
    // Update list's head pointer
    list.head = newNode;
    list.size++;
    
    // Note: tail is unchanged
}

Insertion at Tail (Non-Empty List):

insert-tail-nonempty
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Insert at the tail of a non-empty list.
 * Before: head → ... ↔ [Old Tail] ← tail
 * After:  head → ... ↔ [Old Tail] ↔ [New Node] ← tail
 */
function insertAtTail<T>(list: DoublyLinkedList<T>, newNode: Node<T>): void {
    const oldTail = list.tail!; // We know list is non-empty
    
    // Set up new node's pointers
    newNode.prev = oldTail;     // New tail's prev is the old tail
    newNode.next = null;        // New tail has no successor
    
    // Update old tail to point forward to new node
    oldTail.next = newNode;
    
    // Update list's tail pointer
    list.tail = newNode;
    list.size++;
    
    // Note: head is unchanged
}

Insertion in Middle (Between Two Nodes):

insert-middle
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Insert between two existing nodes.
 * Before: ... ↔ [Predecessor] ↔ [Successor] ↔ ...
 * After:  ... ↔ [Predecessor] ↔ [New Node] ↔ [Successor] ↔ ...
 * 
 * Four pointers must be updated!
 */
function insertBetween<T>(
    newNode: Node<T>, 
    predecessor: Node<T>, 
    successor: Node<T>,
    list: DoublyLinkedList<T>
): void {
    // Set up new node's pointers (2 updates)
    newNode.prev = predecessor;
    newNode.next = successor;
    
    // Update existing nodes (2 updates)
    predecessor.next = newNode;
    successor.prev = newNode;
    
    list.size++;
    
    // Note: head and tail are unchanged for middle insertions
}

Count the Pointer Updates

For a middle insertion, exactly 4 pointers change: newNode.prev, newNode.next, predecessor.next, successor.prev. For head insertion, 3 pointers change. For tail insertion, 3 pointers change. Counting expected updates helps verify your implementation.

Pointer Manipulation: Deletion Patterns

Deletion in a doubly linked list is remarkably elegant compared to singly linked lists. Because each node knows its predecessor, you can delete any node given just a reference to that node—no need to traverse from the head.

The Power of Self-Sufficient Deletion:

In a singly linked list, to delete node B, you need access to node A (B's predecessor) to update A.next. Finding A requires O(n) traversal from head.

In a doubly linked list, node B already contains a reference to A via B.prev. Deletion is always O(1).

delete-middle
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Delete a node from the middle of the list.
 * Before: ... ↔ [Predecessor] ↔ [Node to Delete] ↔ [Successor] ↔ ...
 * After:  ... ↔ [Predecessor] ↔ [Successor] ↔ ...
 * 
 * The deleted node is "bypassed" - its neighbors now point to each other.
 */
function deleteMiddleNode<T>(nodeToDelete: Node<T>, list: DoublyLinkedList<T>): void {
    // Get references to neighbors
    const predecessor = nodeToDelete.prev!;  // We know it exists (not head)
    const successor = nodeToDelete.next!;     // We know it exists (not tail)
    
    // Bypass the deleted node
    predecessor.next = successor;
    successor.prev = predecessor;
    
    // Clean up the deleted node (optional but good practice)
    nodeToDelete.prev = null;
    nodeToDelete.next = null;
    
    list.size--;
}

Deletion at Head:

delete-head
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Delete the head node.
 * Before: head → [Node to Delete] ↔ [New Head] ↔ ...
 * After:  head → [New Head] ↔ ...
 */
function deleteHead<T>(list: DoublyLinkedList<T>): Node<T> | null {
    if (list.head === null) {
        return null; // Empty list
    }
    
    const nodeToDelete = list.head;
    
    if (list.head === list.tail) {
        // Only one node - list becomes empty
        list.head = null;
        list.tail = null;
    } else {
        // Multiple nodes - update head
        const newHead = nodeToDelete.next!;
        newHead.prev = null;  // New head has no predecessor
        list.head = newHead;
    }
    
    // Clean up deleted node
    nodeToDelete.prev = null;
    nodeToDelete.next = null;
    
    list.size--;
    return nodeToDelete;
}

Deletion at Tail:

delete-tail
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Delete the tail node.
 * Before: ... ↔ [New Tail] ↔ [Node to Delete] ← tail
 * After:  ... ↔ [New Tail] ← tail
 */
function deleteTail<T>(list: DoublyLinkedList<T>): Node<T> | null {
    if (list.tail === null) {
        return null; // Empty list
    }
    
    const nodeToDelete = list.tail;
    
    if (list.head === list.tail) {
        // Only one node - list becomes empty
        list.head = null;
        list.tail = null;
    } else {
        // Multiple nodes - update tail
        const newTail = nodeToDelete.prev!;
        newTail.next = null;  // New tail has no successor
        list.tail = newTail;
    }
    
    // Clean up deleted node
    nodeToDelete.prev = null;
    nodeToDelete.next = null;
    
    list.size--;
    return nodeToDelete;
}

General Deletion (Handles All Cases):

delete-general
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Delete any node from the list.
 * Handles all cases: head, tail, middle, only node.
 */
function deleteNode<T>(node: Node<T>, list: DoublyLinkedList<T>): void {
    // Handle predecessor link
    if (node.prev !== null) {
        node.prev.next = node.next;  // Predecessor skips over node
    } else {
        // Node was the head - update head
        list.head = node.next;
    }
    
    // Handle successor link
    if (node.next !== null) {
        node.next.prev = node.prev;  // Successor skips over node
    } else {
        // Node was the tail - update tail
        list.tail = node.prev;
    }
    
    // Clean up deleted node
    node.prev = null;
    node.next = null;
    
    list.size--;
}

The Universal Delete Pattern

The general delete function works for all cases by checking for null at each step. This is more robust than writing separate functions for head/tail/middle deletion. In production code, prefer this unified approach—fewer code paths mean fewer bugs.

Traversal Mechanics: Walking Both Directions

The primary benefit of doubly linked lists is effortless bidirectional traversal. Both directions work identically—the only difference is which pointer you follow.

Forward Traversal: Start at head, follow next pointers until you reach null.

traversal-forward
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Forward traversal: head → tail
 */
function traverseForward<T>(list: DoublyLinkedList<T>): T[] {
    const result: T[] = [];
    let current = list.head;
    
    while (current !== null) {
        result.push(current.data);
        current = current.next;  // Follow the next pointer
    }
    
    return result;
}
 
// For list: A ↔ B ↔ C ↔ D
// Returns: ["A", "B", "C", "D"]

Backward Traversal: Start at tail, follow prev pointers until you reach null.

traversal-backward
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Backward traversal: tail → head
 */
function traverseBackward<T>(list: DoublyLinkedList<T>): T[] {
    const result: T[] = [];
    let current = list.tail;
    
    while (current !== null) {
        result.push(current.data);
        current = current.prev;  // Follow the prev pointer
    }
    
    return result;
}
 
// For list: A ↔ B ↔ C ↔ D
// Returns: ["D", "C", "B", "A"]

Cursor-Based Navigation:

One powerful pattern is maintaining a "cursor" that can move in either direction. This is exactly how text editors implement navigation.

cursor-navigation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * A cursor that can navigate a doubly linked list in either direction.
 * This pattern is fundamental to text editors, music players, and more.
 */
class ListCursor<T> {
    private current: Node<T> | null;
    private list: DoublyLinkedList<T>;
    
    constructor(list: DoublyLinkedList<T>) {
        this.list = list;
        this.current = list.head;  // Start at the beginning
    }
    
    /** Move cursor forward. Returns false if already at end. */
    moveNext(): boolean {
        if (this.current === null || this.current.next === null) {
            return false;
        }
        this.current = this.current.next;
        return true;
    }
    
    /** Move cursor backward. Returns false if already at beginning. */
    movePrev(): boolean {
        if (this.current === null || this.current.prev === null) {
            return false;
        }
        this.current = this.current.prev;
        return true;
    }
    
    /** Move to head of list */
    moveToStart(): void {
        this.current = this.list.head;
    }
    
    /** Move to tail of list */
    moveToEnd(): void {
        this.current = this.list.tail;
    }
    
    /** Get data at current position */
    getData(): T | null {
        return this.current?.data ?? null;
    }
    
    /** Check if cursor has a next element */
    hasNext(): boolean {
        return this.current !== null && this.current.next !== null;
    }
    
    /** Check if cursor has a previous element */
    hasPrev(): boolean {
        return this.current !== null && this.current.prev !== null;
    }
}
 
// Usage example - simulating arrow key navigation
const cursor = new ListCursor(list);
console.log(cursor.getData());  // First element
 
cursor.moveNext();
cursor.moveNext();
console.log(cursor.getData());  // Third element
 
cursor.movePrev();
console.log(cursor.getData());  // Back to second element

Common Pointer Bugs and How to Avoid Them

Even experienced developers make pointer manipulation mistakes. Let's examine the most common bugs and develop strategies to prevent them.

The Hall of Pointer Bugs

•Forgetting One Direction: Updating next but not prev (or vice versa). The list appears to work for forward traversal but fails on backward traversal.
•Lost Reference: Overwriting a pointer before saving the old value. You lose access to nodes you still need to update.
•Null Pointer Dereference: Following a pointer without checking if it's null first. Crashes at runtime.
•Dangling Update: Updating a pointer to a node that's been deleted. Creates references to freed memory.
•Off-by-One in Head/Tail: Updating the list's head or tail pointer incorrectly after insertion or deletion at endpoints.
•Self-Reference Loop: Accidentally setting node.next = node or node.prev = node. Creates infinite loops.

bug-examples
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// BUG 1: Forgetting the backward link
function insertAfterBUGGY<T>(node: Node<T>, newNode: Node<T>): void {
    newNode.next = node.next;
    newNode.prev = node;
    node.next = newNode;
    // MISSING: if (newNode.next !== null) newNode.next.prev = newNode;
    // Forward traversal works, backward traversal is broken!
}
 
// BUG 2: Lost reference
function insertBeforeBUGGY<T>(node: Node<T>, newNode: Node<T>): void {
    node.prev = newNode;  // OOPS! We just lost reference to the old prev!
    // newNode.prev = ???  // Can't access it anymore
}
 
// BUG 3: Null pointer dereference
function deleteBUGGY<T>(node: Node<T>): void {
    node.prev.next = node.next;  // Crashes if node is head (prev is null)!
    node.next.prev = node.prev;  // Crashes if node is tail (next is null)!
}
 
// CORRECT: Always check for null
function deleteCorrect<T>(node: Node<T>): void {
    if (node.prev !== null) {
        node.prev.next = node.next;
    }
    if (node.next !== null) {
        node.next.prev = node.prev;
    }
}

Defensive Programming Strategy

Before every pointer operation, ask three questions: (1) Could this pointer be null? (2) After this update, will all invariants still hold? (3) Do I have all the references I'll need for subsequent updates? If you can answer yes, yes, and yes, proceed confidently.

Summary: Mastering Bidirectional Pointers

We've covered the mechanics of prev and next pointers in depth. These are the foundational skills for all doubly linked list operations.

Key Takeaways

•Pointers store addresses: Each pointer holds a reference to another node (or null for end markers).
•Bidirectional invariant: For adjacent nodes A and B, A.next = B requires B.prev = A. Always maintain both.
•Order matters: Save references before modifying pointers. Set up new nodes before updating existing ones.
•Insertion requires 2-4 pointer updates: Depending on position (head, tail, or middle).
•Deletion is O(1): Because nodes know their predecessors, deletion only needs the node reference.
•Traversal is symmetric: Forward (follow next) and backward (follow prev) are identical patterns.
•Check for null: Every pointer access must account for the null case.

What's Next:

Now that you understand how to manipulate pointers, we'll explore the advantages this enables: bidirectional traversal and simplified deletion. You'll see how these capabilities make doubly linked lists the right choice for specific problem domains.

Page Complete

You now understand the mechanics of prev and next pointers—what they store, how to update them safely, and how to avoid common bugs. This knowledge is the foundation for implementing any doubly linked list operation correctly.