Go 题解 哈希表 + 双向链表 | #设计LRU缓存结构#

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
type LRUStruct struct {
    Size int
    Capacity int
    Cache map[int]*NodeList
    Head, Tail *NodeList
}

type NodeList struct {
    Key, Value int
    Prev, Next *NodeList
}

func LRU( operators [][]int ,  k int ) []int {
    res := []int{}
    newlru := initLRU(k)

    for i := 0;i < len(operators); i++{
        if len(operators[i]) == 3{
            newlru.set(operators[i][1], operators[i][2])
        }else{
            res = append(res, newlru.get(operators[i][1]))
        }
    }

    return res
}

func (this *LRUStruct) get(k int) int{
    if v, ok := this.Cache[k]; ok {
        this.removeToHead(v)
        return v.Value
    }

    return -1
}

func (this *LRUStruct) set(key int, value int) {
    if v, ok := this.Cache[key]; ok {
        v.Value = value
        this.removeToHead(v)
        return 
    }
    node := initNode(key, value)
    this.addToHead(node)
    this.Cache[key] = node
    this.Size ++
    if this.Size > this.Capacity {
        n := this.removeTail()
        delete(this.Cache, n.Key)
        this.Size --
    }

    return
}

func initNode (key int, value int) *NodeList {
    return &NodeList{Key:key, Value: value}
}

func initLRU(cap int) *LRUStruct {
    l := &LRUStruct{
        Capacity: cap,
        Cache: map[int]*NodeList{},
        Head: initNode(0, 0),
        Tail: initNode(0, 0),
    }
    l.Head.Next = l.Tail
    l.Tail.Prev = l.Head

    return l
}

func (this *LRUStruct) addToHead(node *NodeList) {
    node.Next = this.Head.Next
    node.Prev = this.Head
    this.Head.Next.Prev = node
    this.Head.Next = node
}

func (this *LRUStruct) removeNode(node *NodeList) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (this *LRUStruct) removeToHead(node *NodeList){
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUStruct) removeTail() *NodeList {
    node := this.Tail.Prev
    this.removeNode(node)

    return node
}