class LRUCache {

    let capacity: Int

    var dict: [Int: Node] = [:]
    var cache = DoubleList()

    init(_ capacity: Int) {
        self.capacity = capacity
    }

    func get(_ key: Int) -> Int {
        guard let val = dict[key]?.val else {
            return -1
        }
        put(key, val)
        return val
    }

    func put(_ key: Int, _ value: Int) {
        let new = Node(key: key, val: value)
        if let node = dict[key] {
            cache.delete(node: node)
            cache.insert(node: new)
            dict[key] = new
        } else {
            cache.insert(node: new)
            if cache.size > capacity {
                if let last = cache.deleteLast() {
                    dict[last.key] = nil
                }
            }
            dict[key] = new
        }
    }
}