数据结构之双链表

本篇目标：

1. 学会关于双链表的相关操作

2. 了解链表和顺序表的区别和优点

一、双链表接口实现

1. 双向链表的结构

• 单链表的结点中保存了指向后继结点的地址，所以单链表中找当前结点的后继结点很容易，但要获取当前结点的前驱结点就很麻烦，就只能从头开始往后遍历获取，时间复杂度为 O(n)；所以单链表中只有当前结点的指针 pos 时（没有头指针），想要在 pos 之前插入结点和删除 pos 位置结点都是无法实现的。

• 双向链表相比单链表最大的特征是每个结点中多了一个前驱指针，一些场景需要获取当前结点前驱结点的场景中就需要用双链表实现，如：倒着遍历、删除当前结点、在当前结点前插入结点等。

• 双向链表的一些不足是找尾结点依旧不是很方便，另外呢，头尾插入删除考虑的边界依旧比较多。后面的带头双向循环链表可以很好地解决这个问题。

代码块：

1typedef int DCLDataType;
2
3// 双向循环链表结点
4typedef struct DCListNode
5{
6    DCLDataType data;           // 存储数据元素的值
7    struct DCListNode* prev;    // 存放前驱结点的指针
8    struct DCListNode* next;    // 存放后继结点的指针
9} DCListNode;

如图：

• 实践中链表最常见的操作并非在第 i 个位序插入删除数据，而是在头尾插入删除数据，前面的单链表头插头删效率高，可以做到时间复杂度 O(1)，但是尾插尾删，需要找到尾结点，时间复杂度为 O(N)，也就是说单链表结构适合头插头删，这个在后面单链表作为复杂数据结构的子结构中可以看到主要就使用它的头插头删。

• 双向链表头插头删效率高，确定某个结点位置以后插入删除效率也很高，均可以做到时间复杂度 O(1)，但是同样尾插尾删，需要增加一个尾指针，相对麻烦；所以这里我们引用一个新的结构，循环链表可以解决这里的问题。

如图：

• 下图是单向循环链表和双向循环链表，单向循环链表就是让尾结点的 next 指向头结点；双向循环链表就是尾结点的 next 指向头结点，同时头结点的 prev 指向尾结点。

• 实践中双向循环链表非常实用，C++ 标准库（STL）中 list 就是使用的这个结构实现，因为它可以通过头结点的 prev 指针找到尾结点，轻松实现尾插尾删。也就是说这个结构头尾插入删除效率都是 O(1)，确定某个结点位置以后的插入删除也是。下面我们会重点实现这个结构。

2. 接口函数定义

1#pragma once
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <assert.h>
6
7typedef int DCLDataType;
8
9// 双向循环链表结点
10typedef struct DCListNode
11{
12    DCLDataType data;           // 存储数据元素的值
13    struct DCListNode* prev;    // 存放前驱结点的指针
14    struct DCListNode* next;    // 存放后继结点的指针
15} DCListNode;
16
17// 链表初始化
18DCListNode* DCListInit();
19
20// 销毁链表
21void DCListDestroy(DCListNode* L);
22
23// 获取链表中位序为 i 的结点
24DCListNode* DCListGetElem(DCListNode* L, int i);
25
26// 在 pos 位置后插入值为 x 的结点
27void DCListInsert(DCListNode* pos, DCLDataType x);
28
29// 删除 pos 位置的结点
30void DCListDelete(DCListNode* pos);
31
32// 头插
33void DCListPushFront(DCListNode* L, DCLDataType x);
34
35// 尾插
36void DCListPushBack(DCListNode* L, DCLDataType x);
37
38// 头删
39void DCListPopFront(DCListNode* L);
40
41// 尾删
42void DCListPopBack(DCListNode* L);
43
44// 打印链表中的元素
45void DCListPrint(DCListNode* L);

我们实现的是带头双向链表。

2.1. 初始化

初始化时，我们需要先创建一个头节点，并且前后指针要指向自己。

1// 创建一个结点
2DCListNode* BuyDCListNode(DCLDataType x)
3{
4    DCListNode* newNode = (DCListNode*)malloc(sizeof(DCListNode));
5    if (newNode == NULL)
6    {
7        perror("malloc failed");
8        return NULL;
9    }
10    newNode->data = x;
11    newNode->prev = NULL;
12    newNode->next = NULL;
13    return newNode;
14}
15
16// 链表初始化
17DCListNode* DCListInit()
18{
19    // 创建哨兵头结点
20    DCListNode* head = BuyDCListNode(-1);
21    if (head == NULL)
22    {
23        return NULL;
24    }
25    // 空链表中，头结点的前驱和后继都指向自己
26    head->next = head;
27    head->prev = head;
28    return head;
29}

2.2. 打印链表

打印双链表其实与单链表的过程差不多。

1// 打印链表中的元素
2void DCListPrint(DCListNode* L)
3{
4    assert(L != NULL);
5
6    DCListNode* cur = L->next;
7
8    printf("头结点<->");
9
10    while (cur != L)
11    {
12        printf("%d<->", cur->data);
13        cur = cur->next;
14    }
15
16    printf("头结点\n");
17}

流程图：

2.3. 销毁链表

销毁双链表其实与单链表的过程差不多，但是要记得结尾删除头节点。

1// 销毁链表
2void DCListDestroy(DCListNode* L)
3{
4    assert(L != NULL);
5
6    DCListNode* cur = L->next;
7
8    // 依次释放所有数据结点
9    while (cur != L)
10    {
11        DCListNode* next = cur->next;
12
13        free(cur);
14        cur = next;
15    }
16
17    // 最后释放哨兵头结点
18    free(L);
19}

2.4. 查找节点

查找节点时，我们需要返回这个节点，这是为了方便后面增删操作。

1// 获取链表中位序为 i 的结点
2// i 从 0 开始，i = 0 表示第一个数据结点
3DCListNode* DCListGetElem(DCListNode* L, int i)
4{
5    assert(L != NULL);
6    assert(i >= 0);
7
8    DCListNode* cur = L->next;
9    int j = 0;
10
11    while (cur != L && j < i)
12    {
13        cur = cur->next;
14        j++;
15    }
16
17    // 如果 cur == L，说明 i 超出了链表范围
18    assert(cur != L);
19
20    return cur;
21}

流程图：

2.5. 插入

• 在 pos 结点之后插入一个新结点 newNode，这里要改四个指针的链接关系，要注意的是一定不能先动 pos->next = newNode，否则就会找不到 pos 的后继结点。建议把 pos->next = newNode; 放到最后就不会出乱子。

• pos 可以指向任意结点（包括头结点），不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表（非循环），要注意的是pos 为尾结点时，需要考虑 pos->next 为空的情况，并且 pos 不能为头结点。

如图：

1// 在 pos 结点后插入值为 x 的结点
2void DCListInsert(DCListNode* pos, DCLDataType x)
3{
4    assert(pos != NULL);
5
6    DCListNode* newNode = BuyDCListNode(x);
7    assert(newNode != NULL);
8
9    DCListNode* next = pos->next;
10
11    // 将新结点连接到 pos 和 next 之间
12    pos->next = newNode;
13    newNode->prev = pos;
14
15    newNode->next = next;
16    next->prev = newNode;
17}

有了这个插入，那么头插和尾插就变得比较简单了，如代码：

1// 头插
2void DCListPushFront(DCListNode* L, DCLDataType x)
3{
4    assert(L != NULL);
5
6    DCListInsert(L, x);
7}
8
9// 尾插
10void DCListPushBack(DCListNode* L, DCLDataType x)
11{
12    assert(L != NULL);
13
14    DCListInsert(L->prev, x);
15}

2.6. 删除

• 这里改动两个指针链接关系即可，注意一定要画图捋清楚指针间的关系，否则很容易乱，这两个链接指针关系没有前后顺序。

• pos 可以指向除了头结点以外的任意结点，不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表（非循环），要注意的是 pos 为尾结点时，需要考虑 pos->next 为空的情况。

1// 删除 pos 结点
2// 注意：pos 必须是有效数据结点，不能是哨兵头结点
3void DCListDelete(DCListNode* pos)
4{
5    assert(pos != NULL);
6    assert(pos->prev != NULL);
7    assert(pos->next != NULL);
8
9    DCListNode* prev = pos->prev;
10    DCListNode* next = pos->next;
11
12    // 将 pos 的前驱和后继直接连接
13    prev->next = next;
14    next->prev = prev;
15
16    // 避免留下无效连接
17    pos->prev = NULL;
18    pos->next = NULL;
19
20    free(pos);
21}
22

有了这个删除，那么头删和尾删就变得比较简单了，如代码：

1// 头删
2void DCListPopFront(DCListNode* L)
3{
4    assert(L != NULL);
5
6    // 空链表不执行删除
7    if (L->next == L)
8    {
9        return;
10    }
11
12    DCListDelete(L->next);
13}
14
15// 尾删
16void DCListPopBack(DCListNode* L)
17{
18    assert(L != NULL);
19
20    // 空链表不执行删除
21    if (L->prev == L)
22    {
23        return;
24    }
25
26    DCListDelete(L->prev);
27}

2.7. 测试代码

1#include "DCList.h"
2
3int main()
4{
5    // 初始化链表
6    DCListNode* L = DCListInit();
7
8    // 头插
9    DCListInsert(L, 1);
10    DCListInsert(L, 2);
11    DCListInsert(L, 3);
12    DCListInsert(L, 4);
13    DCListPrint(L);
14
15    // 尾插
16    DCListInsert(L->prev, 5);
17    DCListInsert(L->prev, 6);
18    DCListInsert(L->prev, 7);
19    DCListInsert(L->prev, 8);
20    DCListPrint(L);
21
22    // 头删
23    DCListDelete(L->next);
24    DCListDelete(L->next);
25    DCListPrint(L);
26
27    // 尾删
28    DCListDelete(L->prev);
29    DCListDelete(L->prev);
30    DCListPrint(L);
31
32    // 中间插入
33    DCListInsert(DCListGetElem(L, 2), 100);
34    DCListPrint(L);
35
36    // 中间删除
37    DCListDelete(DCListGetElem(L, 2));
38    DCListPrint(L);
39
40    // 销毁链表
41    DCListDestroy(L);
42
43    return 0;
44}

二、顺序表和链表的比较

1. 对比

顺序表和链表都属于线性表，它们的逻辑结构都是线性结构。二者最大的区别在于存储结构，也就是物理结构不同。

顺序表使用一段连续的物理空间存储数据；链表中的结点可以分散存储在任意位置，各个结点通过指针连接起来。

<1>.顺序表

优点：

支持下标随机访问，访问任意位置元素的时间复杂度为 O(1)。
适合排序、二分查找、堆和优先级队列等操作。
数据连续存储，CPU 缓存命中率较高。
通常不会产生大量零散的内存碎片。

缺点：

在中间或头部插入、删除数据时，需要移动后面的元素，时间复杂度通常为 O(N)。
只有尾插和尾删在不扩容等理想情况下，时间复杂度可以达到 O(1)。
空间不足时需要扩容，扩容时通常需要申请新空间并复制原有数据。
扩容后可能会存在一定的空间浪费。

<2>.链表

优点：

按需申请和释放结点空间，不需要像顺序表一样整体扩容。
在已经确定插入或删除位置的情况下，双向链表可以在 O(1) 时间内完成插入和删除。
插入和删除时不需要整体移动其他元素。

缺点：

不支持下标随机访问，访问第 i 个结点通常需要从头遍历，时间复杂度为 O(N)。
每个结点需要额外保存指针，会增加空间开销。
结点在内存中不连续，CPU 缓存命中率通常低于顺序表。
频繁申请和释放小块内存，可能产生内存碎片。

需要特别注意一句：链表的插入和删除是 O(1)，前提是已经找到了对应结点。

对比项	顺序表	链表

物理存储	连续	不连续

随机访问	O(1)	O(N)

中间插入删除	O(N)	已知位置时 O(1)

扩容	需要	不需要整体扩容

额外空间	较少	需要保存指针

缓存命中率	较高	较低

总结：大量随机访问、排序和尾插时，更适合顺序表；频繁在已知位置插入和删除时，更适合链表。

《数据结构之双链表》是转载文章，点击查看原文。