链表和双向链表

Posted 2024-09-27 Updated 2024-09- 27

By 随风

14~18 min read

链表（Linked List）是一种基础的数据结构，具有灵活的动态内存分配特点。链表中的元素（称为节点）通过指针连接，形成线性结构。链表和数组是两种常见的线性数据结构，但链表不同于数组，链表中的元素并不连续存储。

链表的主要优点是：插入和删除操作非常高效，只需要调整指针即可，不需要像数组那样进行大规模的数据移动。

下面详细介绍链表和双向链表的结构、操作、优缺点及应用场景。

1. 单向链表（Singly Linked List）

1.1 基本结构

单向链表由一组节点组成，每个节点包含两个部分：

数据域（Data）：存储数据元素。
指针域（Next）：存储指向下一个节点的指针。

链表中的第一个节点称为 头节点（Head），最后一个节点的 Next 指向 NULL，表示链表的终止。

1.2 链表示例

一个简单的单向链表可以如下表示：

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> NULL

1.3 常用操作

插入（Insert）：在链表的头部、尾部或中间插入一个新节点。
- 在头部插入：直接修改头节点的指针即可。
- 在尾部插入：需要遍历链表，找到最后一个节点，将其 Next 指向新节点。
- 在中间插入：需要遍历到目标位置，调整相邻节点的 Next 指针。
删除（Delete）：删除链表中的某个节点。
- 删除头节点：直接将头节点的指针指向第二个节点。
- 删除中间节点或尾节点：需要遍历链表，找到要删除的节点，调整前一个节点的 Next 指针，跳过要删除的节点。
查找（Search）：根据值查找链表中的节点，通常需要遍历链表进行逐个比较。
遍历（Traverse）：从头节点开始依次访问每个节点，直到链表末尾。

1.4 时间复杂度

插入：在头部插入为 O(1)，在尾部插入为 O(n)（需要遍历链表）。
删除：删除头节点为 O(1)，删除中间节点或尾部节点为 O(n)（需要遍历链表）。
查找：O(n)，需要遍历链表。
遍历：O(n)。

1.5 优缺点

优点：

动态内存分配，链表大小不固定，能根据需要增删节点。
插入和删除操作效率较高，特别是在头部和尾部操作时，避免了大规模数据移动。

缺点：

链表需要额外的指针存储空间。
随机访问效率低，无法直接通过下标访问，需要遍历链表。
查找、删除特定值的效率较低，因为需要线性扫描整个链表。

1.6 应用场景

实现队列、栈等数据结构。
内存有限时，使用链表能更好地管理内存，避免因数组大小限制导致的溢出。
动态集合：链表适合需要频繁插入、删除元素的场景。

2. 双向链表（Doubly Linked List）

2.1 基本结构

双向链表与单向链表类似，但它的每个节点包含三个部分：

数据域（Data）：存储数据元素。
前向指针（Prev）：指向前一个节点。
后向指针（Next）：指向下一个节点。

由于每个节点有指向前后节点的指针，双向链表可以从任意节点向前或向后遍历。

2.2 链表示例

一个简单的双向链表可以如下表示：

NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL

2.3 常用操作

双向链表的操作与单向链表类似，但由于有两个指针，插入和删除时需要更多的指针调整。

插入（Insert）：
- 在头部插入：新节点的 Next 指向旧头节点，旧头节点的 Prev 指向新节点。
- 在尾部插入：新节点的 Prev 指向旧尾节点，旧尾节点的 Next 指向新节点。
- 在中间插入：新节点的 Prev 和 Next 分别指向前后节点，前后节点的指针需要进行相应调整。
删除（Delete）：
- 删除头节点：调整头节点的 Next 节点的 Prev 为 NULL，并将头节点移向下一个节点。
- 删除尾节点：调整尾节点的 Prev 节点的 Next 为 NULL，并将尾节点移向上一个节点。
- 删除中间节点：调整前后节点的 Prev 和 Next 指针，跳过要删除的节点。
查找（Search）：与单向链表类似，仍然需要从头或尾遍历链表。
遍历（Traverse）：
- 从头节点遍历到尾节点：沿着 Next 指针访问每个节点。
- 从尾节点遍历到头节点：沿着 Prev 指针访问每个节点。

2.4 时间复杂度

与单向链表类似，双向链表的插入、删除和查找操作的时间复杂度为 O(n)。但双向链表在删除操作中具有一定优势，可以直接访问前驱节点，无需再次遍历。

插入：O(1) 在头部和尾部的插入仍然很高效。
删除：O(1) 如果节点位置已知，可以直接通过 Prev 指针访问前驱节点并删除，操作效率更高。
查找：O(n)，需要遍历链表。
遍历：O(n)，可以从头到尾或从尾到头遍历。

2.5 优缺点

优点：

双向遍历：可以从任意节点向前或向后遍历链表，灵活性较高。
删除节点时效率较高：删除时可以通过前向指针直接访问前一个节点，无需再次遍历链表。
插入删除操作与单向链表一样灵活。

缺点：

与单向链表相比，双向链表需要额外的存储空间来存储前向指针。
代码实现相对复杂，因为每次操作需要同时处理 Prev 和 Next 指针。

2.6 应用场景

LRU缓存机制：双向链表通常与哈希表结合使用，构建 LRU（Least Recently Used）缓存淘汰策略。双向链表能高效地实现元素的插入、删除和调整顺序操作。
浏览器历史记录：浏览器的前进和后退功能可通过双向链表实现。
文本编辑器：文本编辑器中的撤销与重做功能可以使用双向链表存储操作步骤。

3. 单向链表 vs 双向链表

总结

单向链表 结构简单，适用于只需要从头遍历到尾且不需要频繁删除操作的场景。
双向链表 更灵活，适合频繁插入、删除操作，特别是在需要前后双向遍历的场景中有显著优势。

其他

License: CC BY 4.0