Linked Lists:Singly, Doubly, and Circular Without Losing the Head

You hold a cursor on a playlist: “insert this track after the current song.” On an ArrayList, every later track slides one slot. On a linked list you rewire two pointers — if you already hold the node.

That is the layout the series glossary names as linked versus contiguous. An array sits in one block; index i is pointer arithmetic. A linked list sits in nodes. To reach the fifth element you walk four pointers. Splice is cheap when you hold the node. Index i is a walk. Lose the head pointer and the whole chain is unreachable.

This post covers the three variants you actually meet: singly, doubly, and circular. Head and tail, the “lost the head” bug, optional dummy nodes, and why java.util.LinkedList is a doubly linked deque that still loses to ArrayList for most Java lists.

The bill: walk vs splice

There is no “fast linked list.” There is a structure whose expensive operations are ones you rarely perform. Read this table as a shopping list, the same way the roadmap taught complexity tables:

Operation	Cost	Why
get(i)	O(n)	Walk i pointers from a known end
Insert / delete after a held node	O(1)	Rewire a couple of pointers
Insert / delete at index i	O(n)	Walk, then splice
Search by value	O(n)	Same scan as any unsorted list
Space	O(n)	One node object (and pointer(s)) per element

The cheap splice is the whole point. The walk is the tax. If the hot path is “I already have this node; put something next to it,” a linked list is the right layout. If the hot path is get(i) or a tight scan, it is not.

A singly list in one sketch:

head → [A|•] → [B|•] → [C|•] → null
         ^ you hold B
insert X after B: B.next = X; X.next = C
splice is O(1). Finding B from head is O(n).

Singly linked lists

Each node stores a value and one pointer: next. The list is the head. Everything else is a walk from there.

A minimal node and a list that tracks head — and optionally tail, so append does not scan:

final class SinglyList<T> {
    static final class Node<T> {
        T value;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size;

    Node<T> head() { return head; }
    int size() { return size; }
}

Keep a tail if append is hot. Insert-at-end becomes O(1): tail.next = newNode; tail = newNode. Delete-the-last stays O(n) on a singly list — you need the predecessor of tail, and you do not have a prev pointer to find it.

Losing the head

The list is the head reference. Reassign a local and you have not moved the list. Drop the only reference to head and the chain is garbage.

This prepend looks like it works until you notice head never moved:

void brokenAddFirst(Node<T> newHead) {
    newHead.next = head; // new node points at the old chain
    // forgot: head = newHead;
}

Callers still see the old first node. The new one is reachable only if someone else kept newHead. The correct prepend updates the list’s entry point — and tail, when the list was empty:

void addFirst(T value) {
    Node<T> n = new Node<>(value);
    n.next = head;
    head = n;
    if (tail == null) {
        tail = n;
    }
    size++;
}

A local Node p = head; p = p.next does not move the list. It moves your finger. head = head.next is how you drop the first element — and if that was the last node, you must clear tail too.

Splice when you hold the node

Insert-after is the operation arrays cannot match. You already have node. You do not walk from head:

void insertAfter(Node<T> node, T value) {
    Node<T> n = new Node<>(value);
    n.next = node.next;
    node.next = n;
    if (node == tail) {
        tail = n;
    }
    size++;
}

Delete is awkward on a singly list: to unlink node you need its predecessor. Either walk from head (O(n)), or delete the successor and copy (a trick, not a general API). That gap is why doubly lists exist.

Dummy nodes (optional)

A dummy (sentinel) head is a node you never treat as data. head.next is the first real element. Empty and non-empty lists share the same insert/delete code — you stop special-casing “is this the first node?”

// dummy.next is the first real node; dummy itself has no payload
final Node<T> dummy = new Node<>(null);

void insertAfterDummyStyle(Node<T> pred, T value) {
    Node<T> n = new Node<>(value);
    n.next = pred.next;
    pred.next = n;
}

You do not need a dummy. It is a bookkeeping choice. Use it when the empty-list branches are noisier than one extra node. Skip it when the list is a teaching sketch or a short-lived structure with two operations.

Doubly linked lists

Each node stores prev and next. You can walk both ways. More importantly, you can unlink the node you hold without finding a predecessor.

final class DoublyList<T> {
    static final class Node<T> {
        T value;
        Node<T> prev;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private Node<T> head;
    private Node<T> tail;
}

Unlink is pointer surgery on both neighbors. Ends are the usual special cases — unless you add dummy nodes at both ends and never let head / tail be data:

void unlink(Node<T> node) {
    Node<T> p = node.prev;
    Node<T> n = node.next;
    if (p != null) {
        p.next = n;
    } else {
        head = n;
    }
    if (n != null) {
        n.prev = p;
    } else {
        tail = p;
    }
    node.prev = node.next = null;
}

Head and tail are both first-class. addFirst / addLast / removeFirst / removeLast are O(1). That is a deque. An LRU cache is this shape plus a hash map from key to node: hit moves a held node to the front in O(1); miss evicts the tail. The cache post in this series will assemble that machine; the list half is what you just saw.

Note: Extra prev pointers cost memory and extra writes on every splice. You pay that to make delete-the-held-node and reverse walks cheap. If you only ever prepend and walk forward, a singly list is enough.

Dummy nodes show up here more often than on singly lists. Two sentinels (or one circular sentinel — see below) mean unlink never tests p == null. java.util.LinkedList uses a single sentinel node whose next is the first element and whose prev is the last.

Circular lists

In a circular list the last node’s next points at the first. There is no null terminator. A singly circular list with one external pointer often keeps the tail: tail.next is head, so both ends are one hop away.

         ┌──────────────────────────┐
         ▼                          │
tail → [C|•] → [A|•] → [B|•] ───────┘
              head = tail.next

Round-robin is the natural job: take the next client, then advance. You do not fall off the end; you come back around. Stop conditions must compare identity (“back to the start node”), not next == null.

A rotate-and-serve sketch — tail is the last served; tail.next is next up:

T serveNext(Circular<T> ring) {
    if (ring.tail == null) {
        throw new NoSuchElementException();
    }
    ring.tail = ring.tail.next; // advance to the next node
    return ring.tail.value;
}

A circular doubly list wraps both directions: head.prev == tail and tail.next == head. One sentinel node can sit in that ring and make the real list a loop of data nodes around it. Josephus-style “every k-th node” games, multiplayer turns, and some buffer rings use this shape.

A naive loop for (Node n = head; n != null; n = n.next) never ends on a circular list. Walk with a start mark:

void visitAll(Node<T> start) {
    if (start == null) {
        return;
    }
    Node<T> n = start;
    do {
        System.out.println(n.value);
        n = n.next;
    } while (n != start);
}

Empty circular lists are a design choice: tail == null, or a sentinel that points at itself. Pick one and keep it consistent. Mixing “null means empty” with “self-linked sentinel” is how you insert into a ghost ring.

java.util.LinkedList is a doubly linked deque

Java’s LinkedList is not a singly teaching list. It is a doubly linked list that implements List and Deque: nodes with prev / next, a header sentinel, O(1) add/remove at both ends, and List indexes that walk.

LinkedList<String> tracks = new LinkedList<>();
tracks.addLast("intro");
tracks.addLast("verse");
tracks.addFirst("cold-open");   // O(1)
tracks.removeLast();            // O(1)
String at = tracks.get(2);      // O(n) — still a walk

Use it when you need List plus cheap ends, or when you already hold a ListIterator and splice through that iterator. Do not use it as “the linked list I learned in class” for a stack or queue — ArrayDeque is the JDK default for both ends without the node objects.

ArrayList still wins for almost every ordinary Java list. Random access is O(1). Scans hit contiguous memory (CPU cache lines actually help). Append is amortized O(1). LinkedList.get(i) in a loop is accidentally quadratic: each get restarts from an end.

int sumIndexed(List<Integer> list) {
    int s = 0;
    for (int i = 0; i < list.size(); i++) {
        s += list.get(i); // ArrayList: O(1) each. LinkedList: O(n) each.
    }
    return s;
}

Iterate with for-each / an iterator if you must use LinkedList. Index loops are how people “prove” linked lists are slow when they have only proved that get(i) walks.

When not to use a linked list

Skip this layout when:

• The hot path is random access — get(i), binary search over indexes, shuffling by index. That is an array / ArrayList job.
• You scan a lot. Node objects are scattered on the heap. A linear read of an ArrayList is a cache-friendly stride. A linear read of a linked list is a pointer chase: more cache misses, more GC pressure from one object per element.
• You only needed a stack or queue. ArrayDeque gives O(1) ends on a circular array. You do not need prev / next for that ADT.
• You do not hold the node. “Insert at index 50,000” is a walk then a splice. The splice is O(1); finding the spot is O(n). An ArrayList also pays O(n) to slide — but the slide is a tight memmove over contiguous memory, which often beats the walk-plus-allocate of a linked list at real sizes.
• The list is small. Constant factors dominate. An ArrayList of twenty elements is not a performance story.

Note: Interview folklore says “linked list if you insert in the middle.” The accurate version is: linked list if you insert in the middle and you already hold the node (or an iterator sitting on it). Otherwise you paid the walk, and you should measure against an array.

Cheat sheet

Singly:   value + next. Head is the list. Tail makes append O(1).
          Delete-held-node needs a predecessor (or a walk).
Doubly:   prev + next. Unlink the node you hold in O(1). Deque-shaped.
Circular: last.next = first. Stop on identity, not null. Tail often is the handle.
Dummy:    optional sentinel so empty/head cases share code.

get(i)              O(n)     — always a walk
splice (hold node)  O(1)     — the reason this layout exists
insert at index i   O(n)     — walk, then splice
search by value     O(n)

JDK:  LinkedList = doubly linked deque (List + Deque)
      Prefer ArrayList for indexed lists; ArrayDeque for stacks/queues

Do:

• Name the hot operation first. Splice-with-node is the green light.
• Update head and tail on every end mutation. Empty-list is a real state.
• Walk circular lists with a start mark (do / while (n != start)).
• Iterate LinkedList with an iterator, not get(i) in a for index loop.

Don’t:

• Reassign a local copy of head and think the list moved.
• Use LinkedList as a default List. It is a deque that also implements List.
• Treat “insert in the middle” as automatically cheaper than ArrayList when you still have to find index i.
• Write n != null as the loop guard on a circular ring.

Wrap-up

A linked list is nodes and pointers. get(i) walks. Splice is O(1) when you already hold the node. Singly lists are the smallest story: one next, a head you must not lose, an optional tail for cheap append, and awkward deletes. Doubly lists add prev so the node you hold can leave in O(1) — that is the deque (and the list half of an LRU). Circular lists drop the null end so a walk returns to the start; the loop guard is identity, not null.

java.util.LinkedList is a doubly linked deque. For an ordinary indexed list, ArrayList still wins: contiguous scans, O(1) get(i), amortized append. Reach for a linked layout when the job is rewiring a held node, not when the job is “a list” in the everyday Java sense.

Terms this post used without re-defining — ADT vs implementation, contiguous vs linked, Big-O — live on the Data Structures Roadmap.

Next optional step in the series LIFO is the same shape as undo and the call stack. Stack: Undo, Parse, and Call Frames →