Linked lists explained for university students
8 min readUpdated
A linked list stores items in separate nodes, each pointing to the next. It is a core topic in university data structures modules because it teaches you to think in references instead of indexes.
Nodes and references
Each node holds a value and a reference to the next node. The list keeps a reference to the first node, the head. The last node's next is null.
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}Traversing
Node current = head;
while (current != null) {
System.out.println(current.value);
current = current.next;
}Inserting and deleting
// insert at the front: O(1)
Node n = new Node(5);
n.next = head;
head = n;
// delete the node after prev: O(1) once you have prev
if (prev.next != null) {
prev.next = prev.next.next;
}Order matters: set the new node's next before moving head, or you lose the rest of the list.
Reversing a list
Node reverse(Node head) {
Node prev = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}Linked list vs array
| Operation | Array / ArrayList | Singly linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at front | O(n) | O(1) |
| Insert at end | O(1) amortised | O(1) with a tail reference, else O(n) |
| Search | O(n) | O(n) |
| Memory | Compact | Extra reference per node |
Doubly linked lists
Each node also has a prev reference, so you can walk backwards and delete a node in O(1) when you already hold it. Java's LinkedList class is doubly linked.
Bugs students hit most
- NullPointerException from reading
current.nextwhencurrentis null. - Losing the rest of the list by overwriting a
nextbefore saving it. - Forgetting to update
headwhen the first node changes. - Not handling the empty list and the one-node list.
Draw boxes and arrows on paper for every pointer change. It is the fastest way to find a linked list bug.
Frequently asked questions
Why use a linked list if arrays are faster to index?
Linked lists make insertion and deletion at known positions cheap and never need resizing. They also underpin stacks, queues and hash table chains.
How do I find the middle of a linked list?
Move a slow pointer one step and a fast pointer two steps; when fast reaches the end, slow is in the middle.
How do I detect a cycle?
Use the same slow and fast pointers. If they ever meet, the list has a cycle.
Learn it step by step
Practise this, step by step
Short lessons with quizzes, practice and interview questions, from your first program to job-ready.