> Как работает двусвязный список в LRU кэше (Go)

В LRU-кэше двусвязный список используется для отслеживания порядка использования элементов. Каждый узел списка хранит ключ, значение и указатели на предыдущий и следующий узлы. Голова списка содержит самый недавно использованный элемент (MRU), а хвост - самый давно (LRU). При обращении к элементу он перемещается в голову. При переполнении кэша удаляется элемент из хвоста.

В Go это реализуется через структуру с мапой для O(1) доступа и двусвязным списком из стандартного пакета container/list. Пример:

GO
type Cache struct {
    cap  int
    m    map[int]*list.Element
    list *list.List
}

type entry struct {
    key   int
    value int
}

func NewCache(capacity int) *Cache {
    return &Cache{
        cap:  capacity,
        m:    make(map[int]*list.Element),
        list: list.New(),
    }
}

func (c *Cache) Get(key int) int {
    if elem, ok := c.m[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *Cache) Put(key, value int) {
    if elem, ok := c.m[key]; ok {
        elem.Value.(*entry).value = value
        c.list.MoveToFront(elem)
        return
    }
    if c.list.Len() == c.cap {
        tail := c.list.Back()
        delete(c.m, tail.Value.(*entry).key)
        c.list.Remove(tail)
    }
    elem := c.list.PushFront(&entry{key, value})
    c.m[key] = elem
}

Ключевое преимущество - операции Get и Put выполняются за O(1) благодаря комбинации хеш-таблицы и двусвязного списка.