题解 | #设计LRU缓存结构#

package main

// 手动实现LRU&时间复杂度为1.
// 双端有序列表 + hashMap.
// get & set -> 时间复杂度为1; -> HashMap
// set的时候需要弹出最不常用的元素； -> 根据元素的顺序排列
// 每次get;set都用把元素放到最高优先级；放到队列末尾
//调试代码难；做好把拆分方法的；尽量复用性高
type dataNode struct {
	Key  int
	Val  int
	pre  *dataNode
	next *dataNode
}
type Solution struct {
	// write code here
	HashStorage map[int]*dataNode //节点值指向具体的节点
	Cap         int               //容量
	Head        *dataNode         //双端列表的头
	Tail        *dataNode         //双端列表的尾
}

func Constructor(capacity int) Solution {
	// write code here
	return Solution{
		HashStorage: make(map[int]*dataNode),
		Cap:         capacity,
		Head:        nil,
		Tail:        nil,
	}
}

func (this *Solution) get(key int) int {
	// write code here
	node, ok := this.HashStorage[key]
	if !ok {
		return -1
	}

	//添加到队列的末尾
	this.moveNodeToTheEnd(node)
	return node.Val
}
func (this *Solution) moveNodeToTheEnd(node *dataNode) {
	if this.Tail == node {
		return
	}
	//前后节点建立链接；保证有效
	//从原先的位置删除
	this.deleteFromList(node)

	//放到后面
	this.addNodeToEnd(node)
}

func (this *Solution) deleteFromList(node *dataNode) {
	//唯一元素
	if this.Head == node && this.Tail == node {
		this.Head = nil
		this.Tail = nil
		return
	}
	//队尾？
	if this.Tail == node {
		if this.Tail.pre != nil {
			this.Tail.pre.next = nil
		}
		this.Tail = this.Tail.pre
		return
	}
	//队首
	if this.Head == node {
		if this.Head.next != nil {
			this.Head.next.pre = nil
		}
		this.Head = this.Head.next
		return
	}
	//队中
	node.pre.next, node.next.pre = node.next, node.pre
}

// 队尾添加元素
func (this *Solution) addNodeToEnd(node *dataNode) {
	if this.Head == nil && this.Tail == nil {
		this.Head = node
		this.Tail = node
		return
	}
	//加到队尾
	this.Tail.next = node
	node.pre = this.Tail
	node.next = nil
	this.Tail = node //节点变成最后一个节点
}

func (this *Solution) set(key int, value int) {
	// write code here
	//新增或者修改？
	node, ok := this.HashStorage[key]
	if ok {
		//修改
		node.Val = value
		this.moveNodeToTheEnd(node)
		return
	}

	//插入的情况；
	if len(this.HashStorage) >= this.Cap {
		//弹出首个元素
		tmpV := this.Head.Key
		this.deleteFromList(this.Head)
		delete(this.HashStorage, tmpV)
	}
	//加入一个元素
	node = &dataNode{
		Key: key,
		Val: value,
	}
	this.HashStorage[key] = node
	this.addNodeToEnd(node)
	return

}