golang实现LRU算法

Least Recently used

本文仅列出完成 LeetCode146.LRU缓存的思路

实现：

• 哈希表：键为关键字key，值为*DLinkNode，映射对应链表中的节点
• 双向链表：靠近头部的元素是最近使用的，靠近尾部则是最久未使用的

实现LRU并不难，建议先把算法的各个函数的框架先列好，再去敲代码！！

结构：

//LRUCache定义
type LRUCache struct {
    size int     
    capacity int
    cache map[int]*DLinkNode
    head, tail *DLinkNode
}

//双向链表节点
type DLinkNode struct {
    key,value int
    pre, next *DLinkNode
}

功能：

//缓存实现的功能
//如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
func (this *LRUCache) Get(key int) 

//如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出最久未使用的关键字
func (this *LRUCache) Put(key int, value int) 

//一些链表的操作
//初始化一个新节点
func initDLinkedNode(key, value int) *DLinkNode 

//更新到链头，用于key命中的情况下，不改变缓存的size
func (this *LRUCache) UpdateToHead(node *DLinkNode) 

//删除链尾元素
func (this *LRUCache) DeleteLast()

//添加新元素，用于key未命中时，size+1
func (this *LRUCache) InsertNewHead(node *DLinkNode) 

以下附上完整代码

type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkNode
    Head, Tail *DLinkNode
}

type DLinkNode struct {
    key,value int
    Pre, Next *DLinkNode
}

func InitDlinkNode(key, value int) *DLinkNode {
    return &DLinkNode{key,value,nil,nil}
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{
        0,
        capacity,
        map[int]*DLinkNode{},
        InitDlinkNode(0, 0),
        InitDlinkNode(0, 0),
    }
    l.Head.Next = l.Tail
    l.Tail.Pre = l.Head
    return l
}


func (this *LRUCache) Get(key int) int {
    if _,ok := this.cache[key];!ok {
        return -1
    }
    node := this.cache[key]
    this.UpdateToHead(node)
    return node.value
}


func (this *LRUCache) Put(key int, value int)  {
    if _,ok := this.cache[key];!ok {
        node := InitDlinkNode(key, value)
        for this.size >= this.capacity {
            this.DeleteLast()
        }
        this.cache[key] = node
        this.InsertNewHead(node)
    }else {
        node := this.cache[key]
        node.value = value
        this.UpdateToHead(node)
    }
}

func (this *LRUCache) UpdateToHead(node *DLinkNode) {
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
    temp := this.Head.Next
    this.Head.Next = node
    node.Pre = this.Head
    node.Next = temp
    temp.Pre = node
 
}

func (this *LRUCache) DeleteLast() {
    node := this.Tail.Pre
    this.Tail.Pre = node.Pre
    node.Pre.Next = node.Next
    node.Pre = nil
    node.Next = nil
    this.size--
    delete(this.cache, node.key)
}

func (this *LRUCache) InsertNewHead(node *DLinkNode) {
    temp := this.Head.Next
    this.Head.Next = node
    node.Pre = this.Head
    temp.Pre = node
    node.Next = temp
    this.size++
}