链表操作模拟 - 单向/双向链表增删改查

链表（Linked List）是一种线性数据结构，由一系列节点组成。每个节点包含数据域和指针域，指针域存储下一个节点的内存地址。与数组不同，链表的节点在内存中不必连续存储。

单向链表：每个节点只有一个指针 next，指向后继节点。只能从头向尾单向遍历。

双向链表：每个节点有两个指针 prev 和 next，分别指向前驱和后继。可以双向遍历。

关键差异：

• 双向链表删除尾节点为 O(1)（通过prev指针），单向链表为 O(n)
• 双向链表每个节点多占用一个指针的存储空间
• 双向链表支持从任意节点向前或向后遍历
• 在需要频繁双向遍历的场景（如LRU缓存）中双向链表更优

* 本工具使用数组模拟链表，实际链表操作需通过指针操作完成。

反转单向链表使用三指针法（prev, curr, next），迭代遍历并修改指针方向：

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let next = curr.next;  // 保存下一个节点
        curr.next = prev;      // 反转指针
        prev = curr;           // prev 前进
        curr = next;           // curr 前进
    }
    return prev;  // 新的头节点
}

时间复杂度：O(n) | 空间复杂度：O(1)

也可使用递归实现，但递归的空间复杂度为 O(n)。

• LRU缓存淘汰算法：双向链表 + 哈希表实现高效缓存策略
• 浏览器的前进/后退：双向链表管理页面导航历史
• 操作系统内存管理：空闲内存块使用链表组织
• 哈希表冲突解决：链地址法使用链表存储冲突元素
• 音乐播放列表：歌曲的上一首/下一首切换
• Undo/Redo功能：编辑器中的操作历史管理
• 图的邻接表表示：每个顶点的邻接顶点用链表存储
• 多项式运算：稀疏多项式的存储与计算

虽然链表插入/删除操作本身只需修改指针（O(1)），但在实际场景中：

• 查找目标位置需要O(n)：除非已有目标节点的引用，否则需从头遍历
• 内存分配开销：动态分配新节点涉及系统调用
• 缓存未命中：链表节点分散存储，CPU缓存命中率低
• 指针解引用开销：每次访问节点都需要间接寻址

因此在小规模数据场景下，数组的插入删除（虽然理论O(n)）可能因缓存友好而更快。