golang sample code to implement the LRU cache elimination algorithm

LRU cache elimination algorithm

LRU stands for the least recently used strategy, which is to weed out data based on historical access to the data. The core idea is that "if the data has been accessed recently, it is more likely to be accessed in the future."

Bi-directional linked list implementation LRU

All the positions of Cache are connected with a double-linked list. When a position is accessed (get/put), the position is adjusted to the head of the linked list by adjusting the direction of the list. The newly added Cache is directly added to the head of the linked list.

In this way, after many operations, the most recently accessed (get/put) will be moved towards the head of the list, while those that are not accessed will be moved towards the rear of the list, with the tail representing the least recently used Cache.

When the cache capacity limit is reached, the last position of the list is the least accessed Cache, we just need to remove the last Cache to continue adding new Cache.

Code implementation

type Node struct {
  Key int
  Value int
  pre *Node
  next *Node
}

type LRUCache struct {
  limit int
  HashMap map[int]*Node
  head *Node
  end *Node
}

func Constructor(capacity int) LRUCache{
  lruCache := LRUCache{limit:capacity}
  lruCache.HashMap = make(map[int]*Node, capacity)
  return lruCache
}

func (l *LRUCache) Get(key int) int {
  if v,ok:= l.HashMap[key];ok {
    l.refreshNode(v)
    return v.Value
  }else {
    return -1
  }
}

func (l *LRUCache) Put(key int, value int) {
  if v,ok := l.HashMap[key];!ok{
    if len(l.HashMap) >= l.limit{
      oldKey := l.removeNode(l.head)
      delete(l.HashMap, oldKey)
    }
    node := Node{Key:key, Value:value}
    l.addNode(&node)
    l.HashMap[key] = &node
  }else {
    v.Value = value
    l.refreshNode(v)
  }
}

func (l *LRUCache) refreshNode(node *Node){
  if node == l.end {
    return
  }
  l.removeNode(node)
  l.addNode(node)
}

func (l *LRUCache) removeNode(node *Node) int{
  if node == l.end {
    l.end = l.end.pre
  }else if node == l.head {
    l.head = l.head.next
  }else {
    node.pre.next = node.next
    node.next.pre = node.pre
  }
  return node.Key
}

func (l *LRUCache) addNode(node *Node){
  if l.end != nil {
    l.end.next = node
    node.pre = l.end
    node.next = nil
  }
  l.end = node
  if l.head == nil {
    l.head = node
  }
}