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

package main

type Solution struct {
	// 使用 Hash 结构作为缓存
    // 使用双向链表实现 LRU
	Table    map[int]*LinkNode
	Capacity int
	Len      int
	Head     *LinkNode
	Tail     *LinkNode
}

type LinkNode struct {
	Key  int
	Val  int
	Pre  *LinkNode
	Next *LinkNode
}

func Constructor(capacity int) Solution {
	obj := Solution{
		Table:    make(map[int]*LinkNode, capacity),
		Capacity: capacity,
		Len:      0,
		Head:     nil,
		Tail:     nil,
	}
	return obj
}

func (this *Solution) get(key int) int {
	if node, ok := this.Table[key]; ok {
		if node != this.Head {
            this.refreshLRU(node)
		}
		return node.Val
	}
	return -1
}

func (this *Solution) set(key int, value int) {
	if node, ok := this.Table[key]; ok {
		if node != this.Head {
			this.refreshLRU(node)
		}
		node.Val = value
		node.Key = key
	} else {
		if this.Len == this.Capacity {
			this.delCache() //删除尾部的节点
		}
		node := &LinkNode{
			Key:  key,
			Val:  value,
			Pre:  nil,
			Next: this.Head,
		}
		if this.Head != nil {
			this.Head.Pre = node
		}
		this.Head = node
		this.Table[key] = node
		this.Len++

		if this.Tail == nil {
			this.Tail = node
		}
	}
}

func (this *Solution) refreshLRU(node *LinkNode) {
    // 将该节点移出
    // 如果这个节点是尾节点，对尾节点重新复制
    if node.Next != nil {
        node.Next.Pre, node.Pre.Next = node.Pre, node.Next
    } else { 
        this.Tail = node.Pre
        this.Tail.Next = nil
    }
    // 将该节点移动到队首
    this.Head.Pre = node
    node.Next = this.Head
    this.Head = node
    this.Head.Pre = nil
}

func(this *Solution) delCache() {
    removeNode := this.Tail
    if this.Tail == this.Head {
        this.Head = nil
        this.Tail = nil
    } else {
        this.Tail = this.Tail.Pre
        this.Tail.Next = nil
    }

    delete(this.Table, removeNode.Key)
    this.Len--
}