题解 | 设计LRU缓存结构

package main

import (
	"container/list"
)

/*
LRU 缓存 (Least Recently Used)

设计思路：
1. 使用一个双向链表 (list.List) + 一个哈希表 (map) 来实现。
   - 双向链表保存元素的访问顺序，最新使用的放在表头，最久未使用的放在表尾。
   - 哈希表用来快速定位 key 对应的链表节点，实现 O(1) 查找。
2. 每次访问 (get) 时，如果 key 存在：
   - 将对应的节点移到链表头部（表示最近使用过）。
   - 返回节点的 value。
   - 时间复杂度 O(1)。
3. 每次插入 (set) 时：
   - 如果 key 已存在：更新 value，并将节点移到链表头部。
   - 如果 key 不存在：新建一个节点插入链表头部，并在 map 中保存 key→节点的映射。
   - 插入后如果超过容量，需要删除链表尾部的节点，同时从 map 中移除对应的 key。
   - 时间复杂度 O(1)。
4. 这样可以保证：
   - 查找、更新、插入和淘汰都在常数时间内完成。
*/

type LRUElement struct {
	value int // 缓存的值
	key   int // 缓存的键，用于淘汰时从 map 中删除
}

type Solution struct {
	linkedList *list.List            // 双向链表，保存元素的访问顺序
	dataMap    map[int]*list.Element // 哈希表，key → 链表节点
	capacity   int                   // 缓存容量
}

// Constructor 初始化 LRU 缓存，指定最大容量
func Constructor(capacity int) Solution {
	return Solution{
		linkedList: list.New(),                // 新建一个空的双向链表
		dataMap:    make(map[int]*list.Element), // 初始化哈希表
		capacity:   capacity,                  // 设置容量
	}
}

// get 获取 key 对应的 value
// 如果 key 存在，将对应节点移到链表头部（表示最近使用过），并返回值
// 如果 key 不存在，返回 -1
func (this *Solution) get(key int) int {
	if existElement, ok := this.dataMap[key]; ok {
		// 移动到链表头部
		this.linkedList.MoveToFront(existElement)
		// 返回值
		return existElement.Value.(*LRUElement).value
	}
	return -1
}

// set 插入或更新 key-value
// 如果 key 已存在，更新 value 并移到链表头部
// 如果 key 不存在，新建节点放到链表头部
// 插入后如果超过容量，淘汰链表尾部节点（最久未使用的）
func (this *Solution) set(key int, value int) {
	// key 已存在 → 更新 value，移到头部
	if existElement, ok := this.dataMap[key]; ok {
		existElement.Value.(*LRUElement).value = value
		this.linkedList.MoveToFront(existElement)
		return
	}

	// key 不存在 → 插入新节点到头部
	elem := &LRUElement{value: value, key: key}
	listElem := this.linkedList.PushFront(elem)
	this.dataMap[key] = listElem

	// 如果超过容量 → 删除尾部节点
	if this.linkedList.Len() > this.capacity {
		backElem := this.linkedList.Back()
		if backElem != nil {
			// 找到尾部元素
			deleteLruElement := backElem.Value.(*LRUElement)
			// 从 map 中删除
			delete(this.dataMap, deleteLruElement.key)
			// 从链表中删除
			this.linkedList.Remove(backElem)
		}
	}
}