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

Короткий ответ

Двусвязный список в LRU кэше обеспечивает операции добавления, удаления и перемещения элементов за O(1). Каждый элемент хранит указатели на предыдущий и следующий узлы, а hash-таблица даёт прямой доступ к узлу по ключу. При обращении к элементу он перемещается в голову списка (most recently used), а при переполнении - удаляется хвост (least recently used). Это классический паттерн, сочетающий быстрый поиск по ключу и поддержание порядка использования.

Подробное объяснение

LRU (Least Recently Used) кэш требует двух структур данных:

• hash-таблица (map) для доступа к элементу по ключу за O(1)
• двусвязный список для поддержания порядка использования

Почему именно двусвязный список, а не односвязный? При удалении узла из середины списка нужно знать предыдущий узел, чтобы переставить указатели. В односвязном списке пришлось бы идти от головы - это O(n). Двусвязный список позволяет удалить любой узел за O(1), имея только ссылку на сам узел.

Структура узла:

GO
type Node struct {
    key   string
    value interface{}
    prev  *Node
    next  *Node
}

Ключевые операции:

1. Get(key) - если ключ есть в map, получаем узел, перемещаем его в голову списка (remove + addToHead), возвращаем value. Если нет - возвращаем nil.

2. Put(key, value) - если ключ уже есть, обновляем value и перемещаем узел в голову. Если нет - создаём новый узел, добавляем в голову и в map. Если размер превышает capacity, удаляем хвостовой узел и его ключ из map.

Перемещение узла в голову - это две операции: удаление узла из текущей позиции (перестановка указателей prev/next соседей) и вставка после головы (или перед head). Обе - O(1).

Инвариант списка: голова - самый свежий элемент, хвост - самый старый. При переполнении удаляем именно хвост.

На практике

В Go нет встроенной реализации LRU, но есть стандартный контейнер container/list - двусвязный список. Однако на практике часто пишут свою реализацию для контроля над деталями и избежания лишних аллокаций.

Важные нюансы:

• Синхронизация: если кэш используется из нескольких горутин, нужен sync.Mutex или sync.RWMutex. Без блокировки будет data race.
• Хранение ключа в узле обязательно: при удалении хвоста нужно знать ключ, чтобы удалить его из map.
• Capacity - фиксированный размер, при превышении удаляем хвост.
• В Go map не гарантирует порядок, поэтому полагаться только на map нельзя - список даёт порядок.

Пример с container/list:

GO
type LRUCache struct {
    mu       sync.Mutex
    capacity int
    items    map[string]*list.Element
    list     *list.List
}

type entry struct {
    key   string
    value interface{}
}

func NewLRU(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key string) interface{} {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    if elem, ok := c.items[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value
    }
    return nil
}

func (c *LRUCache) Put(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    if elem, ok := c.items[key]; ok {
        elem.Value.(*entry).value = value
        c.list.MoveToFront(elem)
        return
    }
    
    elem := c.list.PushFront(&entry{key: key, value: value})
    c.items[key] = elem
    
    if c.list.Len() > c.capacity {
        oldest := c.list.Back()
        if oldest != nil {
            c.list.Remove(oldest)
            delete(c.items, oldest.Value.(*entry).key)
        }
    }
}

Как отвечать на собеседовании

Начни с краткого описания структуры: map + двусвязный список. Объясни, зачем нужен список - поддержание порядка использования. Подчеркни, что все операции O(1). Затем опиши алгоритм Get и Put, акцентируя перемещение в голову и удаление хвоста. Если спросят про альтернативы - упомяни, что можно использовать container/list, но своя реализация даёт больше контроля. Обязательно упомяни потокобезопасность и необходимость блокировок. Если собеседник спросит про edge cases - расскажи про capacity = 0 или 1, про обновление существующего ключа.

Что проверяет интервьюер

• Понимание структур данных и их комбинаций
• Умение оценивать сложность операций
• Знание нюансов работы с указателями и списками
• Понимание требований к кэшу: быстрый доступ, ограничение памяти, порядок использования
• Умение писать корректный код с учётом граничных случаев

Типичные ошибки

• Забыть удалить ключ из map при удалении узла из списка - утечка памяти
• Не хранить ключ в узле - невозможно удалить из map при eviction
• Использовать односвязный список - удаление из середины становится O(n)
• Не учитывать потокобезопасность - data race при конкурентном доступе
• Путать голову и хвост: голова - самый свежий, хвост - самый старый
• Не обновлять позицию узла при Get - кэш перестаёт быть LRU
• Забыть про случай capacity = 0 - кэш не должен хранить ничего