-
Notifications
You must be signed in to change notification settings - Fork 0
004 — Linked Lists
Arrays are a parking garage — fixed spots, instant access. Linked lists throw that away entirely and buy something different: cheap insertion and removal, anywhere, at the cost of never being able to jump straight to an index.
Picture a train: a line of cars, each one coupled only to the car directly behind it. You're standing at the front, and someone asks "what's in car 47?" You have no choice but to walk car by car — 1, 2, 3... — counting couplings until you reach it. There's no shortcut, no jumping straight there.
But now suppose the railway wants to insert a new car between car 12 and car 13. They don't need to shift cars 13 through 47 down the track to make room — they just uncouple car 12 from car 13, couple car 12 to the new car, and couple the new car to car 13. Three coupling changes, done, regardless of how long the train is.
That's the whole trade: slow to reach a position, fast to splice once you're there.
A linked list is a sequence of nodes, where each node holds a value and a reference (pointer) to the next node. There's no contiguous memory and no index arithmetic — to get to the 5th node, you must walk through nodes 1 through 4 first.
- A singly linked list has one pointer per node:
next. You can only walk forward. - A doubly linked list adds a
prevpointer too, so you can walk backward and delete a node inO(1)if you already have a reference to it (no need to re-find its predecessor).
Swift removed Array-like built-in linked lists from the standard library — there's no LinkedList<T> in stdlib. If you need one, you build it, which is exactly why interviews love asking for it.
Reach for a linked list when:
- You're inserting/removing at the front constantly (
O(1), vs. an array'sO(n)shift). - You're building something like an LRU cache, where you need
O(1)removal of an arbitrary node once you've located it (a doubly linked list + hash map combo is the classic implementation). - You need to represent a sequence where you'll be splicing pieces in and out a lot, and you don't care about random access.
Skip it when you need frequent access by index, or good cache locality (contiguous arrays are much friendlier to CPU caches — linked list nodes can be scattered anywhere in memory).
Singly linked list:
head tail
│ │
▼ ▼
┌────┬────┐ ┌────┬────┐ ┌────┬────┐ ┌────┬──────┐
│ 10 │ ●──┼───▶│ 25 │ ●──┼───▶│ 7 │ ●──┼───▶│ 42 │ nil │
└────┴────┘ └────┴────┘ └────┴────┘ └────┴──────┘
node 1 node 2 node 3 node 4
To read node 3's value (7), you MUST walk head → node1 → node2 → node3.
No shortcuts — that's O(n) access.
Doubly linked list — pointers both ways:
head tail
│ │
▼ ▼
┌──────┬────┬────┐ ┌────┬────┬────┐ ┌────┬────┬──────┐
│ nil │ 10 │ ●──┼───▶│ ● │ 25 │ ●──┼───▶│ ● │ 7 │ nil │
│ │ │ │◀───┼──● │ │ │◀───┼──● │ │ │
└──────┴────┴────┘ └────┴────┴────┘ └────┴────┴──────┘
prev val next prev val next prev val next
There's no stdlib equivalent — this hand-rolled version is the implementation. Nodes need reference semantics (so links actually point to shared, mutable objects), so Node is a class, not a struct.
final class Node<T> {
var value: T
var next: Node<T>?
init(_ value: T) {
self.value = value
}
}
final class SinglyLinkedList<T> {
private var head: Node<T>?
private var tail: Node<T>?
private(set) var count = 0
// O(1) — just relink the front
func prepend(_ value: T) {
let newNode = Node(value)
newNode.next = head
head = newNode
if tail == nil { tail = newNode }
count += 1
}
// O(1) — thanks to keeping a tail pointer
func append(_ value: T) {
let newNode = Node(value)
if let tail = tail {
tail.next = newNode
} else {
head = newNode
}
tail = newNode
count += 1
}
// O(n) — must walk to the index first
func insert(_ value: T, at index: Int) {
precondition(index >= 0 && index <= count, "Index out of range")
if index == 0 { return prepend(value) }
if index == count { return append(value) }
var current = head
for _ in 0..<(index - 1) {
current = current?.next
}
let newNode = Node(value)
newNode.next = current?.next
current?.next = newNode
count += 1
}
// O(n) — must walk to find the value
func remove(_ value: T) where T: Equatable {
guard let head = head else { return }
if head.value == value {
self.head = head.next
if self.head == nil { tail = nil }
count -= 1
return
}
var previous = head
var current = head.next
while let node = current {
if node.value == value {
previous.next = node.next
if node === tail { tail = previous }
count -= 1
return
}
previous = node
current = node.next
}
}
// O(n) — no shortcuts, walk from the head
func node(at index: Int) -> Node<T>? {
precondition(index >= 0 && index < count, "Index out of range")
var current = head
for _ in 0..<index {
current = current?.next
}
return current
}
}| Operation | Big-O | Why |
|---|---|---|
| Prepend (add at front) | O(1) |
Just relink head — no shifting, unlike an array. See Big-O Notation. |
| Append (add at end) | O(1) |
Only true if you maintain a tail pointer; otherwise it's O(n) to walk and find the end. |
| Insert at known index | O(n) |
You must walk index nodes to get there before the O(1) relink happens. |
| Insert given a node reference (doubly linked) | O(1) |
No walking needed — you already hold the node, just relink its neighbors. |
| Access by index | O(n) |
No index arithmetic exists — you must walk node by node. Contrast with an array's O(1). |
| Search by value | O(n) |
Same story — walk until you find it or hit nil. |
| Delete (given the node, doubly linked) | O(1) |
With prev and next both available, relinking the neighbors takes constant work. |
A linked list is a train of cars coupled one to the next — splice a new car in anywhere without moving the rest of the train, but you can only ever walk it car by car.
The SinglyLinkedList above keeps a tail pointer specifically to make append O(1). Explain why that same trick does not give you O(1) removal of the last node (i.e., removeLast()), even though you have direct access to tail. What would you need to add to the node or the list to fix that?