Doubly linked lists

Each node of a doubly linked list has two references: next to its successor and prev to its predecessor. Following next then prev returns to the same node. Every structural change must update both directions, and forgetting one leaves the list corrupt: forward traversal works but backward traversal does not.

The solid arrows in the diagram are next pointers and the dashed ones are prev pointers.

1class DNode {
2    int val;
3    DNode prev, next;
4    DNode(int val) { this.val = val; }
5}

1class DNode { int val; DNode prev, next; }
2// head and tail are sentinels: head.next == tail when the list is empty, so no null checks are needed
3static void insertAfter(DNode a, int v) {                  // O(1) once you hold node a
4    DNode n = new DNode(); n.val = v; DNode b = a.next;
5    n.prev = a; n.next = b;                                // point the new node at both neighbours first
6    a.next = n; b.prev = n;                                // then make both neighbours point at it
7}
8static void remove(DNode n) {                              // O(1): the node knows both neighbours
9    n.prev.next = n.next;
10    n.next.prev = n.prev;
11}

Given a node a, inserting after it takes four pointer writes: set the new node's prev and next first, then make a.next and the old successor's prev point at it. Removing a node needs two: n.prev.next = n.next and n.next.prev = n.prev. No search for the previous node is needed, so both are O(1) once you hold the node, which is the main advantage over a singly linked list.

Step through insert and remove in the animation; each pointer write is one frame.

1static void insertAfter(DNode a, int v) {
2    DNode n = new DNode(v), b = a.next;
3    n.prev = a; n.next = b;        // point the new node at both neighbours
4    a.next = n; b.prev = n;        // then make both neighbours point back
5}
6static void remove(DNode n) {
7    n.prev.next = n.next;
8    n.next.prev = n.prev;
9}

1class DNode { int val; DNode prev, next; }
2// head and tail are sentinels: head.next == tail when the list is empty, so no null checks are needed
3static void insertAfter(DNode a, int v) {                  // O(1) once you hold node a
4    DNode n = new DNode(); n.val = v; DNode b = a.next;
5    n.prev = a; n.next = b;                                // point the new node at both neighbours first
6    a.next = n; b.prev = n;                                // then make both neighbours point at it
7}
8static void remove(DNode n) {                              // O(1): the node knows both neighbours
9    n.prev.next = n.next;
10    n.next.prev = n.prev;
11}

Sentinel (dummy) nodes at both ends hold no data and are never removed, so every real node always has a non-null prev and next. Insert and remove then need no special cases for the first or last element, and an empty list is just head.next == tail. The cost is two extra nodes.

H and T in the animation are the sentinels.

1class DList {
2    private final DNode head = new DNode(0), tail = new DNode(0);
3    private int size;
4    DList() { head.next = tail; tail.prev = head; }
5    void addFirst(int v) { insertAfter(head, v); size++; }
6    void addLast(int v) { insertAfter(tail.prev, v); size++; }
7    boolean isEmpty() { return head.next == tail; }
8}

1class DNode { int val; DNode prev, next; }
2// head and tail are sentinels: head.next == tail when the list is empty, so no null checks are needed
3static void insertAfter(DNode a, int v) {                  // O(1) once you hold node a
4    DNode n = new DNode(); n.val = v; DNode b = a.next;
5    n.prev = a; n.next = b;                                // point the new node at both neighbours first
6    a.next = n; b.prev = n;                                // then make both neighbours point at it
7}
8static void remove(DNode n) {                              // O(1): the node knows both neighbours
9    n.prev.next = n.next;
10    n.next.prev = n.prev;
11}

A doubly linked list can be walked forward from the head or backward from the tail, and a node can be found from either end: pick the nearer one when the index is known. java.util.LinkedList does this, so get(i) costs O(min(i, n - i)) instead of O(i). Backward traversal also makes tail deletion O(1).

Remember to stop at the sentinels, not at null.

1static void printBackward(DNode head, DNode tail) {
2    StringBuilder sb = new StringBuilder();
3    for (DNode cur = tail.prev; cur != head; cur = cur.prev) sb.append(cur.val).append(' ');
4    System.out.println(sb.toString().trim());
5}
6static DNode nodeAt(DNode head, DNode tail, int index, int size) {
7    if (index < size / 2) { DNode cur = head.next; for (int i = 0; i < index; i++) cur = cur.next; return cur; }
8    DNode cur = tail.prev; for (int i = size - 1; i > index; i--) cur = cur.prev; return cur;
9}

The second pointer adds 4 bytes per node with compressed references. For an int value the node stays 24 bytes after 8-byte alignment (12 header + 4 value + 4 + 4), but for larger payloads the extra reference is real overhead, and every change costs more pointer writes. It is worth it when you must remove arbitrary nodes by reference, walk backwards or implement an LRU cache or a deque. If you only push and pop at the ends, an ArrayDeque is smaller and faster.

A singly linked list is enough for stacks, simple queues and forward-only scans.