What a linked list is
A linked list stores a sequence of values in separate small objects called nodes. Each node holds one value and a reference to the next node. The list is identified by its first node, the head, and the last node's reference is null, which marks the end. To visit the elements in order, you start at the head and follow the references one by one.
This is the opposite trade-off from an array. An array keeps its elements side by side in memory, so reading element i is a direct jump. A linked list scatters its nodes, so reaching element i means following i references. In exchange, adding or removing a node needs no shifting of other elements: only a reference or two change.
A node in Scala
The linked list lessons use a node class with two mutable fields, a value and a link to the next node. In Scala it can be written like this:
class ListNode(var `val`: Int = 0, var next: ListNode = null)
Some details of this definition:
varin the parameter list turns each parameter into a mutable field. Withvalinstead ofvar,nextcouldn't be reassigned, and the list couldn't be changed in place.- Backticks around
val.valis a Scala keyword, so using it as a field name needs backticks, both in the definition and when reading the field:node.`val`. - Default arguments.
ListNode()makes a node with value 0 and no next node, andListNode(5)gives value 5. Calling a class withoutnewis allowed in Scala 3. nullmarks the end. Scala code normally prefersOption, but the lessons usenullto match the usual linked list formulation. Followingnexton anullreference throws aNullPointerException.
Three nodes can be built from the back, so that each one can refer to the next:
val c = new ListNode(3)
val b = new ListNode(2, c)
val a = new ListNode(1, b) // a is the head of 1 -> 2 -> 3
Traversal
Almost every linked list operation starts with a loop that walks from the head until it falls off the end:
var count = 0
var node = a
while (node != null) {
count += 1
node = node.next
}
// count is 3
The walking variable has to be a var, since it is reassigned on every step. It's also a separate variable from a: if you moved a itself, you would lose the head. Counting this way takes O(n) time and O(1) extra space.
The core operations
Insert at the front
Create a node whose next is the old head. The new node is the new head. It takes constant time and does not depend on the length of the list.
val newHead = new ListNode(0, a) // 0 -> 1 -> 2 -> 3
Insert after a known node
Given a reference to node b, make the new node point to b.next first, then make b point to the new node. The order matters: if you set b.next first, the rest of the list is lost.
b.next = new ListNode(99, b.next) // 0 -> 1 -> 2 -> 99 -> 3
Delete the node after a known node
Skip over it by pointing b.next to b.next.next. Nothing refers to the skipped node any more, so the JVM can reclaim it.
b.next = b.next.next // 0 -> 1 -> 2 -> 3 again
This needs the node before the one you want to remove. In a singly linked list, a node has no way back to its predecessor, so you usually walk the list with a variable that stands one node behind the node being examined.
Search
Walk until you find the value or reach null. Search takes O(n) time, since there is no way to jump into the middle of the list.
var cur = newHead
while (cur != null && cur.`val` != 3) {
cur = cur.next
}
// cur is the node holding 3, or null if there is none
The test cur != null comes first and the test on cur.`val` second, because && stops as soon as the first part is false. Swapping them would read the field of a null reference at the end of the list.
| Operation | Linked list | Array |
|---|---|---|
Read element i | O(i) | O(1) |
| Insert or delete at the front | O(1) | O(n) |
| Insert or delete after a known node | O(1) | O(n) |
| Search for a value | O(n) | O(n) |
Techniques you will use in the chapter
- A dummy node. Deleting the head is a special case, because the head has no predecessor. Placing a throwaway node in front of the head removes that case: every real node then has a node before it. The Remove Linked List Elements lesson uses this.
- Several pointers. Reversing a list needs a variable for the previous node, one for the current node, and a saved copy of the next node. Rewriting a link without saving the rest of the list first cuts the list in two.
- Edge cases. An empty list is
null, so check for it before readinghead.next. A one-node list hasnext == null.
Scala's own List
Scala's standard List is also a linked list, but an immutable one. 0 :: xs builds a new list whose head is 0 and whose tail is the existing list xs, without copying it. xs.head and xs.tail read the first element and the rest. For xs = List(1, 2, 3), xs.head is 1 and xs.tail is List(2, 3). Calling head on an empty list throws a NoSuchElementException.
The lessons use their own mutable ListNode instead, because the point of the chapter is to practise changing links directly, which an immutable List doesn't allow.
Key takeaways
- A linked list is a chain of nodes, each holding a value and a reference to the next node. The head is the entry point, and
nullends the chain. - Reaching an element is
O(n), while insertion and deletion next to a known node areO(1). - Walk with a separate variable, and keep the head.
- When rewriting links, save what you are about to overwrite, or the rest of the list is lost.
- In Scala,
valas a field name needs backticks, and the end of the list is checked with!= null.
