Beyond the Single Direction

[!NOTE] This module explores the core principles of Doubly & Circular Lists, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

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).

Each node now carries two pointers:

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

A Circular Linked List is a variation where the Tail points back to the Head instead of null, creating an infinite loop.

---

2. Interactive Analysis

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

Node: 0

Circular Mode

Start at Head.

---

3. Intuition

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).

The Superpower: O(1) Deletion

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.

---

4. Implementation

Java

Go

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

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

class DoublyLinkedList {
    DoublyNode head;
    DoublyNode tail;

    // Add to Head
    public void addFirst(int val) {
        DoublyNode newNode = new DoublyNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // Delete Node (O(1) given reference)
    public void remove(DoublyNode node) {
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next; // Removing head

        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev; // Removing tail
    }
}

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

type DoublyLinkedList struct {
    Head *DoublyNode
    Tail *DoublyNode
}

// Add to Head
func (dll *DoublyLinkedList) AddFirst(val int) {
    newNode := &DoublyNode{Val: val}
    if dll.Head == nil {
        dll.Head = newNode
        dll.Tail = newNode
    } else {
        newNode.Next = dll.Head
        dll.Head.Prev = newNode
        dll.Head = newNode
    }
}

// Delete Node (O(1) given reference)
func (dll *DoublyLinkedList) Remove(node *DoublyNode) {
    if node.Prev != nil {
        node.Prev.Next = node.Next
    } else {
        dll.Head = node.Next
    }

    if node.Next != nil {
        node.Next.Prev = node.Prev
    } else {
        dll.Tail = node.Prev
    }
}

---

5. Complexity Analysis

Operation	Time	Space	Notes
Search	O(N)	O(1)	Must scan. Can search from Head or Tail.
Insert (Head/Tail)	O(1)	O(1)	Pointer swaps only.
Delete (Given Node)	O(1)	O(1)	No traversal needed.
Delete (By Value)	O(N)	O(1)	Must search first.