Java singly linked lists
Build a list of nodes by hand, insert at the front and the back, and reverse it.
class Main {
static class Node {
int value;
Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
static Node head = null;
static void addFirst(int value) {
head = new Node(value, head);
}
static void addLast(int value) {
Node node = new Node(value, null);
if (head == null) {
head = node;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
static void reverse() {
Node previous = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
}
head = previous;
}
static String show() {
StringBuilder sb = new StringBuilder();
for (Node n = head; n != null; n = n.next) {
sb.append(n.value).append(n.next == null ? "" : " -> ");
}
return sb.toString();
}
public static void main(String[] args) {
addFirst(2);
addFirst(1);
addLast(3);
addLast(4);
System.out.println(show());
reverse();
System.out.println(show());
}
}1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1
Explanation
A singly linked list stores each item in a node that holds a value and a reference to the next node. The list keeps a reference to the first node, called the head. Inserting at the front is O(1): create a node whose next is the old head and make it the new head. Appending at the end is O(n) unless the list also keeps a tail reference.
Reversing the list walks through it once and flips each next reference. Three references are needed: the previous node, the current node, and the next node, saved before the link is changed. Lists give constant-time insertion at a known position and no shifting, but they have no fast indexing and use extra memory per element.
Explore the dry run
class Main { static class Node { int value; Node next; Node(int value, Node next) { this.value = value; this.next = next; } } static Node head = null; static void addFirst(int value) { head = new Node(value, head); } static void addLast(int value) { Node node = new Node(value, null); if (head == null) { head = node; return; } Node current = head; while (current.next != null) { current = current.next; } current.next = node; } static void reverse() { Node previous = null; Node current = head; while (current != null) { Node next = current.next; current.next = previous; previous = current; current = next; } head = previous; } static String show() { StringBuilder sb = new StringBuilder(); for (Node n = head; n != null; n = n.next) { sb.append(n.value).append(n.next == null ? "" : " -> "); } return sb.toString(); } public static void main(String[] args) { addFirst(2); addFirst(1); addLast(3); addLast(4); System.out.println(show()); reverse(); System.out.println(show()); }}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The new node points to the old head and becomes the head: O(1). | — | — | |
| To append, walk to the last node: O(n). | — | — | |
| Reversal flips the link of the current node to point backwards. | — | — | |
| After addFirst(2), addFirst(1), addLast(3), addLast(4) the list is 1, 2, 3, 4. | — | 1 -> 2 -> 3 -> 4 | |
| When the loop ends, previous is the old last node, which is the new head. | — | 1 -> 2 -> 3 -> 4 | |
| The same nodes now appear in the reverse order. | — | 1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1 |
Cost and common mistakes
addFirst O(1), addLast O(n), reverse O(n) time and O(1) extra space.
- Always save current.next before overwriting it, or the rest of the list is lost.
- Forgetting to handle the empty list (head == null) causes a NullPointerException.
- In practice use java.util.LinkedList or ArrayList. Writing a list by hand is for learning how they work.
Try it yourself
How would you add a tail reference to make addLast O(1)?
Reveal answer and reasoning
Keep a Node tail field; addLast sets tail.next = node and tail = node, with a special case for an empty list.