4. 基础数据结构实现：链表节点定义、哈希表初始化、双向链表增删操作

LRU 缓存的核心是快速查找和有序淘汰。要同时实现 O(1) 的 get 和 put 操作，必须将 哈希表 与 双向链表 组合使用。本章将定义基础节点结构，初始化哈希表与链表，并实现双向链表的增删操作，为后续的淘汰逻辑打下基础。

4.1 数据结构设计总览

• 双向链表：按访问时间排序。最近访问的节点在 头部，最久未访问的节点在 尾部（淘汰候选）。
• 哈希表：key -> 链表节点指针 的映射。支持 O(1) 键值定位。
• 组合关系：哈希表负责快速定位节点，链表负责维护淘汰顺序。

4.2 链表节点定义

每个节点存储 key、value 以及前后指针 prev 和 next。使用 int 类型为例，实际工程中可使用泛型。

// C++ 示例：双向链表节点
struct DLinkedNode {
    int key;
    int value;
    DLinkedNode* prev;
    DLinkedNode* next;

    // 带参构造函数
    DLinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    // 默认构造函数（用于哨兵节点）
    DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
};

4.3 哈希表初始化

哈希表选用 unordered_map，键为 int，值为 DLinkedNode*。初始化时分配链表节点池或使用动态内存。

class LRUCache {
private:
    int capacity_;                    // 最大容量
    int size_;                        // 当前节点数
    DLinkedNode* head_;               // 虚拟头节点
    DLinkedNode* tail_;               // 虚拟尾节点
    unordered_map<int, DLinkedNode*> cache_; // 哈希表

public:
    LRUCache(int capacity) : capacity_(capacity), size_(0) {
        // 初始化双向链表：创建两个哨兵节点
        head_ = new DLinkedNode();
        tail_ = new DLinkedNode();
        head_->next = tail_;
        tail_->prev = head_;
    }
    ~LRUCache() {
        // 析构时释放所有节点
        DLinkedNode* cur = head_;
        while (cur) {
            DLinkedNode* next = cur->next;
            delete cur;
            cur = next;
        }
    }
};

4.4 双向链表增删操作

在 LRU 缓存中，链表操作主要有三种：头部插入、尾部删除、节点移除（任意位置）。后两者是基础，头部插入可视为移除后再插入头部。

4.5 核心函数代码实现

以下是双向链表四项关键操作的实现。注意指针修改顺序，避免丢失链表地址。

// 将节点添加到虚拟头节点之后（头部实际首节点）
void addToHead(DLinkedNode* node) {
    node->prev = head_;
    node->next = head_->next;
    head_->next->prev = node;
    head_->next = node;
}

// 从链表中移除节点（不删除内存）
void removeNode(DLinkedNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 移除并返回尾部实际节点（删除前仍需 return 以获取 key）
DLinkedNode* removeTail() {
    DLinkedNode* node = tail_->prev;
    removeNode(node);
    return node;
}

// 将已有节点移动到头部
void moveToHead(DLinkedNode* node) {
    removeNode(node);
    addToHead(node);
}

4.6 数据结构关系图

下面用内联 SVG 展示哈希表与双向链表的协同结构，以及节点间的连接关系。哈希表指向链表节点，链表节点通过 prev/next 串联，head_ 和 tail_ 作为哨兵节点位于两端，实际数据节点位于中间。

4.7 数据结构关系说明

1. 哈希表：键为缓存 key，值为指向链表节点的指针，实现 O(1) 查找。
2. 双向链表：真实数据节点按访问时间顺序排列，head_ 侧为最近使用，tail_ 侧为最久未使用。
3. 哨兵节点：head_ 和 tail_ 不存储数据，简化边界情况处理。
4. 淘汰机制：当缓存达到容量上限，移除 tail_->prev 节点，并删除哈希表中对应的 key。