LRU算法实现

package main

import (
    "fmt"
)

// 定义节点结构体
type node struct {
    key   string
    value string
    next  *node
    prev  *node
}

// 定义lru结构体
type lru struct {
    //缓存最大数量
    k int
    // 存放节点数据
    cache map[string]*node
    //头节点
    head *node
    // 尾节点
    tail *node
}

// 工厂方法，构造一个LRU缓存对象
func NewLRUCache(k int) *lru {
    return &lru{k: k}
}

// 对外开放的Get方法
func (lru *lru) Get(key string) string {
    if lru.cache == nil {
        return ""
    }
    n, ok := lru.cache[key]
    if ok {
        value := n.value
        //更新到头节点
        lru.moveNodeToHead(n)
        return value
    } else {
        return ""
    }
}

// 对外开放的Set方法
func (lru *lru) Set(key string, value string) {
    //初始化map
    if lru.cache == nil {
        lru.cache = make(map[string]*node)
    }
    n, ok := lru.cache[key]
    if ok {
        //更新缓存
        n.value = value
    } else {
        //创建新节点
        n = &node{key: key, value: value}
        // 添加到map中
        lru.cache[key] = n
        //如果超过缓存大小，移除最后一个节点
        if len(lru.cache) > lru.k {
            lru.removeTail()
        }
    }
    // 更新节点为头节点
    lru.moveNodeToHead(n)
}

//将指定节点移到头节点
func (lru *lru) moveNodeToHead(n *node) {
    //如果头节点和尾节点都是空，说明是第一次添加数据
    if lru.head == nil && lru.tail == nil {
        lru.head = n
        lru.tail = n
        return
    }
    // 如果是头节点，那么不动
    if lru.head == n {
        return
    }
    nextNode := n.next
    prevNode := n.prev
    // 如果是尾节点，那么要先与上一个节点断开
    if n == lru.tail {
        prevNode.next = nil
        n.prev = nil
    } else if prevNode != nil && nextNode != nil {
        //如果是中间节点，要与前后节点都断开
        nextNode.prev = prevNode
        prevNode.next = nextNode
        n.prev = nil
    }
    //把节点移到到头节点
    n.next = lru.head
    lru.head.prev = n
    lru.head = n
}

//移除最后一个节点
func (lru *lru) removeTail() {
    // 如果尾节点wei空，那么清空数据直接返回
    if lru.tail == nil {
        lru.cache = nil
        return
    }
    tailPrev := lru.tail.prev
    // 尾节点与上一个节点断开
    lru.tail.prev = nil
    if tailPrev != nil {
        tailPrev.next = nil
    }
    // 把上一个节点置为尾节点
    lru.tail = tailPrev
    // 从map中删除尾节点数据
    delete(lru.cache, lru.tail.key)
}

// 重写String方法，自定义打印结果
func (lru *lru) String() string {
    point := lru.head
    result := ""
    flag := "\t"
    for point != nil {
        if len(result) > 0 {
            result = fmt.Sprintf("%v%v[%v:%v]", result, flag, point.key, point.value)
        } else {
            result = fmt.Sprintf("[%v:%v]", point.key, point.value)
        }
        point = point.next
    }
    return result
}

func main() {
    LRUCache := NewLRUCache(5)
    LRUCache.Set("1", "1")
    LRUCache.Set("2", "2")
    LRUCache.Set("3", "3")
    LRUCache.Set("4", "4")
    LRUCache.Set("5", "5")
    //打印缓存数据，验证容量是否起作用
    fmt.Println(LRUCache)
    //设置超过最大容量的数据
    LRUCache.Set("6", "6")
    //打印缓存数据，验证超过容量是否起作用
    fmt.Println(LRUCache)
    //查询头节点数据
    fmt.Println(LRUCache.Get("6"))
    //打印缓存数据
    fmt.Println(LRUCache)
    //查询非头节点数据
    fmt.Println(LRUCache.Get("4"))
    //打印缓存数据
    fmt.Println(LRUCache)
    //查询尾节点数据
    fmt.Println(LRUCache.Get("2"))
    //打印缓存数据
    fmt.Println(LRUCache)
}

image.png