一、链表概念
链表是什么？链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
简单理解一下便是：链表可以近似的看作成火车，用节点一个一个串起来，需要操作时运用节点进行操作。
其特点如下：
链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc），每个节点包括两个部分：
一个是存储数据元素的数据域
另一个是存储下一个节点地址的指针域
链表可分为以下几类：
| 带头 | 不带头 |
| 单向 | 双向 |
| 循环 | 不循环 |
一共为8种组合（2*2*2），可用下图表示： 
虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构： 单向不带头不循环链表（单链表） 和 双向带头循环链表（双链表）。
原因如下：
1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构。
2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带 来很多优势，实现反⽽简单了。
二、单链表的实现
我们在实现链表时其实现目的与顺序表类似，无外乎为：“增删查改”四大功能。
2.1 定义结点
1. typedef int SLTDataType;//使用目的：方便更改数据类型 2. typedef struct SListNode 3. { 4. struct SListNode* next; 5. SLTDataType date; 6. }SLTNode;
注意：在定义节点（写成此结点也无所谓）时不要写成：SLTNode* next;因为编译器把结构体读完时才能达成重写条件。
2.2 具体实现功能如下：
1. void SLTPrint(SLTNode* phead); 2. 3. //头部插入删除/尾部插入删除 4. void SLTPushBack(SLTNode** pphead, SLTDataType x); 5. void SLTPushFront(SLTNode** pphead, SLTDataType x); 6. void SLTPopBack(SLTNode** pphead); 7. void SLTPopFront(SLTNode** pphead); 8. 9. //查找 10. SLTNode* SLTFind(SLTNode* phead, SLTDataType x); 11. //在指定位置之前插入数据 12. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); 13. //删除pos节点 14. void SLTErase(SLTNode** pphead, SLTNode* pos); 15. //在指定位置之后插入数据 16. void SLTInsertAfter(SLTNode* pos, SLTDataType x); 17. //删除pos之后的节点 18. void SLTEraseAfter(SLTNode* pos); 19. //销毁链表 20. void SListDesTroy(SLTNode** pphead);
接下来会带领大家一个一个实现。
2.3 单链表打印
1. void SLTPrint(SLTNode* phead) 2. { 3. SLTNode* p = p; 4. while (p) 5. { 6. printf("%d-> ", p->date); 7. } 8. printf("NULL\n"); 9. }
在对链表进行打印时，我们不能像打印顺序表那样那样用for循环进行遍历， 因为链表在内存中并不是像顺序表线性存放，而是靠节点进行联系。在此处我们是否需要assert断言吗？大家可以稍作思考。
答案是不需要，原因如下：若链表为空，不会进入for循环，直接打印NULL。
2.4单链表插入
单链表插入像顺序表一样分为：头插与尾插，接下来会一一实现。
2.4.1 尾插
1. Node* SLTBuyNode(SLTDataType x) 2. { 3. SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); 4. if (node == NULL) 5. { 6. return -1; 7. } 8. node->date = x; 9. node->next = NULL; 10. return node; 11. } 12. void SLTPushBack(SLTNode** pphead, SLTDataType x)//此处可猜测一下为什么使用二级指针 13. { 14. assert(*pphead); 15. SLTNode* newnode = SLTBuyNode(x);//因创建新节点方法会被多次使用，于是便单独封装出来 16. if (*pphead == NULL) 17. { 18. *pphead = pphead; 19. } 20. else 21. { 22. SLTNode* p = *pphead; 23. while (p) 24. { 25. p = p->next; 26. } 27. p->next = newnode; 28. } 29. }
在进行尾插时要注意以下几点 ：
首先，要使用二级指针来接收。在进行测试时发现使用一级指针无法改变实参，要改变实参只能传地址，一级指针传地址要用二级指针来接收。
其次，要考虑头节点为零的情况。在头节点为空时，新开辟的节点便是我们要插入的节点。
最后，为了使以后方便我们便创建了一个方法，需要使用使直接调用即可。
2.4.2头插
1. void SLTPushFront(SLTNode** pphead, SLTDataType x) 2. { 3. assert(*pphead); 4. SLTNode* newnode = SLTBuyNode(x); 5. newnode->next = *pphead; 6. *pphead = newnode; 7. }
头插的代码相较于尾插能简单一点，只需要将新开辟出的节点的指向改成头节点，将头节点改为新开辟的节点即可。
2.5 单链表删除
和插入一样，单链表的删除同样分为头删和尾删。
2.5.1 尾删
1. void SLTPopBack(SLTNode** pphead) 2. { 3. assert(pphead && *pphead); 4. if ((*pphead)->next == NULL) 5. { 6. free(*pphead); 7. *pphead = NULL; 8. } 9. else 10. { 11. SLTNode* p = *pphead; 12. SLTNode* n; 13. while (p->next) 14. { 15. n = p; 16. p = p->next; 17. } 18. free(p); 19. p = NULL; 20. n->next = NULL; 21. //法二 22. //SLTNode* p = *pphead; 23. //while(p->next->next) 24. //{ 25. // p = p->next; 26. //} 27. //free(p->next); 28. //p->next = NULL; 29. } 30. }
写尾删注意如下：
1.考虑到只有一个头节点。即该头节点指向空，可直接对其释放。
2.若不为空，可使用两种方法：双指针或创造出的指针向后多指向一次。
3.别忘记释放和置空。
2.5.2 头删
1. void SLTPopFront(SLTNode** pphead) 2. { 3. assert(pphead && *pphead); 4. SLTNode* next = (*pphead)->next; 5. free(*pphead); 6. *pphead = next; 7. }
以上便是头删实现无需考虑情况，因为该节点若为头节点那它所指向的即为NULL。只需定义一个指向下一位的节点即可。
2.6 单链表关于指定节点的增与删
2.6.1在指定位置之前插入数据
1. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) 2. { 3. assert(pphead && *pphead); 4. assert(pos); 5. SLTNode* newnode = SLTBuyNode(x); 6. SLTNode* p = *pphead; 7. if (pos == *pphead) 8. { 9. //调用头插 10. SLTPushFront(pphead, x); 11. } 12. else 13. { 14. while (p->next != pos) 15. { 16. p = p->next; 17. } 18. newnode->next = pos; 19. p->next = newnode; 20. } 21. }
在经行插入数据时，我们要创造头节点以及分析是否要分类讨论。
2.6.2 在指定位置之后插入数据
1. void SLTInsertAfter(SLTNode* pos, SLTDataType x) 2. { 3. assert(pos); 4. SLTNode* newnode = SLTBuyNode(x); 5. newnode->next = pos->next; 6. pos->next = newnode; 7. }
这种插入代码比较简单创造出节点后即可快速完成。
2.6.3删除pos节点
1. void SLTErase(SLTNode** pphead, SLTNode* pos) 2. { 3. assert(pphead && *pphead); 4. assert(pos); 5. if (pos == *pphead) 6. { 7. //调用头删 8. SLTPopFront(pphead); 9. } 10. else 11. { 12. SLTNode* p = *pphead; 13. while (p->next != pos) 14. { 15. p = p->next; 16. } 17. p->next = pos->next; 18. free(p->next); 19. p->next = NULL; 20. } 21. }
代码与之前插入类似。
2.6.4 删除pos之后的节点
1. void SLTEraseAfter(SLTNode* pos) 2. { 3. assert(pos); 4. SLTNode* p = pos->next; 5. pos->next = p->next; 6. free(p); 7. p = NULL; 8. }
2.7 销毁链表
1. void SListDesTroy(SLTNode** pphead) 2. { 3. SLTNode* p = *pphead; 4. SLTNode* n = *pphead; 5. while (p) 6. { 7. n = p->next; 8. free(p); 9. p = n; 10. } 11. *pphead = NULL; 12. }
好了，以上便是我们单链表的学习了，请大家休息片刻，我们随后开始双链表的学习。
三、双链表的实现
接下来，我们来学习双链表。双链表与单链表有相同也有不同，大家可在学习中自行体会。（在该链表使用一级指针而不用二级指针后面会说明）
3.1 双链表初始化
1. LTNode* LTInit(LTDataType x) 2. { 3. LTNode* phead = LTBuyNode(x); 4. return phead; 5. } 6. LTNode* LTBuyNode(LTDataType x) 7. { 8. LTNode* node = (LTNode*)malloc(sizeof(LTNode)); 9. if (node == NULL) 10. { 11. return -1; 12. } 13. node->date = x; 14. node->next = node; 15. node->prve = node; 16. return node; 17. }
这里的LTBuyNode与上文单链表功能类似都是为了便于后面的使用。单、双链表的不同已在上文呈现，这里不过多介绍。
3.2 功能实现
1. LTNode* LTInit(LTDataType x);//初始化 2. void LTDestroy(LTNode* phead);//销毁 3. void LTPrint(LTNode* phead);//打印 4. void LTPushBack(LTNode* phead, LTDataType x);//尾插 5. void LTPopBack(LTNode* phead);//尾删 6. 7. void LTPushFront(LTNode* phead, LTDataType x);//头插 8. void LTPopFront(LTNode* phead);//头删 9. 10. void LTInsert(LTNode* pos, LTDataType x);//在pos位置之后插入数据 11. void LTErase(LTNode* pos);//删除pos位置数据 12. LTNode* LTFind(LTNode* phead, LTDataType x);//查找数据
3.3 头插与尾插
3.3.1 尾插
1. void LTPushBack(LTNode* phead, LTDataType x)//尾插 2. { 3. assert(phead); 4. LTNode* newnode = LTBuyNode(x); 5. newnode->next = phead; 6. newnode->prve = phead->prve; 7. phead->prve->next = newnode;//不可颠倒 8. phead->prve = newnode; 9. }
注意：后俩行代码位置不可交换。
3.3.2 头插
1. void LTPushFront(LTNode* phead, LTDataType x) 2. { 3. assert(phead); 4. LTNode* newnode = LTBuyNode(x); 5. newnode->next = phead->next; 6. newnode->prve = phead; 7. phead->next->prve = newnode; 8. phead->next = newnode; 9. }
注意点还是一样即：后俩行代码位置不可交换。
3.4 头删与尾删
3.4.1 头删
1. void LTPopFront(LTNode* phead) 2. { 3. assert(phead && phead->next != phead); 4. LTNode* del = phead->next; 5. phead->next = del->prve; 6. del->next->prve = phead; 7. free(del); 8. del = NULL; 9. }
注意：断言时要加入后半句，否则会删掉哨兵位。
3.4.2 尾删
1. void LTPopBack(LTNode* phead) 2. { 3. assert(phead && phead->next != phead); 4. LTNode* del = phead->prve; 5. phead->prve = del->prve; 6. del->prve->next = phead; 7. free(del); 8. del = NULL; 9. }
注意点还是一样，断言要加入后半句。
3.5 指定位置插入、修改数据
3.5.1 指定位置后插入数据
1. void LTInsert(LTNode* pos, LTDataType x) 2. { 3. assert(pos); 4. LTNode* newnode = LTBuyNode(x); 5. newnode->next = pos->next; 6. newnode->prve = pos; 7. pos->next->prve = newnode; 8. pos->next = newnode; 9. }
注意：最后两行代码顺序不可修改。
3.5.2 删除pos位置数据
1. void LTErase(LTNode* pos) 2. { 3. assert(pos); 4. pos->next->prve = pos->prve; 5. pos->prve->next = pos->next; 6. free(pos); 7. pos = NULL; 8. }
3.6 查找数据
1. LTNode* LTFind(LTNode* phead, LTDataType x) 2. { 3. assert(phead); 4. LTNode* p = phead->next; 5. while (p != phead) 6. { 7. if (p->date == x) 8. { 9. return p; 10. } 11. p = p->next; 12. } 13. return NULL; 14. }
3.6 打印链表
1. void LTPrint(LTNode* phead) 2. { 3. LTNode* p = phead->next; 4. while (p!=phead) 5. { 6. printf("%d->", p->date); 7. p = p->next; 8. } 9. printf("NULL\n"); 10. }
打印方法与单链表类似。
3.7 销毁链表
1. void LTDestroy(LTNode* phead) 2. { 3. LTNode* p = phead->next; 4. LTNode* n = phead->next; 5. while (p != phead) 6. { 7. n = p->next; 8. free(p); 9. p = n; 10. } 11. //此时p指向phead，phead还没销毁 12. free(phead); 13. phead = NULL; 14. } 15. //存在问题传入一级指针后实参不会修改为NULL，需要手动修改
3.8 总结
为什么使用一级指针而不用二级指针？
1.传入数据之前，链表要进行初始化，为了保护哨兵位，使用一级指针即可，若使用二级指针不会改变哨兵位也可以使用，不过还是推荐使用一级指针。
2. 保持接口一致性，减少记忆成本。此链表接口过多，如若一会一级指针，一会二级指针会造成记忆成本。
四、顺序表和双向链表的优缺点分析
| 不同点 | 顺序表 | 链表（单链表） |
| 存储空间上 | 物理上⼀定连续 | 逻辑上连续，但物理上不⼀定连续 |
| 随机访问 | ⽀持O(1) | 不⽀持：O(N) |
| 任意位置插⼊或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩 容 | 没有容量的概念 |
| 应用场景 | 元素⾼效存储+频繁访问 | 任意位置插⼊和删除频繁 |
五、代码展示
5.1 单链表
5.1.1slist.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include"slist.h" 3. void SLTPrint(SLTNode* phead) 4. { 5. SLTNode* p = p; 6. while (p) 7. { 8. printf("%d-> ", p->date); 9. } 10. printf("NULL\n"); 11. } 12. SLTNode* SLTBuyNode(SLTDataType x) 13. { 14. SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); 15. if (node == NULL) 16. { 17. return -1; 18. } 19. node->date = x; 20. node->next = NULL; 21. return node; 22. } 23. void SLTPushBack(SLTNode** pphead, SLTDataType x)//此处可猜测一下为什么使用二级指针 24. { 25. assert(*pphead); 26. SLTNode* newnode = SLTBuyNode(x);//因创建新节点方法会被多次使用，于是便单独封装出来 27. if (*pphead == NULL) 28. { 29. *pphead = pphead; 30. } 31. else 32. { 33. SLTNode* p = *pphead; 34. while (p) 35. { 36. p = p->next; 37. } 38. p->next = newnode; 39. } 40. } 41. void SLTPushFront(SLTNode** pphead, SLTDataType x) 42. { 43. assert(*pphead); 44. SLTNode* newnode = SLTBuyNode(x); 45. newnode->next = *pphead; 46. *pphead = newnode; 47. } 48. void SLTPopBack(SLTNode** pphead) 49. { 50. assert(pphead && *pphead); 51. if ((*pphead)->next == NULL) 52. { 53. free(*pphead); 54. *pphead = NULL; 55. } 56. else 57. { 58. SLTNode* p = *pphead; 59. SLTNode* n; 60. while (p->next) 61. { 62. n = p; 63. p = p->next; 64. } 65. free(p); 66. p = NULL; 67. n->next = NULL; 68. //法二 69. //SLTNode* p = *pphead; 70. //while(p->next->next) 71. //{ 72. // p = p->next; 73. //} 74. //free(p->next); 75. //p->next = NULL; 76. } 77. } 78. void SLTPopFront(SLTNode** pphead) 79. { 80. assert(pphead && *pphead); 81. SLTNode* next = (*pphead)->next; 82. free(*pphead); 83. *pphead = next; 84. } 85. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) 86. { 87. assert(pphead && *pphead); 88. assert(pos); 89. SLTNode* newnode = SLTBuyNode(x); 90. SLTNode* p = *pphead; 91. if (pos == *pphead) 92. { 93. //调用头插 94. SLTPushFront(pphead, x); 95. } 96. else 97. { 98. while (p->next != pos) 99. { 100. p = p->next; 101. } 102. newnode->next = pos; 103. p->next = newnode; 104. } 105. } 106. void SLTInsertAfter(SLTNode* pos, SLTDataType x) 107. { 108. assert(pos); 109. SLTNode* newnode = SLTBuyNode(x); 110. newnode->next = pos->next;//位置不可颠倒 111. pos->next = newnode; 112. } 113. void SLTErase(SLTNode** pphead, SLTNode* pos) 114. { 115. assert(pphead && *pphead); 116. assert(pos); 117. if (pos == *pphead) 118. { 119. //调用头删 120. SLTPopFront(pphead); 121. } 122. else 123. { 124. SLTNode* p = *pphead; 125. while (p->next != pos) 126. { 127. p = p->next; 128. } 129. p->next = pos->next; 130. free(p->next); 131. p->next = NULL; 132. } 133. } 134. void SLTEraseAfter(SLTNode* pos) 135. { 136. assert(pos); 137. SLTNode* p = pos->next; 138. pos->next = p->next; 139. free(p); 140. p = NULL; 141. } 142. void SListDesTroy(SLTNode** pphead) 143. { 144. SLTNode* p = *pphead; 145. SLTNode* n = *pphead; 146. while (p) 147. { 148. n = p->next; 149. free(p); 150. p = n; 151. } 152. *pphead = NULL; 153. }
5.1.2 slist.h
1. #pragma once 2. #include<stdio.h> 3. #include<stdlib.h> 4. #include<assert.h> 5. typedef int SLTDataType;//使用目的：方便更改数据类型 6. typedef struct SListNode 7. { 8. struct SListNode* next; 9. SLTDataType date; 10. }SLTNode; 11. 12. 13. void SLTPrint(SLTNode* phead); 14. 15. //头部插入删除/尾部插入删除 16. void SLTPushBack(SLTNode** pphead, SLTDataType x); 17. void SLTPushFront(SLTNode** pphead, SLTDataType x); 18. void SLTPopBack(SLTNode** pphead); 19. void SLTPopFront(SLTNode** pphead); 20. 21. //查找 22. SLTNode* SLTFind(SLTNode* phead, SLTDataType x); 23. //在指定位置之前插入数据 24. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); 25. //删除pos节点 26. void SLTErase(SLTNode** pphead, SLTNode* pos); 27. //在指定位置之后插入数据 28. void SLTInsertAfter(SLTNode* pos, SLTDataType x); 29. //删除pos之后的节点 30. void SLTEraseAfter(SLTNode* pos); 31. //销毁链表 32. void SListDesTroy(SLTNode** pphead);
5.2 双链表
5.2.1 list.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include"list.h" 3. LTNode* LTInit(LTDataType x) 4. { 5. LTNode* phead = LTBuyNode(x); 6. return phead; 7. } 8. void LTDestroy(LTNode* phead) 9. { 10. LTNode* p = phead->next; 11. LTNode* n = phead->next; 12. while (p != phead) 13. { 14. n = p->next; 15. free(p); 16. p = n; 17. } 18. //此时p指向phead，phead还没销毁 19. free(phead); 20. phead = NULL; 21. } 22. void LTPrint(LTNode* phead) 23. { 24. LTNode* p = phead->next; 25. while (p!=phead) 26. { 27. printf("%d->", p->date); 28. p = p->next; 29. } 30. printf("NULL\n"); 31. } 32. LTNode* LTBuyNode(LTDataType x) 33. { 34. LTNode* node = (LTNode*)malloc(sizeof(LTNode)); 35. if (node == NULL) 36. { 37. return -1; 38. } 39. node->date = x; 40. node->next = node; 41. node->prve = node; 42. return node; 43. } 44. void LTPushBack(LTNode* phead, LTDataType x)//尾插 45. { 46. assert(phead); 47. LTNode* newnode = LTBuyNode(x); 48. newnode->next = phead; 49. newnode->prve = phead->prve; 50. phead->prve->next = newnode;//不可颠倒 51. phead->prve = newnode; 52. } 53. void LTPopBack(LTNode* phead) 54. { 55. assert(phead && phead->next != phead); 56. LTNode* del = phead->prve; 57. phead->prve = del->prve; 58. del->prve->next = phead; 59. free(del); 60. del = NULL; 61. } 62. 63. void LTPushFront(LTNode* phead, LTDataType x) 64. { 65. assert(phead); 66. LTNode* newnode = LTBuyNode(x); 67. newnode->next = phead->next; 68. newnode->prve = phead; 69. phead->next->prve = newnode; 70. phead->next = newnode; 71. } 72. void LTPopFront(LTNode* phead) 73. { 74. assert(phead && phead->next != phead); 75. LTNode* del = phead->next; 76. phead->next = del->prve; 77. del->next->prve = phead; 78. free(del); 79. del = NULL; 80. } 81. void LTInsert(LTNode* pos, LTDataType x) 82. { 83. assert(pos); 84. LTNode* newnode = LTBuyNode(x); 85. newnode->next = pos->next; 86. newnode->prve = pos; 87. pos->next->prve = newnode; 88. pos->next = newnode; 89. } 90. void LTErase(LTNode* pos) 91. { 92. assert(pos); 93. pos->next->prve = pos->prve; 94. pos->prve->next = pos->next; 95. free(pos); 96. pos = NULL; 97. } 98. LTNode* LTFind(LTNode* phead, LTDataType x) 99. { 100. assert(phead); 101. LTNode* p = phead->next; 102. while (p != phead) 103. { 104. if (p->date == x) 105. { 106. return p; 107. } 108. p = p->next; 109. } 110. return NULL; 111. }
5.2.2 list.h
1. #pragma once 2. #include<stdio.h> 3. #include<stdlib.h> 4. #include<assert.h> 5. typedef int LTDataType; 6. typedef struct ListNode 7. { 8. struct ListNode* next; 9. struct ListNode* prve; 10. LTDataType date; 11. }LTNode; 12. 13. LTNode* LTInit(LTDataType x);//初始化 14. void LTDestroy(LTNode* phead);//销毁 15. void LTPrint(LTNode* phead);//打印 16. 17. void LTPushBack(LTNode* phead, LTDataType x);//尾插 18. void LTPopBack(LTNode* phead);//尾删 19. 20. void LTPushFront(LTNode* phead, LTDataType x);//头插 21. void LTPopFront(LTNode* phead);//头删 22. 23. void LTInsert(LTNode* pos, LTDataType x);//在pos位置之后插入数据 24. void LTErase(LTNode* pos);//删除pos位置数据 25. LTNode* LTFind(LTNode* phead, LTDataType x);//查找数据
完！
