type listNode struct {
	key int
	val int
	prev *listNode
	next *listNode
}

type linkedList struct {
	head *listNode
	tail *listNode
}

func newLinkedList() *linkedList {
	head, tail := &listNode{}, &listNode{}
	head.next = tail
	tail.prev = head
	li := &linkedList{head, tail}
	return li
}

func (li *linkedList) remove(node *listNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (li *linkedList) insert(node *listNode) {
	node.next = li.head.next
	node.prev = li.head
	li.head.next = node
	node.next.prev = node
}

type LRUCache struct {
	capacity int
	size     int
	cache    map[int]*listNode
	list     *linkedList
}

func Constructor(capacity int) LRUCache {
	var lru LRUCache
	lru.capacity = capacity
	lru.cache = make(map[int]*listNode)
	lru.list = newLinkedList()
	return lru
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.list.remove(node)
		this.list.insert(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int)  {
	if this.capacity == 0 {
		return
	}
	if node, ok := this.cache[key]; ok {
		this.list.remove(node)
		this.list.insert(node)
		node.val = value
		return
	}
	if this.size == this.capacity {
		node := this.list.tail.prev
		delete(this.cache, node.key)
		this.list.remove(node)
		this.size--
	}
	newNode := &listNode{key, value, nil, nil}
	this.list.insert(newNode)
	this.cache[key] = newNode
	this.size++
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */