LinkList的底层数据结构及优缺点详解

底层数据结构

链表由一系列 节点（node） 组成，每个节点包含两部分：

• 数据域：存储实际数据。
• 指针域：存储指向下一个节点（单向链表）或前驱/后继节点（双向链表）的地址。
• 物理存储：节点在内存中 非连续分布，通过指针链接形成逻辑上的线性关系。
• 核心操作：通过指针的重新指向实现插入/删除，无需移动其他元素。

优点

1.动态大小

• 无需预先分配固定内存，可动态扩展或收缩，避免内存浪费。

2.高效插入/删除

• 时间复杂度：o(1)（已知节点位置时，如头/尾操作）。
• 仅需修改指针，无需移动其他元素（与数组的 o(n) 对比明显优势）。

3.灵活的存储结构

• 适用于频繁修改的场景（如队列、图邻接表）。
• 双向链表支持反向遍历，提升某些操作效率。

缺点

1.随机访问低效

• 必须从头节点遍历，时间复杂度 o(n)，而数组通过索引访问为 o(1)。

2.额外内存开销

• 每个节点需存储指针，占用额外空间（尤其是双向链表，每个节点多一个指针）。

3.缓存不友好

• 内存非连续分布，导致 cpu 缓存命中率低，遍历效率低于数组。

4.代码复杂度

• 需要手动管理指针，易出现内存泄漏或指针错误（如双向链表的指针维护）。

不同链表类型的对比

类型	特点	适用场景
单向链表	每个节点仅指向下一个节点，内存占用较少	简单插入/删除（如栈、lru缓存）
双向链表	支持双向遍历，插入/删除更灵活，但内存占用更高	频繁双向操作（如双向队列）
循环链表	尾节点指向头节点，形成环，适合周期性操作（如轮询调度）	循环队列、轮询任务管理

总结

• 选择链表：需频繁插入/删除，且不依赖随机访问。
• 选择数组：需快速访问元素，或内存紧凑性要求高。
• 优化方向：结合哈希表（如设计 lru 缓存）可弥补链表访问效率问题。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。