单链表与双链表实现-阿里云开发者社区

一、链表概念

链表是什么？链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

简单理解一下便是：链表可以近似的看作成火车，用节点一个一个串起来，需要操作时运用节点进行操作。

其特点如下：

链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（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);//查找数据

完！

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

单链表与双链表实现