Doubly & Circular Linked List

A singly linked list has two annoying limitations: you can only walk it forward, and deleting a node requires a separate scan just to find its predecessor. Two variations fix different parts of this: the doubly linked list adds a backward reference, and the circular linked list closes the chain into a loop. They solve different problems and are often combined (a doubly and circular list is a common real design, e.g. in LRU cache implementations).

Doubly Linked List: Node With prev and next

Each node now stores a reference to both neighbors. The extra prev pointer costs memory per node but unlocks two capabilities a singly linked list can't offer cheaply.

class DNode {
    int val;
    DNode prev;
    DNode next;

    DNode(int val) {
        this.val = val;
    }
}

Time complexity: O(1) to construct — fixed field assignment. Space complexity: O(1) per node, though it's roughly double a singly linked node's overhead (two reference fields instead of one).

O(1) Deletion Given a Node Reference

This is the headline benefit. In a singly linked list, deleting a node you already have a reference to still requires walking from the head to find its predecessor — O(n). In a doubly linked list, the node already knows its own predecessor, so deletion is a pure O(1) relink.

// Delete `node` directly -- no traversal needed, unlike a singly linked list.
public void deleteNode(DNode node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next; // node was the head
    }

    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev; // node was the tail
    }
}

Time complexity: O(1) — assuming you already hold a reference to the node (as is common when a hash map tracks node references, e.g. in an LRU cache), no traversal is needed at all. Space complexity: O(1) — only pointer reassignment, no new allocation.

Backward Traversal

public void printReverse() {
    DNode curr = tail;
    while (curr != null) {
        System.out.print(curr.val + " -> ");
        curr = curr.prev;
    }
    System.out.println("null");
}

Time complexity: O(n) — visits every node once, just in reverse order; a singly linked list cannot do this at all without either extra storage or re-scanning from the head repeatedly. Space complexity: O(1) — a single traversal pointer.

Circular Linked List

A circular linked list changes one thing: instead of the last node's next being null, it points back to the head, so the chain has no true "end." This is useful for anything that logically cycles — round-robin CPU scheduling is the standard example, where each process gets a time slice and control passes to "the next one," wrapping back to the first process after the last.

class CNode {
    int val;
    CNode next;
    CNode(int val) { this.val = val; }
}

// Insert a new node right after `tail`, then re-point tail.next back to head to keep the loop closed.
public void insert(int val) {
    CNode node = new CNode(val);
    if (head == null) {
        head = node;
        node.next = head; // single node points to itself
    } else {
        node.next = head;
        tail.next = node;
    }
    tail = node;
}

// Round-robin: advance to the next process, wrapping automatically since the list is circular.
public CNode nextTurn(CNode current) {
    return current.next; // never null -- always wraps around to head eventually
}

Time complexity: insert is O(1) with a maintained tail reference; nextTurn is O(1) — it's just following one pointer. Space complexity: O(1) per operation beyond the node itself; the structure holds O(n) total nodes.

Comparison: Singly vs Doubly vs Circular

Type	Extra cost	Gains	Pick it when
Singly linked	None — baseline	O(1) insert at head, simplest to implement	You only ever need forward traversal and head-insertion (e.g. a basic stack).
Doubly linked	One extra pointer per node	O(1) deletion given a node reference, backward traversal	You need to delete arbitrary nodes quickly (LRU cache) or walk in both directions (e.g. a text editor's cursor).
Circular (singly or doubly)	None extra beyond the base type; just a different last-link target	No special-casing "the end" — wrapping is automatic	The data is naturally cyclic: round-robin scheduling, a repeating playlist, a circular buffer.