C 语言数据结构（二）：序次表和链表

目次
1. 线性表
2. 序次表
2.1 概念及结构
2.1.1 静态序次表（不常用）
2.1.2 动态序次表（常用）
​编辑
2.2 训练
2.2.1 移除元素
2.2.2 删除有序数组中的重复项
2.2.3 归并两个有序数组
2.3 序次表存在的标题
3. 链表
3.1 概念及结构
3.2 链表的分类
​编辑
3.2.1 常用链表
3.2.1.1 无头单向非循环链表
3.2.1.2 带头双向循环链表
3.3 无头单向非循环链表的实现
3.4 带头双向循环链表的实现
4. 对比序次表和链表

   💬 ：如果你在阅读过程中有任何疑问或想要进一步探究的内容，接待在批评区各抒己见！我们一起学习、共同发展~！
  👍 ：如果你以为这篇文章还不错，不妨顺手点个赞、到场收藏，并分享给更多的朋侪噢~！
  

---

1. 线性表

   线性表（linear list）是 n 个具有雷同特性的数据元素的有限序列。它是一种在实际中广泛利用的数据结构。
  常见的线性表包罗：序次表、链表、栈、队列、字符串等。
  线性表在逻辑上是线性结构，即一条连续的直线。但是在物理结构上并不愿定是连续的，线性表在物理上存储时，通常以数组和链式结构的情势存储。

---

2. 序次表

2.1 概念及结构

   序次表是用一段物理所在连续的存储单元依次存储数据元素的线性结构，一样寻常接纳数组存储。在数组上完成数据的增删查改。
  

序次表一样寻常可以分为：静态序次表，动态序次表。
2.1.1 静态序次表（不常用）

静态序次表利用定长数组存储元素。存储数据前，必要预先确定命组的长度，且在步伐运行过程中数组长度不能改变。
示例：

1. #include <stdio.h>
2. #define N 7
4. // int 类型重命名为 SLDataType
5. typedef int SLDataType;
7. // 定义静态顺序表结构体
8. typedef struct SeqList     // 此结构体类型起了一个别名 SeqList
9. {
10.     SLDataType array[N];  // 定长数组
11.     size_t size;         
12.     // size_t 用于表示无符号整数类型，通常用于表示数组的索引、对象的大小等
13.     // size ：当前有效数据的个数
15. } SeqList;
17. void SeqListInit(SeqList* psl)
18. {
19.     psl->size = 0;   
20. }
22. // 向静态顺序表尾部插入数据
23. int SeqListPushBack(SeqList* psl, SLDataType x)
24. {
25.     if (psl->size >= N)
26.     {
27.         printf("顺序表已满，无法插入\n");
28.         return 0;
29.     }
31.     psl->array[psl->size] = x;
32.     psl->size++;   // 表示成功插入了一个数据
33.     return 1;
34. }
36. // 打印静态顺序表
37. void SeqListPrint(SeqList* psl)
38. {
39.     for (size_t i = 0; i < psl->size; i++)
40.     {
41.         printf("%d ", psl->array[i]);
42.     }
43.     printf("\n");
44. }
46. int main()
47. {
48.     SeqList sl;
49.     // 声明一个SeqList类型的变量sl，用于表示一个静态顺序表
51.     SeqListInit(&sl);
52.     SeqListPushBack(&sl, 1);
53.     SeqListPushBack(&sl, 2);
54.     SeqListPushBack(&sl, 3);
55.     SeqListPrint(&sl);
57.     return 0;
58. }

复制代码

2.1.2 动态序次表（常用）

动态序次表利用动态开辟的数组存储元素。可根据实际必要动态地增减数组的容量，以顺应数据量的变革。
示例：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <assert.h>
5. typedef int SLDataType;
6. // int 类型重命名为 SLDataType
8. typedef struct SeqList   // 此结构体类型起了一个别名 SeqList
9. {
10.     SLDataType* array;  // 指向动态开辟的数组
11.     size_t size;        // 顺序表中有效数据的个数
12.     size_t capacity;    // 顺序表当前容量大小
13. } SeqList;
15. // 顺序表初始化
16. void SeqListInit(SeqList* psl)
17. {
18.     // 检查传入的顺序表指针是否为空，若为空则终止程序
19.     assert(psl);
21.     // 初始化时先不分配空间，将数组指针置为 NULL
22.     psl->array = NULL;
23.    
24.     psl->size = 0;
25.     psl->capacity = 0;
26. }
28. // 检查空间，如果满了，进行增容
29. void CheckCapacity(SeqList* psl)
30. {
31.     assert(psl);
33.     // 当有效数据个数等于容量时，说明顺序表已满，需要增容
34.     if (psl->size == psl->capacity)
35.     {
36.         // 若当前容量为 0，先给一个初始容量，这里设为 4
37.         size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
39.         // 重新分配内存空间，大小为新容量乘以每个数据元素的大小
40.         SLDataType* tmp = (SLDataType*)realloc(psl->array, newCapacity * sizeof(SLDataType));
42.         // 检查内存分配是否成功，若失败则终止程序
43.         assert(tmp);
45.         // 更新数组指针为新分配的内存地址
46.         psl->array = tmp;
47.         
48.         psl->capacity = newCapacity;
49.     }
50. }
52. // 顺序表尾插
53. void SeqListPushBack(SeqList* psl, SLDataType x)
54. {
55.     assert(psl);
57.     // 插入元素前先检查是否需要增容
58.     CheckCapacity(psl);
60.     // 在顺序表的末尾插入新元素
61.     psl->array[psl->size] = x;
62.    
63.      // 有效数据个数加 1，表示插入一个元素
64.     psl->size++;
65. }
67. // 顺序表尾删
68. void SeqListPopBack(SeqList* psl)
69. {
70.     assert(psl);
72.     // 检查顺序表中是否有数据，若没有则终止程序
73.     assert(psl->size > 0);
75.     // 表示删除一个元素
76.     psl->size--;
77. }
79. // 顺序表头插
80. void SeqListPushFront(SeqList* psl, SLDataType x)
81. {
82.     assert(psl);
84.     // 插入元素前先检查是否需要增容
85.     CheckCapacity(psl);
87.     // 将顺序表中所有元素依次向后移动一位
88.     for (int i = psl->size; i > 0; i--)
89.     {
90.         psl->array[i] = psl->array[i - 1];
91.     }
93.     psl->array[0] = x;
94.    
95.     psl->size++;
96. }
98. // 顺序表头删
99. void SeqListPopFront(SeqList* psl)
100. {
101.     assert(psl);
103.     // 检查顺序表中是否有数据，若没有则终止程序
104.     assert(psl->size > 0);
106.     // 将顺序表中所有元素依次向前移动一位
107.     for (int i = 0; i < psl->size - 1; i++)
108.     {
109.         psl->array[i] = psl->array[i + 1];
110.     }
111.    
112.     psl->size--;
113. }
115. // 顺序表查找
116. int SeqListFind(SeqList* psl, SLDataType x)
117. {
118.     assert(psl);
119.    
120.     for (size_t i = 0; i < psl->size; i++)
121.     {
122.         // 若找到与目标元素相等的元素，返回其下标
123.         if (psl->array[i] == x)
124.         {
125.             return (int)i;
126.         }
127.     }
128.    
129.     return -1;
130. }
132. // 顺序表在 pos 位置插入 x
133. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
134. {
135.     assert(psl);
137.     // 检查插入位置是否合法，即不能小于 0 且不能大于当前有效数据个数
138.     assert(pos >= 0 && pos <= psl->size);
140.     // 插入元素前先检查是否需要增容
141.     CheckCapacity(psl);
143.     // 将 pos 位置及之后的元素依次向后移动一位
144.     for (size_t i = psl->size; i > pos; i--)
145.     {
146.         psl->array[i] = psl->array[i - 1];
147.     }
148.    
149.     psl->array[pos] = x;
150.    
151.     psl->size++;
152. }
154. // 顺序表删除 pos 位置的值
155. void SeqListErase(SeqList* psl, size_t pos)
156. {
157.     assert(psl);
159.     assert(pos >= 0 && pos < psl->size);
160.    
161.     for (size_t i = pos; i < psl->size - 1; i++)
162.     {
163.         psl->array[i] = psl->array[i + 1];
164.     }
165.    
166.     psl->size--;
167. }
169. // 顺序表销毁
170. void SeqListDestory(SeqList* psl)
171. {
172.     assert(psl);
174.     // 释放动态分配的数组内存
175.     free(psl->array);
177.     // 将数组指针置为 NULL，防止悬空指针
178.     psl->array = NULL;
179.    
180.     psl->size = 0;
181.    
182.     psl->capacity = 0;
183. }
185. void SeqListPrint(SeqList* psl)
186. {
187.     assert(psl);
188.    
189.     for (size_t i = 0; i < psl->size; i++)
190.     {
191.         printf("%d ", psl->array[i]);
192.     }
193.     printf("\n");
194. }
196. int main()
197. {
198.     SeqList sl;
199.     // 声明一个SeqList类型的变量sl，用于表示一个动态顺序表
201.     // 表尾插
202.     SeqListInit(&sl);
203.     SeqListPushBack(&sl, 1);
204.     SeqListPushBack(&sl, 2);
205.     SeqListPushBack(&sl, 3);
206.     SeqListPrint(&sl);
208.     // 表头插
209.     SeqListPushFront(&sl, 0);
210.     SeqListPrint(&sl);
212.     // 查找
213.     int index = SeqListFind(&sl, 2);
214.     if (index != -1)
215.     {
216.         printf("元素 2 在顺序表中的下标是: %d\n", index);
217.     }
218.     else
219.     {
220.         printf("未找到元素 2\n");
221.     }
223.     // 表尾删
224.     SeqListPopBack(&sl);
225.     SeqListPrint(&sl);
227.     // 表头删
228.     SeqListPopFront(&sl);
229.     SeqListPrint(&sl);
231.     // 指定位置插入值
232.     SeqListInsert(&sl, 1, 10);
233.     SeqListPrint(&sl);
235.     // 指定位置删除值
236.     SeqListErase(&sl, 1);
237.     SeqListPrint(&sl);
239.     // 顺序表销毁
240.     SeqListDestory(&sl);
242.     return 0;
243. }

复制代码

2.2 训练

2.2.1 移除元素

有一个数组和一个值 val，要求：

• 原地移除全部便是 val 的元素
  
• 返回数组中未便是 val （剩余）的元素的数目 k
  
• 新数组前 k 个元素包罗未便是 val 的元素
  

   “原地”：仅利用常数级别的额外空间，即空间复杂度为 O(1)。其算法直接在原始数据存储的内存位置上举行修改，而不是创建一个与原始数据规模相当的新数据结构来存储处置惩罚后的结果。

1. #include <stdio.h>
3. int removeElement(int* nums, int numsSize, int val)
4. {
5.     int k = 0;
6.    
7.     for (int i = 0; i < numsSize; i++)
8.     {
9.         if (nums[i] != val)
10.         {
11.             // 如果不等于 val，则将该元素放到数组的前 k 个位置
12.             nums[k] = nums[i];
13.             
14.             k++;
15.         }
16.     }
17.    
18.     return k;
19. }
21. int main()
22. {
23.     int nums[] = {3, 2, 2, 3};
24.     int numsSize = sizeof(nums) / sizeof(nums[0]);
25.     int val = 3;
27.     int newSize = removeElement(nums, numsSize, val);
28.     printf("剩余元素的数量: %d\n", newSize);
29.    
30.     printf("移除指定元素后的数组: ");
31.     for (int i = 0; i < newSize; i++)
32.     {
33.         printf("%d ", nums[i]);
34.     }
35.     printf("\n");
37.     return 0;
38. }

复制代码

只遍历数组一次，以是时间复杂度 O(n) ，n 为数组长度。
2.2.2 删除有序数组中的重复项

原地删除一个非严格递增分列的数组 nums 中重复的元素，使每个元素只出现一次，保持元素的相对序次稳固，返回新数组的长度 k ，新数组前 k 个元素包罗唯一元素。

1. #include <stdio.h>
3. int removeDuplicates(int* nums, int numsSize)
4. {
5.     if (numsSize == 0)
6.     {
7.         return 0;
8.     }
10.     int slow = 0;
12.     for (int fast = 1; fast < numsSize; fast++)
13.     {
14.         if (nums[fast] != nums[slow])
15.         {
16.             slow++;
17.             nums[slow] = nums[fast];
18.         }
19.     }
21.     return slow + 1;
22. }
24. int main()
25. {
26.     int nums[] = {1, 1, 2, 2, 2, 3, 4, 4, 5};
27.     int numsSize = sizeof(nums) / sizeof(nums[0]);
29.     int newLength = removeDuplicates(nums, numsSize);
31.     printf("删除重复元素后数组的新长度: %d\n", newLength);
32.     printf("删除重复元素后的数组: ");
33.     for (int i = 0; i < newLength; i++)
34.     {
35.         printf("%d ", nums[i]);
36.     }
37.     printf("\n");
39.     return 0;
40. }

复制代码

只遍历数组一次，以是时间复杂度 O(n) ，n 为数组长度。
2.2.3 归并两个有序数组

给定两个非递减排序的整数数组 nums1 和 nums2，及整数 m 和 n。
要求：

• nums1 初始长度是 m + n，前 m 个是待归并元素，后 n 个为 0 ；
  
• nums2 初始长度为 n；
  
• nums2 归并到 nums1 里，归并后数组保持非递减序次，归并后结果存于 nums1 中。
  

1. #include <stdio.h>
3. void merge(int* nums1, int m, int* nums2, int n)
4. {
5.     int p1 = m - 1;  // nums1 中最后一个“有效”元素的索引
6.     int p2 = n - 1;  // nums2 中最后一个元素的索引
7.     int p = m + n - 1;  // 合并后数组最后一个元素的索引
9.     // 从后往前比较两个数组的元素
10.     while (p1 >= 0 && p2 >= 0)
11.     {
12.         if (nums1[p1] > nums2[p2])
13.         {
14.             nums1[p] = nums1[p1];
15.             p1--;
16.         }
17.         else
18.         {
19.             nums1[p] = nums2[p2];
20.             p2--;
21.         }
22.         p--;
23.     }
25.     // 其中一个数组遍历完后，若 nums2 还有剩余元素，将其复制到 nums1 前面
26.     while (p2 >= 0)
27.     {
28.         nums1[p] = nums2[p2];
29.         p2--;
30.         p--;
31.     }
32. }
34. int main()
35. {
36.     int nums1[] = { 1, 2, 3, 0, 0, 0, 0, 0 };
37.     int m = 3;
38.     int nums2[] = { 0, 2, 5, 6, 7 };
39.     int n = 5;
41.     merge(nums1, m, nums2, n);
43.     for (int i = 0; i < m + n; i++)
44.     {
45.         printf("%d ", nums1[i]);
46.     }
47.     printf("\n");
49.     return 0;
50. }

复制代码

对比nums1[p]每次比力后的数组

nums1[7] = 71，2，3，0，0，0，0，7

nums1[6] = 61，2，3，0，0，0，6，7

nums1[5] = 51，2，3，0，0，5，6，7

nums1[4] = 31，2，3，0，3，5，6，7

nums1[3] = 21，2，3，2，3，5，6，7

nums1[2] = 21，2，2，2，3，5，6，7

nums1[1] = 11，1，2，2，3，5，6，7 然后 p1 = -1，p2 = 0，p = 0，实行第二个 while 循环，nums1[0] = nums2[0] = 0 ，得到归并数组{0，1，2，2，3，5，6，7} 。
别的，只遍历数组 nums1 和 nums2 一次，以是时间复杂度为 O(m+n) 。
2.3 序次表存在的标题

序次表存在以下标题：

• 举行中心或表头插入、删除操纵时，时间复杂度达 O (N)。
  
• 增容要申请新空间、拷贝数据、开释旧空间，斲丧大。
  
• 扩容一样寻常扩大为原来的 2 倍，若插入数据少，造成空间浪费。
  

为办理这些标题，下面先容链表结构。

---

3. 链表

3.1 概念及结构

   链表是一种物理存储结构上非连续、非序次的存储结构，数据元素的逻辑序次是通过链表中的指针链接序次实现的 。
  链表在逻辑上是连续的，但是——链表节点一样寻常从堆上申请空间，而堆上空间的分配依据肯定计谋举行，导致两次申请的空间大概连续，也大概不连续——以是链表的物理存储所在不愿定连续。

3.2 链表的分类

• 单向/双向
  

• 带头/不带头
  

• 循环/非循环
  

3.2.1 常用链表

3.2.1.1 无头单向非循环链表

结构简朴，一样寻常不会单独用来存数据。实际中更多作为其他数据结构的子结构，如哈希桶、图的毗邻表等。别的这种结构在笔试口试中较常见。
3.2.1.2 带头双向循环链表

结构最复杂，一样寻常用来单独存储数据。实际中利用的链表数据结构多是带头双向循环链表。
3.3 无头单向非循环链表的实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int SLTDateType;
6. // 定义链表节点结构体
7. typedef struct SListNode
8. {
9.     SLTDateType data;  // 节点存储的数据
10.     struct SListNode* next;  // 指向下一个节点的指针
11. }SListNode;
13. // 动态申请一个节点
14. SListNode* BuySListNode(SLTDateType x)
15. {
16.     // 为新节点分配内存空间
17.     SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
18.     if (newNode == NULL)
19.     {
20.         perror("malloc");
21.         return NULL;
22.     }
23.     // 初始化新节点的数据
24.     newNode->data = x;
26.     // 新节点的下一个节点初始化为空
27.     newNode->next = NULL;
29.     return newNode;
30. }
32. void SListPrint(SListNode* plist)
33. {
34.     SListNode* cur = plist;
35.     // plist 是指向链表头节点的指针
37.     while (cur != NULL)
38.     // 无头单向非循环链表的末尾节点的 next 指针始终被设置为 NULL
39.     {
40.         // 打印当前节点的数据
41.         printf("%d -> ", cur->data);
42.         // 移动到下一个节点
43.         cur = cur->next;
44.     }
45.     // 打印链表结束标志
46.     printf("NULL\n");
47. }
49. // 尾插
50. void SListPushBack(SListNode** pplist, SLTDateType x)
51. {
52.     // 创建新节点
53.     SListNode* newNode = BuySListNode(x);
54.     if (*pplist == NULL)
55.     {
56.         // 如果链表为空，新节点就是链表的头节点
57.         *pplist = newNode;
58.     }
59.     else
60.     {
61.         // 找到链表的尾节点
62.         SListNode* tail = *pplist;
63.         while (tail->next != NULL)
64.         {
65.             tail = tail->next;
66.         }
67.         
68.         tail->next = newNode;
69.     }
70. }
72. // 头插
73. void SListPushFront(SListNode** pplist, SLTDateType x)
74. {
75.     SListNode* newNode = BuySListNode(x);
77.     // 新节点的下一个节点指向原来的头节点
78.     newNode->next = *pplist;
79.    
80.     *pplist = newNode;
81. }
83. // 尾删
84. void SListPopBack(SListNode** pplist)
85. {
86.     if (*pplist == NULL)   // 若链表为空
87.     {
88.         return;   // 函数立即终止执行
89.     }
90.     if ((*pplist)->next == NULL)
91.     {
92.         // 如果链表只有一个节点，释放该节点并将头指针置空
93.         free(*pplist);
94.         *pplist = NULL;
95.     }
96.     else
97.     {
98.         SListNode* prev = NULL;
99.         SListNode* tail = *pplist;
100.         while (tail->next != NULL)
101.         {
102.             prev = tail;
103.             tail = tail->next;
104.         }
105.         // 最后一次循环中，prev 被赋为 tail 的前一个节点，tail 移到了尾节点
106.         
107.         free(tail);
109.         // 倒数第二个节点的下一个节点置空
110.         prev->next = NULL;
111.     }
112. }
114. // 头删
115. void SListPopFront(SListNode** pplist)
116. {
117.     if (*pplist == NULL)
118.     {
119.         return;
120.     }
121.     // 保存原来的头节点
122.     SListNode* first = *pplist;
123.     // 更新头节点为原来头节点的下一个节点
124.     *pplist = first->next;
125.     // 释放原来的头节点
126.     free(first);
127. }
129. // 查找
130. SListNode* SListFind(SListNode* plist, SLTDateType x)
131. {
132.     // 遍历链表，查找值为x的节点
133.     SListNode* cur = plist;
134.     while (cur != NULL)
135.     {
136.         if (cur->data == x)
137.         {
138.             return cur;
139.         }
140.         
141.         cur = cur->next;
142.     }
143.    
144.     return NULL;
145. }
147. // 在pos的后一个位置插入值 x
148. void SListInsertAfter(SListNode* pos, SLTDateType x)
149. {
150.     if (pos == NULL)
151.     {
152.         return;
153.     }
154.    
155.     SListNode* newNode = BuySListNode(x);
156.    
157.     newNode->next = pos->next;
158.    
159.     pos->next = newNode;
160. }
162. // 删除pos后一个位置的值
163. void SListEraseAfter(SListNode* pos)
164. {
165.     if (pos == NULL || pos->next == NULL)   // 如果pos为空或者pos是尾节点
166.     {
167.         return;
168.     }
169.     // 保存pos节点的下一个节点
170.     SListNode* nextNode = pos->next;
171.     // pos节点的下一个节点指向要删除节点的下一个节点
172.     pos->next = nextNode->next;
173.     free(nextNode);
174. }
176. int main()
177. {
178.     SListNode* list = NULL;   
179.     // 声明并初始化一个指向 SListNode 类型结构体的指针 list
180.     // 用于表示初始为空的链表
182.     // 尾插
183.     SListPushBack(&list, 1);
184.     SListPushBack(&list, 2);
185.     SListPushBack(&list, 3);
186.     SListPrint(list);
188.     // 头插
189.     SListPushFront(&list, 0);
190.     SListPrint(list);
192.     // 尾删
193.     SListPopBack(&list);
194.     SListPrint(list);
196.     // 头删
197.     SListPopFront(&list);
198.     SListPrint(list);
200.     // 查找
201.     SListNode* found = SListFind(list, 2);
202.     if (found)
203.     {
204.         printf("Found: %d\n", found->data);
205.     }
206.     else
207.     {
208.         printf("Not found\n");
209.     }
210.     // 在pos的后一个位置插入值
211.     SListInsertAfter(list, 4);
212.     SListPrint(list);
213.     // 删除pos后一个位置的值
214.     SListEraseAfter(list);
215.     SListPrint(list);
217.     return 0;
218. }

复制代码

“无头单向非循环链表的末端节点的 next 指针始终被设置为 NULL”：

• 节点创建：新节点创建时，next 指针初始化为 NULL。
  
• 尾插操纵：尾插新节点时，若链表为空，新节点成头节点，next 为 NULL；若不为空，找到尾节点，将其 next 指向新节点（新节点 next 已初始化为 NULL）。
  
• 尾删操纵：尾删时，若链表仅一个节点，开释后链表为空；如有多个节点，开释尾节点，将倒数第二个节点的 next 置为 NULL。
  

思索：为什么在pos的后一个位置插入值，而非前一个位置？为什么不删除 pos 位置节点？
（1）单向链表只能从前向后遍历，没有指向前一节点的指针，无法直接获取 pos 节点的前一个节点，因此只能重新节点开始依次遍历链表，直到找到 pos 节点的前一个节点，时间复杂度达 O(n)；而在 pos 后插入，只改两个指针，时间复杂度为 O(1)。
（2）删除 pos 位置节点需找到其前一节点，时间复杂度达 O(n)；而删除 pos 后节点，只改一个指针，时间复杂度为 O(1)。
3.4 带头双向循环链表的实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int LTDataType;
6. typedef struct ListNode
7. {
8.     LTDataType _data;  // 节点存储的数据
9.     struct ListNode* next;  // 指向下一个节点的指针
10.     struct ListNode* prev;  // 指向前一个节点的指针
11. }ListNode;
13. // 创建返回链表的头结点
14. ListNode* ListCreate()
15. {
16.     // 为头节点分配内存
17.     ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
18.     if (phead == NULL)
19.     {
20.         perror("malloc fail");
21.         return NULL;
22.     }
23.     // 头节点的 next 和 prev 都指向自身，形成循环
24.     phead->next = phead;
25.     phead->prev = phead;
26.     return phead;
27. }
29. // 双向链表销毁
30. void ListDestory(ListNode* plist)
31. {
32.     // 从头节点的下一个节点开始遍历
33.     ListNode* cur = plist->next;
34.     while (cur != plist)
35.     {
36.         // 保存当前节点的下一个节点
37.         ListNode* next = cur->next;
38.         
39.         free(cur);
40.         cur = next;
41.     }
42.     // 最后释放头节点的内存
43.     free(plist);
44. }
46. void ListPrint(ListNode* plist)
47. {
48.     ListNode* cur = plist->next;
49.     while (cur != plist)
50.     {
51.         printf("%d ", cur->_data);
52.         cur = cur->next;
53.     }
54.     printf("\n");
55. }
57. // 尾插
58. void ListPushBack(ListNode* plist, LTDataType x)
59. {
60.     // 创建新节点
61.     ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
62.     if (newnode == NULL)
63.     {
64.         perror("malloc fail");
65.         return;
66.     }
67.     newnode->_data = x;
68.     // 找到尾节点
69.     ListNode* tail = plist->prev;
70.     // 插入新节点
71.     tail->next = newnode;
72.     newnode->prev = tail;
73.     newnode->next = plist;
74.     plist->prev = newnode;
75. }
77. // 尾删
78. void ListPopBack(ListNode* plist)
79. {
80.     // 检查链表是否为空
81.     if (plist->next == plist)
82.     {
83.         return;
84.     }
85.     // 找到尾节点
86.     ListNode* tail = plist->prev;
87.     // 找到尾节点的前一个节点
88.     ListNode* prev = tail->prev;
89.    
90.     free(tail);
92.     // 更新指针
93.     prev->next = plist;
94.     plist->prev = prev;
95. }
97. // 头插
98. void ListPushFront(ListNode* plist, LTDataType x)
99. {
100.     ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
101.     if (newnode == NULL)
102.     {
103.         perror("malloc fail");
104.         return;
105.     }
106.     newnode->_data = x;
107.     // 保存头节点的下一个节点
108.     ListNode* first = plist->next;
109.     // 插入新节点
110.     plist->next = newnode;
111.     newnode->prev = plist;
112.     newnode->next = first;
113.     first->prev = newnode;
114. }
116. // 头删
117. void ListPopFront(ListNode* plist)
118. {
119.     // 检查链表是否为空
120.     if (plist->next == plist)
121.     {
122.         return;
123.     }
124.     // 保存头节点的下一个节点
125.     ListNode* first = plist->next;
126.     // 保存头节点的下下一个节点
127.     ListNode* second = first->next;
128.     // 释放头节点的下一个节点的内存
129.     free(first);
130.     // 更新指针
131.     plist->next = second;
132.     second->prev = plist;
133. }
135. // 查找
136. ListNode* ListFind(ListNode* plist, LTDataType x)
137. {
138.     // 从头节点的下一个节点开始遍历
139.     ListNode* cur = plist->next;
140.     while (cur != plist)
141.     {
142.         if (cur->_data == x)
143.         {
144.             return cur;
145.         }
146.         cur = cur->next;
147.     }
148.     return NULL;
149. }
151. // 在pos的前一个位置插入
152. void ListInsert(ListNode* pos, LTDataType x)
153. {
154.     ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
155.     if (newnode == NULL)
156.     {
157.         perror("malloc fail");
158.         return;
159.     }
160.     newnode->_data = x;
161.     // 找到 pos 节点的前一个节点
162.     ListNode* prev = pos->prev;
163.     // 插入新节点
164.     prev->next = newnode;
165.     newnode->prev = prev;
166.     newnode->next = pos;
167.     pos->prev = newnode;
168. }
170. // 删除pos位置的节点
171. void ListErase(ListNode* pos)
172. {
173.     ListNode* prev = pos->prev;
174.    
175.     ListNode* next = pos->next;
176.    
177.     free(pos);
179.     // 更新指针
180.     prev->next = next;
181.     next->prev = prev;
182. }
184. int main()
185. {
186.     ListNode* plist = ListCreate();
187.     // 调用 ListCreate 创建带头双向循环链表，并将返回的头节点指针赋值给 plist
189.     ListPushBack(plist, 1);
190.     ListPushBack(plist, 2);
191.     ListPushBack(plist, 3);
192.     ListPrint(plist);
194.     ListPushFront(plist, 0);
195.     ListPrint(plist);
197.     ListPopBack(plist);
198.     ListPrint(plist);
200.     ListPopFront(plist);
201.     ListPrint(plist);
203.     ListNode* pos = ListFind(plist, 2);
204.     if (pos)
205.     {
206.         ListInsert(pos, 4);
207.         ListPrint(plist);
208.     }
210.     pos = ListFind(plist, 4);
211.     if (pos)
212.     {
213.         ListErase(pos);
214.         ListPrint(plist);
215.     }
217.     ListDestory(plist);
219.     return 0;
220. }

复制代码

---

4. 对比序次表和链表

对比维度序次表链表存储空间物理存储上肯定连续逻辑上数据元素连续，但物理内存中不愿定连续，节点通过指针相互毗连随机访问支持随机访问，通过下标可直接定位元素，时间复杂度为 O (1)需从表头开始，逐个通过指针遍历查找元素，时间复杂度为 O (N)插入和删除操纵在恣意位置插入或删除元素时，大概需移动后续元素，服从较低，时间复杂度为 O (N)插入或删除元素时，仅需修改干系节点的指针指向，操纵相对轻巧插入特性动态序次表空间不敷时，需举行扩容，涉及重新分配内存、数据拷贝等步调没有容量限定，可随时动态创建和删除节点应用场景恰当元素高效存储且频仍访问的场景，如数组实现的线性表实用于数据插入和删除操纵频仍的场景，如实现队列、栈等数据结构缓存利用率物理存储连续，符合局部性原理，读取数据时相邻数据易一同加载到缓存中，缓存利用率高节点物理位置分散，难以充实利用缓存，缓存利用率较低