题解 | 设计LRU缓存结构 GO语言版本

package main

type Solution struct {
	// write code here
	Data       map[int]*Node //哈希表
	Head, Tail *Node //双向链表
	Cap, Size  int //记录容量
}

type Node struct {
	Key, Val   int
	Prev, Next *Node
}

func Constructor(capacity int) (s Solution) {
	// write code here
	s.Cap = capacity
	s.Size = 0
	s.Data = make(map[int]*Node)
	s.Head = &Node{}
	s.Tail = &Node{}
	s.Head.Next = s.Tail
	s.Tail.Prev = s.Head
	return
}

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

func (this *Solution) set(key int, value int) {
	// write code here
	if node, ok := this.Data[key]; ok {
		this.delete(node)
        this.addToHead(node)
        node.Val = value
	} else {
		if this.Size >= this.Cap{
            delete(this.Data, this.Tail.Prev.Key)
            this.delete(this.Tail.Prev)
            this.Size--
        }
        newNode := &Node{Key: key, Val:value}
        this.Data[key]=newNode
        this.addToHead(newNode)
        this.Size++
	}
}

func (this *Solution) delete(node *Node)  {
    if node.Prev!= nil{
        node.Prev.Next = node.Next
    }
    if node.Next!=nil{
        node.Next.Prev = node.Prev
    }
}

func (this *Solution) addToHead(node *Node) {
    node.Next = this.Head.Next
    node.Prev = this.Head
    this.Head.Next.Prev = node
    this.Head.Next=node
}

/**
 * Your Solution object will be instantiated and called as such:
 * solution := Constructor(capacity);
 * output := solution.get(key);
 * solution.set(key,value);
 */