LRU Cache

package main
type Node struct {
    key, value int
    prev, next *Node
}
type LRUCache struct {
    capacity   int
    head, tail *Node
    cache      map[int]*Node
}
func Constructor(capacity int) LRUCache {
    head, tail := &Node{}, &Node{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity: capacity,
        head:     head,
        tail:     tail,
        cache:    make(map[int]*Node),
    }
}
func (t *LRUCache) Get(key int) int {
    node, exist := t.cache[key]
    if !exist {
        return -1
    }
    t.remove(node)
    t.insert(node)
    return node.value
}
func (t *LRUCache) Put(key int, value int) {
    if node, exist := t.cache[key]; exist {
        t.remove(node)
        t.insert(&Node{
            key:   key,
            value: value,
        })
        return
    }
    if len(t.cache) == t.capacity {
        t.remove(t.head.next)
    }
    t.insert(&Node{
        key:   key,
        value: value,
    })
}
func (t *LRUCache) insert(node *Node) {
    node.prev = t.tail.prev
    node.next = t.tail
    t.tail.prev.next = node
    t.tail.prev = node
    t.cache[node.key] = node
}
func (t *LRUCache) remove(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
    delete(t.cache, node.key)
}