LeetCode LRU算法实现

type Node struct {
	key, val   int
	next, prev *Node
}

func NewNode(k, v int) *Node {
	return &Node{key: k, val: v}
}

type DoubleList struct {
	head, tail *Node
	size       int
}

func NewDoubleList() *DoubleList {
	head := &Node{key: 0, val: 0}
	tail := &Node{key: 0, val: 0}
	head.next, tail.prev = tail, head
	return &DoubleList{
		head: head,
		tail: tail,
		size: 0,
	}
}
func (this *DoubleList) AddLast(n *Node) {
	n.prev = this.tail.prev
	n.next = this.tail
	this.tail.prev.next = n
	this.tail.prev = n
	this.size++
}

func (this *DoubleList) Remove(n *Node) {
	n.prev.next = n.next
	n.next.prev = n.prev
	n.prev = nil
	n.next = nil
	this.size--
}

// 删除链表中的第一个节点并且返回这个节点
func (this *DoubleList) RemoveFirst() *Node {
	if this.head.next == this.tail {
		return nil
	}
	node := this.head.next
	this.Remove(node)
	return node
}

func (this *DoubleList) Size() int {
	return this.size
}

type LRUCache struct {
	_map  map[int]*Node
	cache *DoubleList
	cap   int
}


func Constructor(capacity int) LRUCache {
    	return LRUCache{
		_map:  make(map[int]*Node),
		cache: NewDoubleList(),
		cap:   capacity,
	}
}

func (this *LRUCache) makeRecently(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	this.cache.AddLast(x)
}

func (this *LRUCache) addRecently(key, val int) {
	node := NewNode(key, val)
	this._map[key] = node
	this.cache.AddLast(node)
}

func (this *LRUCache) deleteKey(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	delete(this._map, key)
}

func (this *LRUCache) removeLastRecently() {
	deleteNode := this.cache.RemoveFirst()
	deletedKey := deleteNode.key
	delete(this._map, deletedKey)
}
func (this *LRUCache) Get(key int) int {
    	if _, ok := this._map[key]; !ok {
		return -1
	}
	this.makeRecently(key)
	return this._map[key].val
}


func (this *LRUCache) Put(key int, value int)  {
    if _, ok := this._map[key]; ok {
		this.deleteKey(key)
		this.addRecently(key, value)
		return
	}
	if this.cache.Size() == this.cap {
		this.removeLastRecently()
	}
	this.addRecently(key, value)
}


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