LRUCache

class LRUCache<T> {
    
    init(capicity: Int) {
        self.capicity = capicity
        self.head.connectNext(tail)
    }
    
    func set(_ object: T, for key: AnyHashable) {
        let newNode = LinkNode(object, key)
        
        if let oldNode = dict[key] {
            oldNode.removeFromChain()
        }
        
        dict[key] = newNode
        head.insertNext(newNode)
        fixCapicity()
    }
    func object(for key: AnyHashable) -> T? {
        guard let node = dict[key] else {
            return nil
        }
        node.removeFromChain()
        head.insertNext(node)
        return node.content
    }
    
    private class LinkNode {
        let content:T?
        let key: AnyHashable?
        var previous: LinkNode?
        var next: LinkNode?
        
        
        init(_ content: T?, _ key: AnyHashable?) {
            self.content = content
            self.key = key
        }
        func connectNext(_ next: LinkNode?) {
            self.next = next
            next?.previous = self
        }
        func insertNext( _ next: LinkNode) {
            let old = self.next
            next.connectNext(old)
            self.connectNext(next)
        }
        func removeFromChain() {
            self.previous?.connectNext(self.next)
        }
    }
    
    private var capicity: Int
    private var dict: [AnyHashable: LinkNode] = [:]
    private var head: LinkNode = LinkNode(nil, nil)
    private var tail: LinkNode = LinkNode(nil, nil)
    
    private func fixCapicity() {
        if dict.count <= capicity {
            return
        }
        if tail.previous !== head, let toRemove = tail.previous, let key = toRemove.key{
            toRemove.removeFromChain()
            dict.removeValue(forKey: key)
        }
    }
    func print() {
        var s = "Chain:"
        var n = head
        while let next = n.next {
            s += "-> \(String(describing: next.content)) "
            n = next
        }
        Swift.print(s, dict.count)
    }
}

// usage
let cache = LRUCache<Int>(capicity: 3)
cache.set(1, for: "1")
cache.print()
cache.set(2, for: "2")
cache.print()
cache.set(3, for: "3")
cache.print()
cache.set(4, for: "4")
cache.print()
cache.object(for: "2")
cache.print()