Operations on Doubly Linked List

A doubly linked list stores, in every node, a value plus two pointers — next and prev — so any node can reach both its neighbors in O(1) without re-walking the list; this second pointer is the entire reason DLL operations differ from singly linked list operations: every insert/delete must keep both links consistent on both sides of the edit, in exchange for being able to delete a given node, walk backward, or search from whichever end is closer.

Recognize the pattern

• Problem needs O(1) deletion given only a node reference (no re-scan for the predecessor) — e.g. LRU cache eviction, browser history back/forward.
• Problem needs traversal in both directions from an arbitrary point, or wants to reach an index from whichever end is closer.
• You see phrases like "remove this node", "insert before X", "undo/redo", "most-recently-used" — these all lean on the prev pointer that a singly linked list lacks.

Brute force vs optimal

Brute force (as if singly linked): to delete node target, walk from head to find its predecessor — O(n) time, O(1) space, even though you already hold a reference to target.

Optimal (using prev): read target.prev directly — O(1) time, O(1) space. The DLL trades one extra reference per node (4 bytes with HotSpot compressed oops, 8 without — subject to 8-byte alignment rounding) for turning an O(n) predecessor lookup into an O(1) pointer read.

Complexity from first principles

• Traversal (forward or reverse): each of the n nodes is visited exactly once, one pointer hop and one "process" step per node → n hops ⇒ O(n) time. Only a single current reference is held ⇒ O(1) space.
• Insert/Delete at head or tail: a fixed number of pointer reassignments (≤4), independent of n ⇒ O(1) time, O(1) space.
• Insert/Delete at position k (or given only an index): on a singly linked list you can only walk from head, so reaching index k costs O(k). A DLL can walk from either end — from head if k is small, from tail if k is close to n − 1 — so the real achievable bound is O(min(k, n − k)) time, worst case O(n) when k ≈ n/2; the edit itself is O(1) pointer rewrites once the node is found ⇒ total O(min(k, n − k)) time, O(1) space. This bidirectional-walk trick has no equivalent on a singly linked list.
• Insert/Delete given a node reference (the DLL's advantage): 0 hops needed, just rewire neighbors ⇒ O(1) time, O(1) space — this is impossible in O(1) on a singly linked list because you cannot find prev without scanning.

Worked example: delete node with value 30

List: 10 <-> 20 <-> 30 <-> 40, and we already hold a reference target to the node holding 30.

Result: 10 <-> 20 <-> 40. Zero traversal — 4 pointer writes total (2 to bridge the neighbors, 2 to isolate the removed node), because we started from the node itself instead of scanning for it.

Java implementation

class DNode {
    int val;
    DNode prev, next;
    DNode(int val) { this.val = val; }
}

class DoublyLinkedList {
    DNode head, tail;

    // O(1): 2 reassignments (head, and head.prev if list was non-empty)
    void insertAtHead(int val) {
        DNode n = new DNode(val);
        n.next = head;
        if (head != null) head.prev = n;
        head = n;
        if (tail == null) tail = n;
    }

    // O(1): mirror of insertAtHead, using tail instead
    void insertAtTail(int val) {
        DNode n = new DNode(val);
        n.prev = tail;
        if (tail != null) tail.next = n;
        tail = n;
        if (head == null) head = n;
    }

    // O(1): caller already holds the node reference
    void deleteNode(DNode target) {
        if (target.prev != null) target.prev.next = target.next;
        else head = target.next;
        if (target.next != null) target.next.prev = target.prev;
        else tail = target.prev;
        target.next = null;
        target.prev = null;
    }

    // O(1): delegates to deleteNode once the reference is known
    void deleteAtHead() {
        if (head != null) deleteNode(head);
    }

    void deleteAtTail() {
        if (tail != null) deleteNode(tail);
    }

    // O(1) once you hold anchor: rewires 4 pointers, no traversal
    void insertBefore(DNode anchor, int val) {
        DNode n = new DNode(val);
        DNode p = anchor.prev;
        n.prev = p;
        n.next = anchor;
        anchor.prev = n;
        if (p != null) p.next = n; else head = n;
    }

    void printForward() {
        for (DNode c = head; c != null; c = c.next) System.out.print(c.val + " ");
    }
}

All of these reuse the same two moves as the worked example above: snapshot the neighbors, then rewrite pointers on both sides — insertAtTail, deleteAtHead/deleteAtTail, and insertBefore (the mirror insertAfter just swaps prev/next roles) are all O(1) once the anchor node is known, confirming the head/tail row of the complexity table without needing separate proofs.

Pitfalls

• Updating next before capturing the old next/prev reference — always snapshot both neighbors first, then rewrite.
• Forgetting to check null when the target is the head or tail (no prev or no next to fix).
• Leaving dangling next/prev on the removed node — causes memory leaks in GC'd languages if other references keep it alive, and silent corruption in manual-memory languages. Note this is two separate writes (next = null and prev = null), not one.
• Forgetting to update the separate tail pointer on end deletions/insertions.
• Walking from head for every index-based operation even when index > n/2 — wastes the O(min(k, n−k)) traversal that a DLL's tail pointer makes possible.

When to use / when not — DLL vs singly linked list vs array

Don't reach for a DLL just for backward traversal if you never delete/insert mid-list from a held reference — the extra pointer and bookkeeping isn't worth it. A neat payoff when you do have both ends: palindrome check is Θ(n) time / Θ(1) space with two pointers meeting from head and tail, while a singly list must reverse half the list or stack values (often Θ(n) extra space) to compare.

Takeaways

• The prev pointer converts node deletion/insertion-given-a-reference from O(n) to O(1) — that's the whole value proposition.
• Index-based operations are O(min(k, n−k)), not plain O(k): a DLL can start the walk from whichever end is closer, a trick a singly linked list cannot do; only the rewiring step itself is O(1).
• Every edit fixes up to 4 pointers (prev.next, next.prev, target's own next and prev) — the worked example above traces exactly these 4 writes — always null-check head/tail edge cases.

Recall: Why can a doubly linked list delete a given node in O(1) while a singly linked list generally cannot, and why does index-based access improve from O(k) to O(min(k, n−k))?

Compiled from standard DSA references (GeeksforGeeks, CLRS-style linked list treatments) and verified against hand-traced pointer manipulation.