LFU Cache written in Go2. Playground: https://go2goplay.golang.org/p/qFlA5TGqxHb

lfu.go

package main

type CacheNode[K, V any] struct {
	key    K
	value  V
	prev   *CacheNode[K, V]
	next   *CacheNode[K, V]
	parent *FreqNode[K, V]
}

func (node *CacheNode[K, V]) evictNode() {
	// remove the cache node from the linkedList
	// remove the freqNode(parent) if it is empty
	// do nothing to the map
	curFreqNode := node.parent
	if node.prev != nil {
		node.prev.next = node.next
	} else {
		curFreqNode.head = node.next
	}

	if node.next != nil {
		node.next.prev = node.prev
	} else {
		curFreqNode.tail = node.prev
	}

	if curFreqNode.head == nil {
		curFreqNode.removeFreqNode()
	}
}

func (n *CacheNode[K, V]) moveAddOneFreq(key K, value V) *CacheNode[K, V] {
	var newFreqNode *FreqNode[K, V]
	curFreqNode := n.parent

	if curFreqNode.next != nil && curFreqNode.next.freq == (curFreqNode.freq+1) {
		newFreqNode = curFreqNode.next
	} else {
		newFreqNode = NewFreqNode(curFreqNode.freq+1, curFreqNode, curFreqNode.next)
	}

	newCacheNode := &CacheNode[K, V]{
		key:    key,
		value:  value,
		prev:   nil,
		next:   newFreqNode.head,
		parent: newFreqNode,
	}
	if newFreqNode.head == nil {
		newFreqNode.tail = newCacheNode
	} else {
		newFreqNode.head.prev = newCacheNode
	}

	newFreqNode.head = newCacheNode

	n.evictNode()
	return newCacheNode
}

type FreqNode[K, V any] struct {
	freq int
	head *CacheNode[K, V]
	tail *CacheNode[K, V]
	prev *FreqNode[K, V]
	next *FreqNode[K, V]
}

func (node *FreqNode[K, V]) removeFreqNode() {
	if node.freq == 0 {
		panic("should not remove the head")
	}
	node.prev.next = node.next
	if node.next != nil {
		node.next.prev = node.prev
	}
}

func NewFreqNode[K, V any](freq int, prev *FreqNode[K, V], next *FreqNode[K, V]) *FreqNode[K, V] {
	nn := &FreqNode[K, V]{
		freq: freq,
		prev: prev,
		next: next,
	}
	if prev != nil {
		prev.next = nn
	}
	if next != nil {
		next.prev = nn
	}
	return nn
}

type LFUCache[K comparable, V any] struct {
	size     int
	capacity int
	cache    map[K]*CacheNode[K, V]
	lfuHead  *FreqNode[K, V]
}

func NewLFUCache[K comparable, V any](capacity int) *LFUCache[K, V] {
	zeroFreqHead := &FreqNode[K, V]{
		freq: 0, // head freq is true
	}
	return &LFUCache[K, V]{
		capacity: capacity,
		cache:    make(map[K]*CacheNode[K, V], capacity),
		lfuHead:  zeroFreqHead,
	}
}

func (l *LFUCache[K, V]) Get(key K) (v V, ok bool) {
	if found, ok := l.cache[key]; ok {
		newCacheNode := found.moveAddOneFreq(key, found.value)
		l.cache[key] = newCacheNode
		return found.value, true
	}
	return
}

func (l *LFUCache[K, V]) Put(key K, value V) {
	if l.capacity == 0 {
		return
	}
	if found, ok := l.cache[key]; ok {
		newCacheNode := found.moveAddOneFreq(key, value)
		l.cache[key] = newCacheNode
	} else {
		if l.size >= l.capacity {
			lfuNode := l.lfuHead.next.tail
			delete(l.cache, lfuNode.key)
			lfuNode.evictNode()
		} else {
			l.size++
		}

		var oneFreqNode *FreqNode[K, V]
		if l.lfuHead.next != nil && l.lfuHead.next.freq == 1 {
			oneFreqNode = l.lfuHead.next
		} else {
			oneFreqNode = NewFreqNode(1, l.lfuHead, l.lfuHead.next)
		}

		newCacheNode := &CacheNode[K, V]{
			key:    key,
			value:  value,
			prev:   nil,
			next:   oneFreqNode.head,
			parent: oneFreqNode,
		}
		l.cache[key] = newCacheNode
		if oneFreqNode.head == nil {
			oneFreqNode.tail = newCacheNode
		} else {
			oneFreqNode.head.prev = newCacheNode
		}
		oneFreqNode.head = newCacheNode
	}

}