Linked List Implementation in Java
Think of a treasure hunt at a school fair. Each clue tells you where to find the next clue, and the last one says "the end". There is no master list of all the clues: to reach the fifth clue you must follow the first four. Adding a new clue at the start is easy, though: write it, point it at the old first clue, and you are done. A linked list stores data the same way. Each element, called a node, holds a value and a link to the next node. In this lesson, you will build a singly linked list from scratch in Java, with adding, removing, searching and reversing, and compare it with the JDK's LinkedList and ArrayList.
What Is a Linked List?
A linked list in Java is a linear data structure that is used to store a sequence of elements in nodes, where each node holds a value and a reference to the next node. The list keeps a reference to the first node, called the head. The last node's next is null.
| Kind | Each node links to | JDK class |
|---|---|---|
| Singly linked list | The next node | None (you build it) |
| Doubly linked list | The next and the previous node | java.util.LinkedList |
| Circular linked list | The next node; the last links back to the first | None |
The Node and the List
Let's see a complete singly linked list of strings with the most common operations.
public class SubjectList {
private static class Node {
String value;
Node next;
Node(String value) {
this.value = value;
}
}
private Node head;
private int size;
void addFirst(String value) { // O(1)
Node node = new Node(value);
node.next = head;
head = node;
size++;
}
void addLast(String value) { // O(n): walk to the end
Node node = new Node(value);
if (head == null) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
size++;
}
boolean remove(String value) { // O(n): find it first
if (head == null) return false;
if (head.value.equals(value)) {
head = head.next;
size--;
return true;
}
Node current = head;
while (current.next != null && !current.next.value.equals(value)) {
current = current.next;
}
if (current.next == null) return false;
current.next = current.next.next; // skip over the node
size--;
return true;
}
int indexOf(String value) { // O(n)
int index = 0;
for (Node n = head; n != null; n = n.next, index++) {
if (n.value.equals(value)) return index;
}
return -1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Node n = head; n != null; n = n.next) {
sb.append(n.value).append(" -> ");
}
return sb.append("null").toString();
}
public static void main(String[] args) {
SubjectList list = new SubjectList();
list.addLast("Math");
list.addLast("Science");
list.addLast("English");
System.out.println(list + " (size " + list.size + ")");
list.addFirst("History");
System.out.println(list);
System.out.println("indexOf Science: " + list.indexOf("Science"));
list.remove("Science");
System.out.println(list + " (size " + list.size + ")");
}
}Math -> Science -> English -> null (size 3)
History -> Math -> Science -> English -> null
indexOf Science: 2
History -> Math -> English -> null (size 3)Explanation:
Nodeis a private nested class: users of the list never see nodes, only values.addFirstcreates a node, points it at the old head and moveshead. It doesn't matter how long the list is, so it is O(1).addLastmust walk from the head to the last node, which is O(n). (Keeping atailreference would make it O(1).)removefinds the node before the one to delete and makes it skip over it:current.next = current.next.next. The removed node is no longer reachable, so the garbage collector frees it.- Removing the head is a special case, because there is no node before it.
Reversing a Linked List
Reversing a singly linked list in place is one of the most asked interview questions. Walk through the list and turn each next arrow around, keeping track of the previous node.
public class Reverse {
record Node(int value, Node next) {}
static Node reverse(Node head) {
Node previous = null;
Node current = head;
while (current != null) {
Node rest = current.next; // remember the rest
current = new Node(current.value(), previous);
previous = current; // step forward
current = rest;
}
return previous;
}
static String show(Node head) {
StringBuilder sb = new StringBuilder();
for (Node n = head; n != null; n = n.next()) {
sb.append(n.value()).append(" -> ");
}
return sb.append("null").toString();
}
public static void main(String[] args) {
Node list = new Node(1, new Node(2, new Node(3, new Node(4, null))));
System.out.println(show(list));
System.out.println(show(reverse(list)));
}
}1 -> 2 -> 3 -> 4 -> null
4 -> 3 -> 2 -> 1 -> nullExplanation: previous starts as null, which becomes the new end. For each node, the loop saves the rest of the list, links the node to previous, and steps forward. Because these nodes are immutable records, it builds new nodes; with mutable nodes (like SubjectList), you would write current.next = previous instead and reuse the same nodes. Either way the walk is O(n).
Linked List vs Array List
| Operation | Singly linked list | java.util.LinkedList | ArrayList |
|---|---|---|---|
get(i) | O(n) | O(n) | O(1) |
| Add or remove at the front | O(1) | O(1) | O(n) (shifts everything) |
| Add at the end | O(n), or O(1) with a tail | O(1) | O(1) on average |
| Remove from the middle | O(n) to find, O(1) to unlink | same | O(n) |
| Memory per element | value + 1 reference | value + 2 references | value only |
Interview Corner
How do you find the middle of a linked list in one pass?
Use two references: slow moves one node at a time and fast moves two. When fast reaches the end, slow is in the middle.
How do you detect a cycle?
The same two-speed trick (Floyd's algorithm): if fast ever meets slow, there is a cycle.
Why is get(i) slow in a linked list?
There are no indexes in memory; you must follow i links from the head.
Practice
- Easy: Add a
tailfield toSubjectListso thataddLastbecomes O(1). Remember to updatetailinremovewhen the last node is removed. - Harder: Write
String middle()using the slow and fast pointer trick. Test it with 3, 4 and 5 subjects.
Key Takeaways
Was this tutorial helpful?