☕ DSA Java Articles

Topics › Linked List › Learn Doubly LinkedList

Introduction to Doubly LL

Easy TUF ID 1234 A2Z

Java source ↗ Edit this article ↗

What this covers

A singly linked list lets you move forward and nowhere else. Many operations suffer from that: deleting a node you already hold a reference to requires finding its predecessor, which means a scan from the head; walking backwards is impossible without reversing or using a stack. A doubly linked list (DLL) fixes both by giving every node a second reference, prev, that points at the node before it. The price is one extra reference per node and twice as many links to keep consistent on every edit.

This article introduces the two-link node, builds a DLL from an array, traverses it in both directions, defines the invariant that makes a DLL “well formed”, and shows the two operations that justify the extra link: inserting after a node and deleting a node, both in O(1) with no scan. It closes with a comparison against the singly linked version.

The node

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

A node holds a value and two references. prev is null for the first node and next is null for the last. A one-node list has both set to null, and the empty list is, as always, a null head. The three-argument constructor builds a node that is already wired to both neighbours, which keeps insertion code short.

The defining property of a DLL is a mirror invariant: whenever a.next == b, it must also hold that b.prev == a. Every edit changes links in pairs to preserve it; forgetting one half of a pair is the characteristic DLL bug, and it is invisible when you only traverse forward.

Building a list from an array

The construction is the singly linked one with one extra assignment per node. A mover stays on the current last node; each new node is attached after it, and the new node’s prev is pointed back at the mover.

static Node arrayToDLL(int[] arr) {
    if (arr.length == 0) return null;
    Node head = new Node(arr[0]);
    Node mover = head;                                 // always the current last node
    for (int i = 1; i < arr.length; i++) {
        Node temp = new Node(arr[i]);
        mover.next = temp;                             // forward link
        temp.prev = mover;                             // backward link, the one a singly list does not have
        mover = temp;
    }
    return head;
}

O(n) time, O(n) space for the n nodes. The head’s prev is never assigned, so it stays null, as the invariant requires. The last node’s next likewise stays null.

Traversal in both directions

Forward traversal is identical to the singly linked case. Two passes are needed to fill a Java array, one to count and one to copy.

static int[] toArrayForward(Node head) {
    int n = 0;
    for (Node t = head; t != null; t = t.next) n++;
    int[] out = new int[n];
    int i = 0;
    for (Node t = head; t != null; t = t.next) out[i++] = t.val;
    return out;
}

Backward traversal is the new ability. Given only the head, we first walk to the tail (remembering the last non-null node), then follow prev back to the start. If a tail reference were maintained alongside the head, the first walk would disappear.

static int[] toArrayBackward(Node head) {
    int n = 0;
    Node tail = null;
    for (Node t = head; t != null; t = t.next) { n++; tail = t; }
    int[] out = new int[n];
    int i = 0;
    for (Node t = tail; t != null; t = t.prev) out[i++] = t.val;
    return out;
}

The backward array is the forward array reversed, and the test file checks exactly that on every input. This is a cheap and powerful consistency test: if any prev link is wrong, the backward walk either skips nodes, visits them in the wrong order, or stops early, and the comparison fails.

A rendering helper makes examples readable. 1 <-> 2 <-> 3 is drawn with null on both ends, which reminds you that both the head’s prev and the tail’s next are null.

static String render(Node head) {
    if (head == null) return "null";
    StringBuilder sb = new StringBuilder("null <- ");
    for (Node t = head; t != null; t = t.next) {
        sb.append(t.val);
        sb.append(t.next != null ? " <-> " : " -> null");
    }
    return sb.toString();
}

Checking the invariant

Because the mirror invariant is so easy to break, it is worth having a function that verifies it. A list is well formed when the head has no predecessor and every forward link is matched by the corresponding backward link.

static boolean isWellFormed(Node head) {
    if (head == null) return true;
    if (head.prev != null) return false;
    for (Node t = head; t != null; t = t.next) {
        if (t.next != null && t.next.prev != t) return false;
    }
    return true;
}

The test file deliberately builds a broken two-node list by setting next without prev, confirms isWellFormed reports it, repairs the link and confirms it passes. Keep a helper like this in your own tests whenever you write DLL code; it catches the half-updated links that forward-only checks miss.

O(1) local edits

The reason to pay for prev is that edits around a node you already hold become constant time. To insert after node, create the new node with prev = node and next = node.next, tell the old successor (if any) to look back at the new node, and finally point node.next at it. Four links change instead of one, but there is still no scan.

static void insertAfter(Node node, int val) {
    Node fresh = new Node(val, node, node.next);       // prev = node, next = node's old successor
    if (node.next != null) node.next.prev = fresh;     // the old successor now looks back at fresh
    node.next = fresh;
}

The order matters: node.next.prev must be updated before node.next is overwritten, otherwise the old successor is no longer reachable from node. Building fresh first with the constructor sidesteps most ordering mistakes, because fresh captures node.next before anything is changed.

Deletion is where a singly linked list truly struggles. Given only a reference to target, a singly list needs the predecessor, and the only way to find it is a walk from the head. With prev the predecessor is one field read away. The two neighbours are made to bypass target in both directions; if target has no predecessor it was the head, so the successor becomes the new head.

static Node deleteNode(Node head, Node target) {
    if (target == null) return head;
    if (target.prev != null) target.prev.next = target.next;    // bypass target going forward
    else head = target.next;                                    // target was the head
    if (target.next != null) target.next.prev = target.prev;    // bypass target going backward
    target.prev = null;
    target.next = null;
    return head;
}

The method returns the possibly new head, so the caller writes head = deleteNode(head, target);. Clearing target’s own links is good hygiene: a deleted node that still points into the list is a trap for anyone who later follows it. Both edits are O(1) time and O(1) space, and the tests run them at the head, in the middle and at the tail, checking forward order, backward order and isWellFormed after each.

Singly versus doubly

  Singly linked Doubly linked
Links per node 1 2
Walk backwards no yes, via prev
Delete a node given only its reference O(n), must find the predecessor O(1)
Insert before a node given only its reference O(n) O(1)
Delete the tail O(n) O(n) to reach it, O(1) with a tail reference
Links to update per edit 1 2 to 4
Memory per node value plus one reference value plus two references

Doubly linked lists are what java.util.LinkedList uses, and they are the backbone of LRU caches, where “move this node to the front” and “evict the last node” must both be O(1). When you only ever traverse forward and edit at the head, the singly linked version is simpler and smaller.

Edge cases and pitfalls