Linked lists

Q: What are the most common mistakes with Linked lists?

Losing the rest of the list by overwriting next too early. Null pointer on an empty list or at the tail. Cycles created by mistake causing infinite loops. Forgetting to update head or tail.

A linked list is a chain of nodes, each holding a value and a reference to the next node.

🔎 Unravel this example Prerequisites (2)

Learn these first

Classes, objects and constructors Nested and inner classes

At a glance

Mental model

A treasure hunt: each clue (node) tells you where the next clue is.

What happens, in order

1A node: class Node { int val; Node next; }The list is just a reference head to the first node; the last node has next == null.
2Traverse: for (Node n = head; n != null; n = n.next)Insert after n: new.next = n.next; n.next = new;. Delete after n: n.next = n.next.next;.
3Reverse in place with three references: prev, curr, and next: next = curr.next; curr.next = prev; prev = curr; curr = next;
4A dummy head node (dummy.next = head) removes the special case of changing the first nodeTwo pointers at different speeds find the middle or a cycle (slow and fast).

Remember

Order of pointer updates is everything: change n.next before saving the old value and the rest of the list is lost
In production use ArrayList or ArrayDeque; they are faster due to cache locality
Each node is a separate heap object (header plus two references, about 24 to 32 bytes) scattered in memory, so traversal causes cache misses; this is why the theoretical advantage of cheap insertion rarely shows in benchmarks

Watch out

Losing the rest of the list by overwriting next too earlyNull pointer on an empty list or at the tailCycles created by mistake causing infinite loopsForgetting to update head or tail

Example (highlighted lines explain it)

public class LinkedLists {  static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } }  static ListNode reverse(ListNode head) {    ListNode prev = null, curr = head;    while (curr != null) {      ListNode next = curr.next;      curr.next = prev;      prev = curr;      curr = next;    }    return prev;  }  static boolean hasCycle(ListNode head) {    ListNode slow = head, fast = head;    while (fast != null && fast.next != null) {      slow = slow.next; fast = fast.next.next;      if (slow == fast) return true;    }    return false;  }}

line 2 uses ListNode, the core of Linked lists
line 3 uses ListNode, the core of Linked lists
line 4 uses ListNode, the core of Linked lists
line 6 uses ListNode, the core of Linked lists
line 13 uses ListNode, the core of Linked lists
line 14 uses ListNode, the core of Linked lists

Read the full explanation (about 2 min)

A linked list is a chain of nodes, each holding a value and a reference to the next node. Insertion and removal are cheap once you hold the right node; reaching the nth item means walking from the head.

A mental model

A treasure hunt: each clue (node) tells you where the next clue is. You can add a clue by changing one pointer, but to reach clue 50 you must follow the first 49.

How it works

A node: class Node { int val; Node next; }. The list is just a reference head to the first node; the last node has next == null.

Traverse: for (Node n = head; n != null; n = n.next). Insert after n: new.next = n.next; n.next = new;. Delete after n: n.next = n.next.next;.

Reverse in place with three references: prev, curr, and next: next = curr.next; curr.next = prev; prev = curr; curr = next;.

A dummy head node (dummy.next = head) removes the special case of changing the first node. Two pointers at different speeds find the middle or a cycle (slow and fast).

Going deeper

Order of pointer updates is everything: change n.next before saving the old value and the rest of the list is lost.

In production use ArrayList or ArrayDeque; they are faster due to cache locality. Linked lists matter for learning pointers, for LRU caches (with a hash map), and for lock-free structures.

Doubly linked lists add prev, enabling O(1) removal of a node you already hold; LinkedHashMap and LinkedList use them.

Under the hood

Each node is a separate heap object (header plus two references, about 24 to 32 bytes) scattered in memory, so traversal causes cache misses; this is why the theoretical advantage of cheap insertion rarely shows in benchmarks.

Common mistakes

Losing the rest of the list by overwriting next too early.
Null pointer on an empty list or at the tail.
Cycles created by mistake causing infinite loops.
Forgetting to update head or tail.

How Unravel recognises it

When you paste code, Unravel looks for these signs of linked lists. Spotting them yourself is a good habit when you read unfamiliar code:

Types: ListNode Node
Created with new: ListNode

Part of a learning path

Algorithms and data structures · previous: Dynamic programming and memoisation · next: Building your own stack or queue

Related concepts

ArrayList vs LinkedListJava language Nested and inner classesJava language Trees and tree traversalJava language

Frequently asked questions

What is Linked lists?

What are the most common mistakes with Linked lists?

Losing the rest of the list by overwriting next too early. Null pointer on an empty list or at the tail. Cycles created by mistake causing infinite loops. Forgetting to update head or tail.

How can I see Linked lists in real code?

Paste your own Java into Unravel and it will point out where linked lists appears, explain how it works at the detail level you choose, and draw the flow of the code around it.