What a linked list is
A singly linked list is a sequence of values stored in separate objects called nodes. Each node holds one value and a reference to the next node. The first node is the head, and the last node has no next node: its reference is null. The only way to reach a node is to start at the head and follow the references one by one.
That is the main difference from an array. An array keeps its elements side by side and lets you jump to index k in one step. A linked list lets you insert or remove a node, once you hold the node before it, by changing one or two references, without shifting anything else. The price is that finding the k-th node means walking k steps.
A node in Kotlin
A node is a small class with a value and a nullable reference to the next node. The chapter's lessons use a class named ListNode, which can be written like this:
class ListNode(var `val`: Int = 0) {
var next: ListNode? = null
}
ListNode?means "a node ornull". Kotlin separates nullable from non-nullable types. The end of the list is represented bynull, sonexthas to be nullable, and so does any variable that walks along the list.- Backticks around
val.valis a Kotlin keyword. A property calledvalmust be written with backticks wherever it is used:node.`val`. - Default parameter. Because of
= 0, bothListNode()andListNode(5)are valid. An emptyListNode()is a handy placeholder node, as the lessons show later.
A list is built by linking nodes:
val head = ListNode(1)
head.next = ListNode(2)
head.next!!.next = ListNode(3)
This creates 1 -> 2 -> 3 -> null. The !! in the last line asserts that head.next is not null, which is true because it was just assigned.
Traversal
To visit every node, keep a variable for the current node and move it forward until it becomes null:
fun printList(head: ListNode?) {
var node = head
while (node != null) {
print("${node.`val`} -> ")
node = node.next
}
println("null")
}
On the list above, this prints:
1 -> 2 -> 3 -> null
The variable node is a var, because it is reassigned in the loop, and Kotlin infers its type ListNode? from head. Inside the loop, the check node != null lets Kotlin treat node as a non-null ListNode, so node.next compiles without !!. Counting the nodes works the same way, with a counter that goes up by one per step.
Insertion and deletion
Changing a list means changing next references. The order of the assignments matters, because a reference you overwrite is a reference you lose.
- Insert at the front. Create the new node, point its
nextat the old head, and treat the new node as the head. This takes constant time. - Insert after a node. Point the new node at
node.nextfirst, and only then pointnode.nextat the new node. Doing it the other way round loses the rest of the list. - Delete the node after
node. Setnode.next = node.next?.next. Nothing refers to the skipped node afterwards, so it is no longer part of the list.
val newHead = ListNode(0)
newHead.next = head // 0 -> 1 -> 2 -> 3
val inserted = ListNode(9)
inserted.next = head.next // 9 points at 2
head.next = inserted // 0 -> 1 -> 9 -> 2 -> 3
head.next = head.next?.next // 0 -> 1 -> 2 -> 3 again
Each of these operations is O(1) when you already hold the right node. Finding that node is what costs O(n).
How the operations compare with an array
| Operation | Linked list | Array |
|---|---|---|
Read the k-th element | O(k), a walk from the head | O(1) |
| Insert or remove at the front | O(1) | O(n), everything shifts |
| Insert or remove after a known node | O(1) | O(n) |
| Search for a value | O(n) | O(n) |
| Memory per element | value plus a reference | value only |
Kotlin gotchas
- No smart cast through
next. Writingif (head.next != null) println(head.next.`val`)does not compile. The compiler reports:smart cast to 'ListNode' is impossible, because 'next' is a mutable property that could be mutated concurrently.Usehead.next!!.`val`, a safe callhead.next?.`val`, or copy the reference into a localvalfirst. A local variable can be smart-cast, which is why traversal usesnodeand nothead.nextdirectly. - Safe calls for chains.
head.next?.next?.next?.`val`givesnullif any link on the way is missing, and?: -1supplies a default. On the list1 -> 2 -> 3, the first form givesnulland the second gives-1. - Overwriting a reference loses the nodes behind it. Before changing
node.next, save the old value in a variable if you still need it. Nearly every list algorithm in this chapter follows from that rule. !!throws on null. Callinghead!!.nextwhenheadis null throws aNullPointerException. Use it only where the list cannot be empty.- Cycles. If a node's
nextleads back to an earlier node, a traversal loop never reachesnulland never ends. Cutting the last link, withnext = null, matters when you rearrange nodes. - Equality of nodes. A plain class has reference equality: two separate
ListNode(1)objects are not equal under==. Compare thevalfields to compare contents.
Patterns the chapter builds on
- A dummy node. A placeholder
ListNode()placed in front of the head means that the first real node also has a node before it, so removing the head needs no special case. - Two references. Keeping the previous and the current node, or two nodes a fixed distance apart, lets you change links safely or find positions such as "the node
nfrom the end". - Update in the right order. Save the next node, change the link, then move on. Reversing a list and removing nodes both depend on this order.
Key takeaways
- A linked list is a chain of nodes, each with a value and a nullable
next; the head is the entry point andnullmarks the end. - Access by position needs a walk, while insertion and removal next to a known node are constant time.
- In Kotlin, walkers have the type
ListNode?, thevalfield needs backticks, and!!or?.handle the nullable links. - When rewiring links, copy the reference you are about to overwrite, so you never lose the rest of the list.