class Node {
    var key: Int
    var data: Int
    var prev: Node?
    var next: Node?
    
    init(key: Int, data: Int) {
        self.key = key
        self.data = data
    }
}

class Cache {
    let size = 3
    var currentSize = 0
    var head = Node(key: 0, data: 0)
    var tail = Node(key: 100, data: 100)
    var hashmap:[Int: Node] = [:]
    
    init() {
        head.next = tail
        tail.prev = head
    }
    
    func get(key: Int) -> Int?{
        if let node = hashmap[key] {
            remove(node)
            insert(node)
            return node.data
        } else {
            return nil
        }
    }
    
    func put(key: Int, data: Int) {
        if let node = hashmap[key] {
            remove(node)
            insert(node)
            node.data = data
        } else {
            if currentSize > size {
                if let key = tail.prev?.key {
                    hashmap[key] = nil
                }
                remove(tail.prev)
            }
            let node = Node(key: key, data: data)
            hashmap[key] = node
            insert(node)
        }
    }
    
    // remove the node
    func remove(node: Node!) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
        currentSize--
    }
    
    // insert the node to the head
    func insert(node: Node!) {
        node.next = head.next
        node.prev = head
        head.next = node
        node.next?.prev = node
        currentSize++
    }
}