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

package main

type Node struct {
	pre  *Node
	next *Node
	key  int
	val  int
}
type Solution struct {
	ma   map[int]*Node
	cap  int
	head *Node
	tail *Node
}

func Constructor(capacity int) Solution {
	solution := Solution{
		cap:  capacity,
		ma:   make(map[int]*Node, capacity),
		head: nil,
		tail: nil,
	}
	return solution
}

func (this *Solution) get(key int) int {
	node := this.ma[key]
	if node == nil {
		return -1
	}
	this.moveToHead(node)
	return node.val
}

func (this *Solution) moveToHead(node *Node) {
	this.removeNode(node)
	this.addHead(node)
}

func (this *Solution) addHead(node *Node) {
	if this.head == nil {
		this.head = node
		this.tail = node
	} else {
		node.next = this.head
		this.head.pre = node
		this.head = node
	}
}

func (this *Solution) removeNode(node *Node) {
	pre := node.pre
	next := node.next
	if pre != nil {
		pre.next = next
	}
	if next != nil {
		next.pre = pre
	}
	node.next = nil
	node.pre = nil

	if node == this.head {
		this.head = next
	}
	if node == this.tail {
		this.tail = pre
	}
}

func (this *Solution) removeTail() {
	node := this.tail
	if node != nil {
		this.removeNode(node)
		delete(this.ma, node.key)
	}

}

func (this *Solution) set(key int, value int) {
	node := &Node{
		key: key,
		val: value,
	}
	this.addHead(node)
	this.ma[key] = node
	if len(this.ma) > this.cap {
		this.removeTail()
	}

}