A linked list stores values in nodes connected by references. A singly linked node points to its successor; a doubly linked node also points to its predecessor. Unlike an array, nodes do not provide direct indexed access. Building a small list yourself helps explain head changes, traversal, and insertion before using Java's LinkedList collection. This lesson implements a singly linked list of integers and separates what is constant-time at a known position from what requires searching for that position.
Understand the head and next references
head refers to the first node or null when the list is empty. Each node contains a value and a next reference. The last node's next is null. Traversal follows references until that sentinel rather than incrementing an array index into stored contiguous slots. Changing head changes where the list begins. A detached node can still exist if another reference points to it, so unlinking and destroying an object are different concepts in Java's managed memory model.
Insert at the front in constant time
To prepend, create a node whose next points to the current head, then assign head to the new node. This works for both empty and nonempty lists. Reversing those assignments incorrectly can lose access to the previous chain or create a self-reference. Prepending needs no traversal, so it takes constant time once the value is available. Appending needs traversal unless the data structure also maintains a tail reference.
Traversal and indexed access are linear
Finding the third node requires following two links from the head. Searching for a value may visit every node, taking O(n) time. Java's LinkedList can traverse from the nearer end for indexed access, but it still does not offer array-style constant-time random access. Repeated get(i) calls inside an index loop can therefore make a list traversal unnecessarily expensive. Prefer an iterator or enhanced for loop when using the library collection.
Remove nodes by reconnecting the chain
Deleting the head assigns head to head.next. Deleting a later node requires its predecessor to bypass it by pointing to the removed node's successor. Handle the empty list and missing-value case explicitly. A linked list does not automatically know the predecessor of a singly linked node, so finding it can require a scan. Saying deletion is constant-time without stating that the necessary node references are already known hides that search cost.
Reverse links without losing the remainder
An iterative reversal keeps previous, current, and next references. Save current.next before changing that link; otherwise the remainder of the original chain becomes unreachable from your traversal. Point current backward to previous, advance previous to current, and advance current to the saved next. When current becomes null, previous is the new head. This visits each node once and uses a fixed number of auxiliary references.
Choose the library representation thoughtfully
LinkedList implements List and Deque and handles node management for you. Its nodes have allocation and reference overhead, and array-based collections often offer better locality. Use ArrayList for common indexed collection work and ArrayDeque for many local queue or stack tasks. A custom linked list is valuable for learning or a specialized requirement, not an automatic performance improvement. Protect invariants such as size and tail when you extend its representation.
Practice tasks and checks
Write a removeFirst method that returns the new head for empty, one-node, and longer lists. Then implement a remove-by-value operation and decide whether it removes the first match or every match. Test a missing value and duplicates explicitly. Reverse each resulting list and verify the order, including the empty case. If you add a size field, update it on every successful insertion and removal and ensure a rejected removal does not change it. Finally, compare a traversal using node links with a library LinkedList enhanced for loop. Explain why repeated indexed get calls are a poor way to scan a linked representation, even though the List interface allows the syntax.
Java Summary
- Linked traversal follows next references rather than array indices.
- Save the remaining chain before reversing a link.
- Include position-search cost when analyzing insertion or removal.
- Continue with stack and queue contracts when these examples are clear.
Java Examples
Each example shows the code, the output it produces and what each part does.
Build a chain by prepending
Save this program as LinkedPrepend.java. Compile it with javac LinkedPrepend.java and run it with java LinkedPrepend.
Expected output:
The first node stores four and points to null. The second stores nine and points to the former head, so head now begins the chain nine then four. Traversal reads each node and follows next. The output order is the reverse of insertion order because both insertions occurred at the front. No array indices are involved, and the final null terminates the loop.
public class LinkedPrepend {
static class Node {
final int value; Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
public static void main(String[] args) {
Node head = null;
head = new Node(4, head);
head = new Node(9, head);
for (Node node = head; node != null; node = node.next) {
System.out.println(node.value);
}
}
}9
4Unlink the node after the head
Save this program as LinkedRemoval.java. Compile it with javac LinkedRemoval.java and run it with java LinkedRemoval.
Expected output:
The original chain is two, five, eight. The assignment changes the first node's next reference to the third node, bypassing five. Traversal from head therefore prints only two and eight. The code assumes the second node exists because the example constructs it explicitly. A general remove operation must check the relevant references and return a defined result when the requested position or value is absent.
public class LinkedRemoval {
static class Node {
final int value; Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
public static void main(String[] args) {
Node head = new Node(2, new Node(5, new Node(8, null)));
head.next = head.next.next;
for (Node node = head; node != null; node = node.next) {
System.out.println(node.value);
}
}
}2
8Reverse a singly linked chain
Save this program as LinkedReverse.java. Compile it with javac LinkedReverse.java and run it with java LinkedReverse.
Expected output:
The saved next reference preserves the unprocessed remainder before current.next is redirected. previous becomes the processed reversed prefix, while current advances through the original chain. After all three nodes are processed, previous points to six, the new head. The algorithm also accepts null and returns null for an empty list. Reversing twice restores the original ordering if no other edits intervene.
public class LinkedReverse {
static class Node {
final int value; Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
static Node reverse(Node head) {
Node previous = null, current = head;
while (current != null) {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
public static void main(String[] args) {
Node head = reverse(new Node(1, new Node(3, new Node(6, null))));
for (Node node = head; node != null; node = node.next) System.out.println(node.value);
}
}6
3
1Java FAQ
Is insertion always constant-time?
Insertion is constant-time when the required position references are already available, such as prepending at head. Searching for an arbitrary insertion position can take linear time and must be included in the operation's total cost.
Does Java immediately destroy an unlinked node?
No. Unlinking changes reachability from this list. Garbage collection may reclaim an object later when no live references require it. Another reference can keep an unlinked node reachable.
Why build a linked list when Java has LinkedList?
Building one teaches how references connect objects, how insertion and removal work without shifting elements, and how to reason about null and edge cases. Those skills carry over to trees and graphs, and linked-list questions are common in interviews. In application code, use the library classes.
How do I detect a cycle in a linked list?
Use Floyd's "tortoise and hare" technique: move one reference a node at a time and another two nodes at a time. If they ever point to the same node, the list has a cycle; if the fast one reaches null, it doesn't. It needs no extra memory.
What is a dummy head node?
A placeholder node placed before the real first node. Because every real node then has a predecessor, insertion and removal at the front need no special case, which removes several if (head == null) branches. The list's real content starts at dummy.next.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What terminates traversal in the singly linked examples?
Why save next before redirecting current.next?
Java Quiz
2 questions to check what you learned.
What is the cost of finding an arbitrary value in a singly linked list?
- O(n) worst case
- O(1) always
- O(log n) without sorting
What does head.next = head.next.next do in the constructed example?
- Bypass the node containing five
- Delete the head containing two
- Reverse the entire list