LRUCache.swift

final class Node<Key: Hashable, Value> {
    let key: Key?
    let value: Value
    var prev: Node?
    var next: Node?
    
    init(value: Value, key: Key?) {
        self.value = value
        self.key = key
    }
}

final class LinkedList<Key: Hashable, Value> {
    fileprivate let head: Node<Key, Value>
    fileprivate let tail: Node<Key, Value>
    
    private var prev: Node<Key, Value>?
    private var next: Node<Key, Value>?
    
    init(head: Node<Key, Value>, tail: Node<Key, Value>) {
        self.head = head
        self.tail = tail
        self.head.next = self.tail
        self.tail.prev = self.head
    }
    
    func getHead() -> Node<Key, Value>? {
        return head.next
    }
    
    func getTail() -> Node<Key, Value>? {
        return tail.prev
    }
    
    func add(_ node: Node<Key, Value>) {
        prev = tail.prev
        prev?.next = node
        node.prev = prev
        node.next = tail
        tail.prev = node
    }
    
    func remove(_ node: Node<Key, Value>?) {
        prev = node?.prev
        next = node?.next
        prev?.next = next
        next?.prev = prev
    }
}

final class LRUCache<Key: Hashable, Value> {
    
    private var dict: [Key: Node<Key, Value>] = [:]
    private let list: LinkedList<Key, Value>
    
    let capacity: Int
    
    init(capacity: Int, list: LinkedList<Key, Value>) {
        self.capacity = capacity
        self.list = list
    }
    
    func setValue(_ value: Value, for key: Key) {
        if dict.keys.contains(key) {
            dict[key] = nil
        }
        let node = Node(value: value, key: key)
        list.add(node)
        dict[key] = node
        
        if dict.count > capacity {
            let head = list.getHead()
            list.remove(head)
            dict[head!.key!] = nil
        }
    }
    
    func getValue(for key: Key) -> Value? {
        guard dict.keys.contains(key) else {
            return nil
        }
        let node = dict[key]!
        list.remove(node)
        list.add(node)
        return node.value
    }
}

extension LRUCache: CustomDebugStringConvertible where Value: LosslessStringConvertible {
    var debugDescription: String {
        var current: Node? = list.head
        var values = [Value]()
        while current != nil {
            if let value = current?.value {
                values.append(value)
            }
            current = current?.next
        }
        return values.map({String($0)}).joined(separator: "->")
    }
}