Linked Lists

A different arrangement

An array keeps its elements packed together in one block. A linked list does the opposite: each element lives in its own small object, and each object holds a reference to the next one.

class Node {
    int value;
    Node next;         // reference to the following node, or null at the end

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

A list of three values is three Node objects, each pointing at the next:

[10] -> [20] -> [30] -> null

You keep a reference to the first node, called the head. Everything else is reached by following next from there.

This depends on understanding references — if Node next holding another object feels unclear, review Objects and References first.

Building one by hand

Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);

// walk the list
Node current = head;
while (current != null) {
    System.out.println(current.value);
    current = current.next;
}

The walking pattern — a current reference that advances until it hits null — is how every operation on a linked list works. It is worth writing out a few times until it is automatic.

Node current = head;
while (current != null) { ... current = current.next; }

Why insertion is cheap

To insert a value after a node you already have a reference to, you rearrange two references. Nothing moves.

void insertAfter(Node node, int value) {
    Node fresh = new Node(value);
    fresh.next = node.next;      // new node points at what came next
    node.next = fresh;           // previous node points at the new one
}

The order matters. Setting node.next = fresh first would lose the reference to the rest of the list.

Compare with an array, where inserting in the middle shifts every following element. Here it is two assignments regardless of how long the list is.

Removing is similarly cheap — point around the node you want gone:

void removeAfter(Node node) {
    if (node.next != null) {
        node.next = node.next.next;
    }
}

The removed node is no longer reachable, and Java’s garbage collector reclaims it.

Why indexing is expensive

There is no arithmetic that finds the fifth node. The nodes are scattered in memory, so the only way to reach index 5 is to start at the head and follow next five times.

int get(Node head, int index) {
    Node current = head;
    for (int i = 0; i < index; i++) {
        if (current == null) throw new IndexOutOfBoundsException();
        current = current.next;
    }
    return current.value;
}

This is the fundamental trade: arrays give instant indexing and expensive insertion, linked lists give cheap insertion and slow indexing.

Array versus linked list

Java’s LinkedList

You rarely write your own. Java provides one, and it implements both List and Deque.

import java.util.LinkedList;

LinkedList<String> tasks = new LinkedList<>();
tasks.add("intake");             // append
tasks.addFirst("initialise");    // prepend — instant
tasks.addLast("shoot");

System.out.println(tasks.getFirst());   // initialise
tasks.removeFirst();

Java’s version is doubly linked — each node also holds a previous reference. That makes it possible to walk backwards and to remove from the end instantly.

Why learn it then

Two reasons, both practical.

The node-and-reference idea is the foundation for trees and graphs, which are genuinely the right tool for many problems. A tree is a node with several next references instead of one. If linked lists make sense, Trees will too.

And it teaches you to reason about references — what happens when two variables point at the same object, and what it means for something to become unreachable.

Next