← Back to the section

An array has a built-in problem: inserting or deleting in the middle forces the elements to shift, and the size is fixed up front. A linked list solves both: it grows as needed, and an insert does not move the neighbours. The price for that flexibility is losing fast access by index. One caveat right away: in application Java code a linked list is almost never used today — ArrayList beats it even where the textbook says it should not (why — at the end of the article). But you do need to know how a list works: stacks, queues, hash tables with chaining and trees are all built on it.

Nodes and references

In an array the elements sit next to each other, and the position of each is known by index. A linked list is different: every element is a separate object, a node, that holds data and a reference to the next node. The nodes are scattered anywhere in memory and are held together by those references — like links in a chain.

class Node {
    long data;
    Node next;
}

A class with a field that points to an object of the same class is called self-referential. The list itself stores only a reference to the first node (first); from there, following next, you can reach any of them. The last node points to nowhere (null) — that is how the end of the list is recognised.

The key idea: a list relies on the relationships between elements, not on their positions. In an array you find a house by its address; in a list — only by walking the chain and asking each node, "where is the next one?".

What a list does fast, and what it does slowly

  • Insert at the head — O(1). Create a node, point its next at the former first one, and point first at the new node. Nothing shifts, no matter how many elements there are.
  • Delete from the head — O(1). Just move first to the second node.
  • Deleting a node from the middle is cheap once it is found: the previous node's next is replaced, throwing the reference over the deleted one. No shifting.
  • Search — O(N). This is the weak spot: to find an element by value, or to reach a given position, you walk the chain from the start.

An array has fast access by index but expensive inserts and deletes; a list is the other way round.

null 37 45 58 12 first

Create a node, point its next at the former first one, and move first onto the new node. Not a single element shifts — O(1) at any length.

Let's check that on a live list. The hops counter counts steps along next references — the work a list does instead of index arithmetic.

live example

public class LinkedListDemo {
    static class Node {
        int value; Node next;
        Node(int value, Node next) { this.value = value; this.next = next; }
    }

    static Node first;
    static int hops;

    static Node nodeAt(int index) {
        Node node = first;
        for (int i = 0; i < index; i++) { node = node.next; hops++; }
        return node;
    }

    static void print(String label) {
        StringBuilder chain = new StringBuilder();
        for (Node n = first; n != null; n = n.next) chain.append(n.value).append(" -> ");
        System.out.println(label + chain + "null,  hops: " + hops);
    }

    public static void main(String[] args) {
        for (int value : new int[] {58, 45, 37, 21, 16}) first = new Node(value, first);
        first = new Node(12, first);
        print("insert at head:      ");
        Node before = nodeAt(2);
        before.next = before.next.next;
        print("delete in the middle: ");
        hops = 0;
        for (int i = 0; i < 5; i++) nodeAt(i);
        System.out.println("five lookups by index: " + hops + " hops");
    }
}
Run

Running examples is part of paid access. There the same code runs inside the article: editor, run and check next to the paragraph. Free week →

The insert at the head cost not a single step. The delete in the middle took two — walking to the predecessor; re-pointing the reference itself is free. And five lookups by index cost ten steps: each one starts over from the beginning.

Doubly linked list

A singly linked list has an inconvenience: you can only move forward, and knowing a node does not let you get to the previous one quickly. A doubly linked list adds a second reference to every node — to the previous element (prev). Now the list can be walked in both directions, and deleting a node no longer requires a separate search for its predecessor.

The price is one extra reference per node and the need to update both references on every operation. A doubly linked list is a convenient base for a deque, where elements are added and taken at both ends.

A list as the base for other structures

A stack and a queue can be built on a list rather than on an array: push/pop of a stack is an insert/delete at the head, both O(1). The advantage is that the size need not be known in advance — the list grows as needed.

This is where the abstract data type (ADT) shows up: a stack is defined not by how it is built inside, but by what it can do — push, pop, peek. Inside it may be an array or a list, and the user does not care. Behaviour is described separately from the implementation, so the internals can be changed without touching the surrounding code.

Sorted list

A list can be kept sorted: a new element is inserted not at the head but at its place in order. Then:

  • the insert becomes O(N) (you have to walk to the insertion point), but still without shifting — only a couple of references are re-pointed;
  • the minimum (or maximum) element is always at the head, and taking it out is instant.

A sorted list is handy as a simple priority queue.

Iterators

The weak spot of a list is that there is no access by index. When you need not just "find by value" but to walk the list methodically, inserting and deleting at arbitrary places, you take an iterator — an object that remembers the current node and can move to the next one, read, insert and delete "right here". An iterator is like a finger running along the lines of a page: it gives access to the middle of the list, which the list itself does not have.

How it is done in Java

You do not need to write your own list — the standard library has one. But this is exactly where people pick a structure from a table of complexities and miss.

The reference implementation is LinkedList. Inside it is exactly what we discussed, in the doubly linked flavour: a node with the fields item, next and prev, while the class itself keeps references to the first and the last node. So it honestly delivers what the theory promises: adding or removing an element at either end is O(1) at any length. It also implements Deque, which makes it usable both as a stack and as a queue.

Then come the caveats. get(i) is O(N): nodes have no indexes, so you step along the references (LinkedList starts from the nearer end, but that halves the work, it does not change the growth rate). remove(i) and add(i, v) are O(N) too: you first have to get to the place. O(1) stays with the re-pointing of references, not with the operation as a whole.

By the table of complexities LinkedList should beat ArrayList on inserts and deletes in the middle — in practice it loses almost always. The reason is the hardware. The elements of an ArrayList lie next to each other in memory: the processor pulls them into the cache in batches, and a shift is a single memory-copy operation. The nodes of a LinkedList are scattered over the heap, and every step along next is a jump to an unpredictable place — a cache miss and a wait for memory. On top of that, a node is a separate object with three references and a header: several times more memory for the same element. In the end a linear shift comes out cheaper than the "free" re-pointing after a long walk along references.

The practical conclusion is simple: by default you take ArrayList, and if you need a stack or a queue — ArrayDeque, not LinkedList.

One last pitfall — walking by index:

// wrong
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

// right
for (Long value : list) {
    process(value);
}

On an ArrayList the first loop is O(N), on a LinkedList it is O(N²): every get walks from the end along the references. On a hundred elements you see no difference; on a hundred thousand the loop grinds to a halt. A for-each loop and an iterator move one step along next instead of counting the way from the end again.

In short

  • A linked list is a chain of nodes; each holds data and a reference to the next one. It relies on links, not on positions.
  • Insert and delete at the head are O(1), with no shifting and no size fixed in advance. Search is O(N): you walk the chain.
  • A doubly linked list adds a reference to the previous node — traversal in both directions, a convenient base for a deque.
  • A list is the base for a stack and a queue; hence the ADT idea: a structure is defined by behaviour, not by its internals.
  • A sorted list keeps elements in order; an iterator gives controlled access to the middle.
  • In Java you take ArrayList by default, and ArrayDeque for a stack or a queue: the scattered nodes of a LinkedList lose to the processor cache.