Build An LRU Cache In Swift
An LRU cache is one of those algorithm problems that feels very practical once it clicks. We want a small cache with a fixed capacity. When it fills up, we remove the least recently used item so there is room for the new one.
In other words, every successful read and every write makes a key “recent” again. The oldest untouched key is the one that gets evicted.
Here is the behavior we want:
let cache = LRUCache<String, Int>(capacity: 2)
cache.put("a", 1) // recency: a
cache.put("b", 2) // recency: b, a
cache.get("a") // recency: a, b
cache.put("c", 3) // evicts b, recency: c, a
cache.get("b") // nil
cache.get("a") // 1
cache.get("c") // 3We need two operations:
get(key): return the value if it exists, and mark that key as recently used.put(key, value): insert or update the value, mark it as recently used, and evict the least recently used key if we are over capacity.
The trick is that both operations should be fast. A dictionary gives us fast lookup by key, but it does not tell us which key is oldest. An array can track recency, but moving an item from the middle to the front costs O(n).
So we combine two structures:
- A dictionary from
Keyto a linked-list node. - A doubly linked list ordered from most recent at the head to least recent at the tail.
The dictionary finds the node in O(1). The linked list moves that node to the front in O(1). The tail is the least recently used node, so eviction is also O(1).
The node
Let’s start with the node. It needs to store the key and value, plus links in both directions.
private final class CacheNode<Key, Value> {
let key: Key
var value: Value
weak var previous: CacheNode?
var next: CacheNode?
init(key: Key, value: Value) {
self.key = key
self.value = value
}
}This is a class on purpose. List nodes are identity objects. When the dictionary and the linked list point at the same node, we want mutations to affect that shared object. A struct would make this pointer-style list much harder to manage.
The previous reference is weak because Swift uses ARC. If both previous and next were strong references, neighboring nodes could keep each other alive after the cache is gone. Keeping the backward link weak is a simple way to avoid that retain cycle.
The node stores the key, not just the value. When we evict the tail node, we need to remove the matching dictionary entry:
storage[node.key] = nilThe cache shell
Now we can define the cache itself:
final class LRUCache<Key: Hashable, Value> {
private let capacity: Int
private var storage: [Key: CacheNode<Key, Value>] = [:]
private var head: CacheNode<Key, Value>?
private var tail: CacheNode<Key, Value>?
init(capacity: Int) {
precondition(capacity > 0, "LRUCache capacity must be positive")
self.capacity = capacity
storage.reserveCapacity(capacity)
}
}Key must be Hashable because it is used in a dictionary. I like making invalid capacity a programmer error with precondition. You could allow a capacity of zero, but a positive capacity keeps this version clean.
Moving nodes around
Before writing get and put, let’s add the linked-list helpers.
extension LRUCache {
private func addToFront(_ node: CacheNode<Key, Value>) {
node.previous = nil
node.next = head
head?.previous = node
head = node
if tail == nil {
tail = node
}
}
private func remove(_ node: CacheNode<Key, Value>) {
let previous = node.previous
let next = node.next
if let previous {
previous.next = next
} else {
head = next
}
if let next {
next.previous = previous
} else {
tail = previous
}
node.previous = nil
node.next = nil
}
private func moveToFront(_ node: CacheNode<Key, Value>) {
guard head !== node else {
return
}
remove(node)
addToFront(node)
}
private func evictLeastRecentlyUsed() {
guard let node = tail else {
return
}
remove(node)
storage[node.key] = nil
}
}The linked list is ordered like this:
head tail
most recent -> ... -> least recentaddToFront also handles the empty-list case. If there is no tail yet, the node we added is both head and tail.
remove has to handle a middle node, the head, the tail, and the only node. The branches reconnect neighbors and update head or tail as needed.
moveToFront is remove plus add. If the node is already the most recent one, there is nothing to do.
Implementing get
get is short because the helpers did the list work for us.
extension LRUCache {
func get(_ key: Key) -> Value? {
guard let node = storage[key] else {
return nil
}
moveToFront(node)
return node.value
}
}A cache miss does not change recency. A cache hit does. That is the whole point of LRU: using a value protects it from being evicted next.
Implementing put
put has two paths. Updating an existing key should replace the value and refresh recency. Inserting a new key should add a new node, then evict if we crossed the capacity.
extension LRUCache {
func put(_ key: Key, _ value: Value) {
if let node = storage[key] {
node.value = value
moveToFront(node)
return
}
let node = CacheNode(key: key, value: value)
storage[key] = node
addToFront(node)
if storage.count > capacity {
evictLeastRecentlyUsed()
}
}
}That gives us the complete cache. The dictionary owns lookup. The list owns recency. Every inserted node must be added to both structures, and every evicted node must be removed from both.
Full implementation
Here is the whole thing in one piece:
private final class CacheNode<Key, Value> {
let key: Key
var value: Value
weak var previous: CacheNode?
var next: CacheNode?
init(key: Key, value: Value) {
self.key = key
self.value = value
}
}
final class LRUCache<Key: Hashable, Value> {
private let capacity: Int
private var storage: [Key: CacheNode<Key, Value>] = [:]
private var head: CacheNode<Key, Value>?
private var tail: CacheNode<Key, Value>?
init(capacity: Int) {
precondition(capacity > 0, "LRUCache capacity must be positive")
self.capacity = capacity
storage.reserveCapacity(capacity)
}
func get(_ key: Key) -> Value? {
guard let node = storage[key] else {
return nil
}
moveToFront(node)
return node.value
}
func put(_ key: Key, _ value: Value) {
if let node = storage[key] {
node.value = value
moveToFront(node)
return
}
let node = CacheNode(key: key, value: value)
storage[key] = node
addToFront(node)
if storage.count > capacity {
evictLeastRecentlyUsed()
}
}
private func addToFront(_ node: CacheNode<Key, Value>) {
node.previous = nil
node.next = head
head?.previous = node
head = node
if tail == nil {
tail = node
}
}
private func remove(_ node: CacheNode<Key, Value>) {
let previous = node.previous
let next = node.next
if let previous {
previous.next = next
} else {
head = next
}
if let next {
next.previous = previous
} else {
tail = previous
}
node.previous = nil
node.next = nil
}
private func moveToFront(_ node: CacheNode<Key, Value>) {
guard head !== node else {
return
}
remove(node)
addToFront(node)
}
private func evictLeastRecentlyUsed() {
guard let node = tail else {
return
}
remove(node)
storage[node.key] = nil
}
}Tests
I would test this through the public API. The outside behavior is what matters.
import XCTest
final class LRUCacheTests: XCTestCase {
func testEvictsLeastRecentlyUsedItem() {
let cache = LRUCache<String, Int>(capacity: 2)
cache.put("a", 1)
cache.put("b", 2)
XCTAssertEqual(cache.get("a"), 1)
cache.put("c", 3)
XCTAssertNil(cache.get("b"))
XCTAssertEqual(cache.get("a"), 1)
XCTAssertEqual(cache.get("c"), 3)
}
func testUpdatingExistingKeyRefreshesRecency() {
let cache = LRUCache<String, Int>(capacity: 2)
cache.put("a", 1)
cache.put("b", 2)
cache.put("a", 10)
cache.put("c", 3)
XCTAssertEqual(cache.get("a"), 10)
XCTAssertNil(cache.get("b"))
XCTAssertEqual(cache.get("c"), 3)
}
func testCacheMissDoesNotChangeRecency() {
let cache = LRUCache<String, Int>(capacity: 2)
cache.put("a", 1)
cache.put("b", 2)
XCTAssertNil(cache.get("missing"))
cache.put("c", 3)
XCTAssertNil(cache.get("a"))
XCTAssertEqual(cache.get("b"), 2)
XCTAssertEqual(cache.get("c"), 3)
}
}Those tests cover the big rules: reads and updates refresh recency, misses do not, and inserting past capacity evicts exactly one old item.
What about OrderedDictionary?
If you are building app code and mainly want a dictionary that remembers order, Swift Collections has OrderedDictionary, and it is worth knowing about. For small or moderate app-level caches, an OrderedDictionary version can be easier to read: remove a key and reinsert it when accessed, then remove the oldest key when the count grows past capacity.
I would not treat it as the canonical answer to the LRU algorithm problem, though. The point here is learning the shape: hash table for lookup, linked list for recency. OrderedDictionary can still be the better app-level choice when clarity matters more than building the data structure yourself.
Complexity
get is O(1) average time because dictionary lookup is O(1) average time, and moving a known node to the front is O(1).
put is also O(1) average time. Updating an existing node is lookup plus move-to-front. Inserting a new node is dictionary insertion plus adding to the front. Eviction removes the tail node and deletes its dictionary entry.
Space complexity is O(capacity). The cache stores at most capacity dictionary entries and capacity linked-list nodes.
That is the nice little lesson inside an LRU cache: the dictionary gives us fast access, the linked list gives us fast recency updates, and together they keep the important operations constant time.
