Beyond the Single Direction

Singly Linked Lists are efficient but frustrating: you can’t look back. If you are at Node 5 and need something from Node 4, you have to start over from the Head.

Enter the Doubly Linked List (DLL).

1. Doubly Linked List

Each node now carries two pointers:

  1. Next: Points forward.
  2. Prev: Points backward.

Memory Trade-off

  • Singly: 4 bytes (int) + 8 bytes (next) = 12 bytes per node.
  • Doubly: 4 bytes (int) + 8 bytes (next) + 8 bytes (prev) = 20 bytes per node.
  • Cost: ~66% more memory overhead per node.
  • Benefit: O(1) deletion if you have the node (no need to search for the previous node).

Implementation

Java

class DoublyNode {
  int val;
  DoublyNode next;
  DoublyNode prev;

  public DoublyNode(int val) {
    this.val = val;
  }
}

Go

type DoublyNode struct {
  Val  int
  Next *DoublyNode
  Prev *DoublyNode
}

2. Interactive: DLL Navigator

Experience bidirectional traversal. Toggle “Circular Mode” to connect Tail to Head.

Node: 0
Start at Head.

3. Circular Linked Lists

A Circular Linked List is a list where the Tail points back to the Head instead of null.

Why?

  • Round Robin Scheduling: Operating Systems use this to cycle through running applications.
  • Music Playlists: “Repeat All” functionality.
  • Multiplayer Games: Turns pass from Player 1 → 2 → 3 → 1.

Implementation Tip

In a Circular List, you never reach null.

  • Danger: while(current ≠ null) will be an infinite loop.
  • Fix: do { ... } while (current ≠ head).

4. Deleting a Node (The DLL Superpower)

In a Singly Linked List, to delete Node B, you need a pointer to Node A (its predecessor). This requires scanning from the Head (O(N)).

In a Doubly Linked List, B knows about A via B.prev. We can delete B in O(1) if we have a reference to it.

// O(1) Deletion
node.prev.next = node.next;
node.next.prev = node.prev;

[!WARNING] Always check for null. If you delete the Head or Tail, prev or next might not exist.

In the next chapter, we will tackle the most common interview operations: Reversing and Merging.