What a linked list is
A linked list stores a sequence of values as a chain of small 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's reference is empty (nil in Swift). The list is reached only through its head, and every other node is found by following the references.
An array keeps its elements next to each other and finds element k directly. A linked list has no such shortcut: to reach the k-th node you follow k links. In exchange, inserting or removing a node in the middle changes only a reference or two, and no elements have to shift. The lists in this chapter are singly linked: each node knows only its successor, so you can only walk forward.
A node in Swift
A node needs a value and an optional reference to the next node. Because a node must be shared and changed through several references, it is a class, not a struct:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
The type ListNode? is an optional: it holds either a node or nil. That is how the end of the list is marked, and it is why the lesson methods take head: ListNode?, since an empty list is simply a nil head. The lesson's own ListNode also has an initializer with no arguments, which creates a node with value 0, and the exercises use it for placeholder nodes.
A class is a reference type. Two variables can refer to the same node, and a change made through one is visible through the other. A struct would be copied on assignment, and a struct cannot contain an optional of its own type directly, so a list of structs wouldn't work.
let a = ListNode(5)
let b = a
b.val = 6
print(a.val) // 6
Building a list
To make the list 1 -> 2 -> 3, create the nodes and link them:
let head = ListNode(1)
head.next = ListNode(2)
head.next!.next = ListNode(3)
The last line uses head.next! to force-unwrap the second node. That is safe here because the line before just set it. When you are not sure a link exists, use optional chaining, which gives nil instead of crashing: head.next?.next?.val evaluates to Optional(3) for this list, and to nil if either link is missing.
Traversal
Visiting every node is a loop that follows the links until it falls off the end:
var node: ListNode? = head
while let current = node {
print(current.val, terminator: " ")
node = current.next
}
This prints 1 2 3 . while let unwraps the optional and stops the loop when it is nil, so no ! is needed. Traversal visits n nodes, so it takes O(n) time. Finding the k-th node costs O(k), and a search for a value is O(n) in the worst case.
Inserting and removing
With a reference to a node, changing the list near it costs a few assignments, O(1):
- Insert at the front. Create a node, set its
nextto the old head, and use the new node as the head. - Insert after a node
p. Set the new node'snexttop.nextfirst, then setp.nextto the new node. In the other order, the rest of the list is lost. - Remove the node after
p. Setp.next = p.next?.next. Nothing refers to the skipped node afterwards, and Swift frees it automatically.
let inserted = ListNode(9)
inserted.next = head.next // 9 -> 2 -> 3
head.next = inserted // 1 -> 9 -> 2 -> 3
head.next = head.next?.next // 1 -> 2 -> 3 again
Removing a node requires the node before it, because that node holds the reference to change. A singly linked list can't go backwards to find it, so exercises usually walk one step behind the node they are looking at.
Common mistakes
- Losing the rest of the list. Overwriting a
nextbefore saving where it pointed leaves the following nodes unreachable. Store the old reference first. - Unwrapping
nil.node!.nextcrashes whennodeisnil. Check first, or useif let,guard letand?.. - Forgetting the empty list. A
nilhead is a valid list, and code that starts withhead!crashes on it. - Cycles. A node whose
nextleads back to an earlier node makes a traversal loop forever. This usually comes from forgetting to cut a link while rewiring. - Treating a reference as a copy.
let b = adoesn't copy the node: both names refer to one object.
Key takeaways
- A linked list is a chain of nodes, each with a value and an optional
next, reached through the head. - In Swift a node is a class, so references are shared, and
ListNode?marks the end of the list withnil. - Reading the
k-th node takesO(k), while insertion and removal next to a known node takeO(1). - Most list exercises come down to traversing with a pointer, keeping one node behind, and updating
nextin the right order.
