golang使用list实现lru

在golang中，我们可以使用container/list包来实现一个基于LRU（最近最少使用）策略的缓存。LRU缓存是指当缓存空间不够时，会淘汰最近最少使用的数据项，以便为新的数据腾出空间。

1. 使用list和map结合

首先，我们需要使用container/list包提供的List数据结构创建一个链表来维护数据项的顺序。然后，我们再使用map来维护数据项与其所在链表节点的映射关系。

在实现LRU缓存时，我们需要定义一个LRUCache结构体，该结构体包含一个链表和一个map：

type LRUCache struct {
    capacity int
    cache    map[interface{}]*list.Element
    list     *list.List
}

其中，capacity表示缓存容量，cache用于存储数据项与链表节点的映射关系，list则是用来维护数据项的顺序。

2. 实现Get方法

接下来，我们需要实现LRUCache的Get方法。该方法首先检查key是否存在于cache中，如果存在，则将其对应的链表节点移动到链表头部，并返回对应的value值。如果key不存在，直接返回nil。

具体的实现代码如下：

func (lru *LRUCache) Get(key interface{}) interface{} {
    if node, ok := lru.cache[key]; ok {
        lru.list.MoveToFront(node)
        return node.Value.(*entry).value
    }
    return nil
}

3. 实现Put方法

最后，我们需要实现LRUCache的Put方法。该方法首先检查key是否已存在于cache中，如果是，则更新相应的value并将对应的链表节点移动到链表头部。如果不是，首先检查缓存是否已满，如果已满，则淘汰链表尾部的数据项，并从cache和list中删除相应的节点。然后，创建一个新的链表节点，并将其插入到链表头部。

具体的实现代码如下：

func (lru *LRUCache) Put(key interface{}, value interface{}) {
    if node, ok := lru.cache[key]; ok {
        node.Value.(*entry).value = value
        lru.list.MoveToFront(node)
        return
    }

    if len(lru.cache) == lru.capacity {
        tail := lru.list.Back()
        delete(lru.cache, tail.Value.(*entry).key)
        lru.list.Remove(tail)
    }

    newNode := lru.list.PushFront(&entry{key, value})
    lru.cache[key] = newNode
}

通过以上三个步骤的实现，我们就完成了基于golang的list实现LRU缓存。使用container/list包的好处在于插入和删除节点的时间复杂度都是O(1)，因此，LRU缓存的性能比较高效。