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

type biList struct {
	head *biNode
	tail *biNode
}

func newBiList() *biList {
	head, tail := &biNode{}, &biNode{}
	head.next = tail
	tail.prev = head
	li := &biList{head, tail}
	return li
}

func (li *biList) remove(node *biNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (li *biList) insert(node *biNode) {
	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]*biNode
	list     *biList
}

func Constructor(capacity int) LRUCache {
	var lru LRUCache
	lru.capacity = capacity
	lru.cache = make(map[int]*biNode)
	lru.list = newBiList()
	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 := &biNode{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);
 */