Linked ListsLesson 3

Doubly Linked Lists

Each node now has two pointers — next and previous. Learn the structure and why bidirectional traversal is useful.

What Is It?

A doubly linked list is like a singly linked list, but each node has an extra pointer going the other way.

In a singly linked list, each node only knows who comes next. In a doubly linked list, each node knows both who comes next AND who came before.

So each node holds three things:

  1. The value
  2. A next pointer — points to the next node
  3. A prev pointer — points to the previous node

Because you can go in both directions, the list also keeps track of both ends:

  • head — the first node
  • tail — the last node
Doubly Linked List— Each node has both prev and next pointers
10
20
30
40
head
tail

Bidirectional links allow traversal in both directions. Head.prev and tail.next are null.

The head's prev is null (nothing comes before it). The tail's next is null (nothing comes after it).

Analogy

Imagine a train where each car is connected to both the car in front and the car behind. In a singly linked list, the couplings only go one direction — you can walk from the engine toward the caboose, but not back. In a doubly linked list, you can walk freely in both directions because every car is coupled to its neighbors on both sides.

The engine is the head, the caboose is the tail. If you are standing at any car, you can immediately step forward (next) or backward (prev) without having to go back to the engine and start over.

How It Works

The Node Structure

pseudocode
1
2
3
4
structure DNode:
    data    // the value stored
    prev    // pointer to previous node (or null)
    next    // pointer to next node (or null)

The only difference from a singly linked list node is the extra prev pointer. That small addition makes a big difference.

The List Structure

pseudocode
1
2
3
4
structure DoublyLinkedList:
    head = null
    tail = null
    size = 0

Having both head and tail means we can reach either end of the list instantly — O(1).

Building a Doubly Linked List by Hand

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Create nodes
nodeA = new DNode(10)
nodeB = new DNode(20)
nodeC = new DNode(30)
​
// Wire forward links
nodeA.next = nodeB
nodeB.next = nodeC
​
// Wire backward links
nodeB.prev = nodeA
nodeC.prev = nodeB
​
// Set list pointers
head = nodeA    // first node
tail = nodeC    // last node

The resulting structure:

After Wiring All Pointers— Forward and backward links form a complete chain
10
20
30
head
tail

Every forward link has a matching backward link. This invariant must always hold.

Notice the symmetry: every forward link has a matching backward link. This must always be true — if it breaks, the list is broken.

Why the Prev Pointer Matters

1. Delete a node in O(1) when you have a reference to it.

In a singly linked list, to delete a node, you first need to find the node before it (which takes O(n) to walk there). In a doubly linked list, the node already knows its previous neighbor via prev. You can delete in O(1):

pseudocode
1
2
3
4
// Delete nodeB from:  A <-> B <-> C
nodeB.prev.next = nodeB.next    // A.next = C
nodeB.next.prev = nodeB.prev    // C.prev = A
// Result: A <-> C

This is the single biggest advantage of doubly linked lists.

2. Walk backward.

pseudocode
1
2
3
4
5
function traverseBackward(tail):
    current = tail
    while current is not null:
        process(current.data)
        current = current.prev

With a singly linked list, going backward is a major hassle. With a doubly linked list, it is just as easy as going forward.

3. O(1) insert and delete at both ends.

With both head and tail pointers, adding or removing from either end is instant. This makes doubly linked lists perfect for use cases like browser history or undo/redo.

The Pointer Rule

For any two neighboring nodes A and B in a doubly linked list, this must always be true:

pseudocode
1
A.next = B   AND   B.prev = A

Every insert and delete you write must maintain this. If you update one side and forget the other, the list is broken.

Traversal in Both Directions

pseudocode
1
2
3
4
5
6
7
8
9
10
11
function traverseForward(head):
    current = head
    while current is not null:
        process(current.data)
        current = current.next
​
function traverseBackward(tail):
    current = tail
    while current is not null:
        process(current.data)
        current = current.prev

Both are O(n), but going backward is something a singly linked list simply cannot do.

When to Use Doubly vs. Singly

ScenarioChoose
Simple stack (LIFO)Singly
Simple forward-only traversalSingly
Need to delete nodes with a direct referenceDoubly
Browser history (back and forward)Doubly
LRU cacheDoubly
Insert/remove at both endsDoubly
Memory is very constrainedSingly
Text editor cursor movementDoubly

The simple rule: use singly when you only move forward, doubly when you need to go both ways or want O(1) delete.

Examples

Example 1: Forward and Backward Print

pseudocode
1
2
3
4
List: null <- [1] <-> [2] <-> [3] -> null
​
Forward:  1, 2, 3
Backward: 3, 2, 1

Example 2: O(1) Node Deletion

Suppose you have a direct reference to the node containing 20:

pseudocode
1
2
3
4
5
6
7
Before: null <- [10] <-> [20] <-> [30] -> null
​
node = reference to [20]
node.prev.next = node.next    // [10].next = [30]
node.next.prev = node.prev    // [30].prev = [10]
​
After: null <- [10] <-> [30] -> null

No walking required — two pointer updates and it is done.

Example 3: Checking If a List Is a Palindrome

With a doubly linked list, you can compare from both ends at once:

pseudocode
1
2
3
4
5
6
7
8
9
function isPalindrome(list):
    left = list.head
    right = list.tail
    while left is not right and left.prev is not right:
        if left.data is not equal to right.data:
            return false
        left = left.next
        right = right.prev
    return true

Common Mistakes

1. Updating only one direction. The most common bug. If you update A.next = C but forget C.prev = A, forward traversal will look fine but backward traversal will be wrong. Always update both sides.

2. Not updating head and tail. When inserting at the front, update head. When inserting at the back, update tail. When deleting the only node, set both to null.

3. Null pointer crashes at boundaries. When deleting the head node, node.prev is null — you cannot call node.prev.next. Always check for null before accessing neighbors.

4. Assuming O(1) delete always applies. O(1) delete only works when you already have a reference to the node. If you only know the value, you still need O(n) to find the node first.

Best Practices

Update both pointers every time. Every insert and delete touches four pointers minimum. Make it a habit to ask: "did I update both the forward AND backward links?"

Always update head and tail. Keep a mental checklist — if you touch the first node, check if head needs updating. If you touch the last node, check if tail needs updating.

Test insertion and deletion at all positions: front, middle, back, and on a single-element list. Boundary bugs are the most common source of errors.

Draw it before you code it. Sketch the before and after state with arrows in both directions. This makes the required pointer changes obvious and prevents mistakes.

Runnable Code

Here is a complete JavaScript implementation you can run. It covers creating a doubly linked list, appending, prepending, deleting, and traversing in both directions.

js
Doubly Linked List — Full Implementation
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class DNode {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}
​
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
​
  // Add to the end
  append(data) {
    const node = new DNode(data);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
​
  // Add to the beginning
  prepend(data) {
    const node = new DNode(data);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.size++;
  }
​
  // Delete first occurrence of value
  delete(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) {
        if (current.prev) current.prev.next = current.next;
        else this.head = current.next;
        if (current.next) current.next.prev = current.prev;
        else this.tail = current.prev;
        this.size--;
        return;
      }
      current = current.next;
    }
  }
​
  // Traverse head to tail
  traverseForward() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.data);
      current = current.next;
    }
    console.log('Forward:  ' + values.join(' <-> '));
  }
​
  // Traverse tail to head
  traverseBackward() {
    let current = this.tail;
    const values = [];
    while (current) {
      values.push(current.data);
      current = current.prev;
    }
    console.log('Backward: ' + values.join(' <-> '));
  }
}
​
// --- Demo ---
const dll = new DoublyLinkedList();
​
dll.append(10);
dll.append(20);
dll.append(30);
console.log('After append 10, 20, 30:');
dll.traverseForward();
dll.traverseBackward();
​
dll.prepend(5);
console.log('\nAfter prepend 5:');
dll.traverseForward();
dll.traverseBackward();
​
dll.delete(20);
console.log('\nAfter delete 20:');
dll.traverseForward();
dll.traverseBackward();
console.log('Size:', dll.size);
Singly Linked List OperationsDoubly Linked List Operations