func (c *Cache) moveToHead(n *node) {
	c.removeNode(n)
	c.addNode(n)
}
Moving a node to head means we first break its links,
and then add it to the cache as if it was a new node.
package main
import "fmt"
type node struct {
	key   string
	value string
	prev  *node
	next  *node
}
func newNode() node {
	return node{"", "", nil, nil}
}
type Cache struct {
	head *node
	tail *node
	cache *(map[string]*node)
	capacity int
}
func (c *Cache) popTail() *node {
	n := c.tail.prev
	if n == c.head {
		return nil
	}
	c.removeNode(n)
	return n
}
func (c *Cache) removeNode(n *node) {
	prev := n.prev
	next := n.next
	prev.next = next
	next.prev = prev
}
func (c *Cache) addNode(n *node) {
	n.prev = c.head
	n.next = c.head.next
	c.head.next.prev = n
	c.head.next = n
}