LRU Cache Implementation (iOS) — Using Arrays

Caching is an essential technique in software development, especially when optimizing performance for frequently accessed data. One of the most popular caching algorithms is the Least Recently Used (LRU) Cache. It efficiently manages memory by evicting the least recently used item when the cache reaches capacity.

In this blog, we will implement an LRU Cache in Swift using Arrays, making it simple and easy for iOS developers to understand.

What is an LRU Cache?

An LRU Cache is a data structure that stores a limited number of elements. When it reaches its capacity, it removes the least recently used element to make space for new ones. This ensures that frequently used items remain accessible while older, less-used items get discarded.

Key Operations:

• get(key): Retrieves the value of the key and marks it as most recently used.
• put(key, value): Adds a new key-value pair and, if the cache is full, removes the least recently used entry.

Implementation in Swift (Using Arrays):

We will use two primary data structures:

1. Dictionary (cache) → For O(1) access to values.
2. Array (order) → To track the usage order of keys.

import Foundation

class LRUCache<Key: Hashable, Value> {
    private var cache: [Key: Value] = [:]
    private var order: [Key] = []
    private let capacity: Int

    /// Initializes the LRU cache with a given capacity.
    init(capacity: Int) {
        self.capacity = capacity
    }

    /// Retrieves a value from the cache and marks it as most recently used.
    /// - Parameter key: The key of the item to retrieve.
    /// - Returns: The value associated with the key, or nil if not found.
    func get(_ key: Key) -> Value? {
        guard let value = cache[key] else { return nil }
        moveToRecent(key)
        return value
    }

    /// Inserts a key-value pair into the cache.
    /// If the cache is full, the least recently used item is removed.
    /// - Parameters:
    ///   - key: The key to insert.
    ///   - value: The value associated with the key.
    func put(_ key: Key, _ value: Value) {
        if cache[key] != nil {
            moveToRecent(key)
        } else {
            if cache.count >= capacity, let leastUsedKey = order.first {
                cache.removeValue(forKey: leastUsedKey)
                order.removeFirst()
            }
            order.append(key)
        }
        cache[key] = value
    }

    /// Moves a key to the most recently used position in the order array.
    /// - Parameter key: The key to move.
    private func moveToRecent(_ key: Key) {
        order.removeAll { $0 == key }
        order.append(key)
    }

    func printCache() {
        print("Cache: \(cache)")
        print("Order: \(order)")
    }
}

🔹 How Does It Work?

Let’s walk through an example with a capacity of 3:

Operations & Step-by-Step Execution:

1️⃣ put("A", 1) → Add "A" with value 1
Cache = {A: 1}
Order (Most recent at end) = A

2️⃣ put("B", 2) → Add "B" with value 2
Cache = {A: 1, B: 2}
Order (Most recent at end) = A, B

3️⃣ put("C", 3) → Add "C" with value 3
Cache = {A: 1, B: 2, C: 3}
Order (Most recent at end) = A, B, C

4️⃣ get("A") → Access "A" (moves to most recent)
Cache = {A: 1, B: 2, C: 3}
Order (Most recent at end) = B, C, A

5️⃣ put("D", 4) → Add "D" (removes LRU item "B")
Cache = {A: 1, C: 3, D: 4}
Order (Most recent at end) = C, A, D

Observation:

• Most recently used keys are moved to the end of the order array.
• Least recently used keys are at the beginning of the order array and get evicted when needed.

🚀 Performance Analysis

• get(key) : O(n) (due to array removal & append)
• put(key, value) : O(n) (due to array manipulation)

Potential Optimizations

This approach is simple, but not the most efficient for large-scale use. If you want O(1) time complexity, consider using a Doubly Linked List with a Dictionary, which avoids costly array operations.

When to Use This Implementation?

✅ Use this approach when:

• The cache size is small (e.g., under 100 items).
• You don’t want to deal with pointers & linked lists.

❌ Avoid this approach when:

• The cache is large (1000+ items) → use a Doubly Linked List + Dictionary instead.
• Performance is critical, as O(n) removals can be costly.

Happy Coding Folks!