Doubly Linked List

References in both directions

In a doubly linked list, a node stores two links: next goes forward, while prev goes backward. Therefore, given a reference to a particular node, we can immediately reach both of its neighbors.

class Node {
    int value;
    Node prev;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

The convenience costs one additional reference per node and more careful structural updates: when inserting or removing, we usually have to keep both directions consistent.

Removing a known node

If we already have a reference to the node being removed, its neighbors can be connected directly. For an internal node, the operation does not require searching for the previous element.

if (node.prev != null) {
    node.prev.next = node.next;
}

if (node.next != null) {
    node.next.prev = node.prev;
}

The number of assignments is constant, so removing a known node itself takes O(1). The list boundaries still require attention, however: removing the head or tail also requires updating the external head or tail reference.

When a doubly linked structure helps

A doubly linked structure is useful when an algorithm needs to move in both directions, remove already located nodes quickly, or maintain access to both ends of a list. If backward movement is unnecessary, the extra prev reference may be unnecessary overhead.