Node fundamentals

A linked list node stores one value and one reference to the next node. In Java the reference is just a field of the node's own type, and it is null when there is no next node. Nodes are separate objects on the heap, so a list needs no contiguous block of memory.

Each node costs an object header plus the value and the reference: about 24 bytes for an int value on a 64-bit JVM with compressed references.

1class Node {
2    int val;
3    Node next;                        // reference to the next node, or null
4    Node(int val) { this.val = val; }
5}
6Node a = new Node(10), b = new Node(20), c = new Node(30);
7a.next = b; b.next = c;               // a -> b -> c -> null

The head is the first node and the only entry point: lose the head reference and the whole list is unreachable. The tail is the last node, the one whose next is null. A singly linked list usually stores only the head; keeping a separate tail reference makes appending O(1).

Without a tail pointer, reaching the end means walking the whole list.

1class LinkedList {
2    Node head, tail;
3    int size;
4    void addLast(int v) {                       // O(1) thanks to the tail reference
5        Node n = new Node(v);
6        if (head == null) head = tail = n;
7        else { tail.next = n; tail = n; }
8        size++;
9    }
10}

A singly linked list is a chain of nodes where each node points only forward. Reading the k-th element needs k hops (O(k)), while inserting or deleting right after a node you already hold is O(1) with no shifting. It cannot move backwards, so anything that needs the previous node must keep it while walking.

The animation contrasts reading element k in an array with walking k links.

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}

The end of a list is marked by next == null. Loops walk until the current node is null (visiting every node) or until cur.next is null (stopping at the last node), and choosing the wrong one is a classic off-by-one. Always guard against an empty list (head == null), and never call a method on a possibly-null reference.

A cycle breaks this contract: the loop would never see null.

1static int length(Node head) {
2    int n = 0;
3    for (Node cur = head; cur != null; cur = cur.next) n++;   // stops after the last node
4    return n;
5}
6static Node last(Node head) {
7    if (head == null) return null;
8    Node cur = head;
9    while (cur.next != null) cur = cur.next;                   // stops AT the last node
10    return cur;
11}

Variables of type Node hold references. a == b is true only if both refer to the same node object; two nodes with equal values are different nodes. Assigning Node cur = head copies the reference, not the node, so moving cur never changes the list, while writing cur.next = x changes the shared node everyone sees.

This is why “moving a pointer” and “changing a link” are different operations.

1Node a = new Node(5), b = new Node(5);
2boolean sameNode = (a == b);              // false: two different objects with equal values
3Node alias = a;
4alias.val = 9;                            // a.val is now 9 too
5Node cur = a; cur = cur.next;             // moves the local reference only; the list is unchanged