数据结构动图单向链表

目录

1.什么是链表

        1.问题引入

        2. 链表的概念及结构

        3. 问题解决

2.单向链表接口的实现

        1.接口1，2---头插，尾插

        2. 接口3，4---头删，尾删

        3. 接口5---查找

         4. 接口6，7---插入，删除

        5. 接口8---打印

         6. 注意事项总结

3.完整代码及效果展示 

---

1.什么是链表

        1.问题引入

        上期我们讲解了顺序表的基本概念和实现方法（传送门：详解顺序表）。但是顺序表存在着如下三个问题：

1. 顺序表中间及头部的插入与删除，需要对原有数据进行移动，时间复杂度为O(N),成本较高
2. 使用realloc进行增容时需要申请新空间，释放旧空间，拷贝数据，消耗较高。
3. 由于我们无法知道用户实际需要多少空间，在增容时往往可能会有大量的空间剩余。例如在容量为100时满了进行2倍增容到200，如果后续只需插入5个数据，则会浪费95个数据空间；而如果我们每次只扩大1个数据空间，当需要插入95个数据时，就需要进行realloc操作95次，成本较高。

        那么这些问题要如何解决呢？通过链表， 我们就可以很轻松的解决以上问题。下面，就让我们感受链表的魅力吧！

        2. 链表的概念及结构

        链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它的结构如下所示(以单向链表为例)：

        我们把date和next形成的结构体称为链表的一个结点，我们可以看到，链表就是由一个个结点链接起来的非连续线性结构，不同结点通过next指针连接的，最后一个结点的next指针指向空。链表也是线性表中的一种。

当然，在实际应用中，链表的结构多种多样，通过以下几种情况组合而成的就有8种链表结构：

1. 单 向 、 双 向

2. 带 头结点 、 不 带 头结点

3. 循 环 、 非 循 环

---

本期我们讲解的是实际应用中最常用的两种结构之一：单向不带头非循环链表。（另外一种是带头双向循环链表）

        3. 问题解决

        通过以上链表结构，我们就能很好地解决顺序表的局限：

1. 每当我们需要新增数据时，我们只需申请一个新结点用来保存数据，然后用指针将链表与新结点链接起来即可，并不需要进行数据拷贝。
2. 由于使用链表存储数据总是处于满载状态，每个结点都是有效数据，需要插入时则申请新结点并与链表连接，因此就不存在空间浪费的问题。
3. 链表的结构是线性非连续的，各结点通过指针连接。如果需要在头部或中间插入数据，只需改变结点指针的指向即可，无需再移动数据。

2.单向链表接口的实现

        首先，在实现各种接口函数前，我们需要定义一个结构体来代表每一个结点，用date保存结点中的数据，用next保存下一结点的地址。同样的，我们采取typedef的方式将类型重命名方便代码的编写与维护。如下：

由于我们实现的单向链表是不带头结点的，所以我们还需要定义一个指针指向链表的第一个结点(下面称为头指针)。

        1.接口1，2---头插，尾插

        对于头插，我们只需要创建新结点保存数据，然后将头指针指向新结点，新结点指向原来头指针指向的结点即可，动态效果如下：

        具体代码如下：

1.  
   //用于创建新结点
2.  
   SLNode* CreateNode(SLDateType x)
3.  
   {
4.  
   SLNode* cur = (SLNode*)malloc(sizeof(SLNode));
5.  
   cur->date = x;
6.  
   cur->next = NULL;
7.  
   return cur;
8.  
   }
9.  
    
10.  
    //头插
11.  
    void SListPushFront(SLNode** pphead, SLDateType x)
12.  
    {
13.  
    SLNode* NewNode = CreateNode(x); //获取新结点
14.  
    NewNode->next = *pphead;
15.  
    *pphead = NewNode; //修改头指针
16.  
    }

值得注意的是，函数中我们传入的是头指针的地址。这是由于我们需要修改头指针使其指向新的结点，因此需要采用址传递的方式，用二级指针接收，否则只会修改临时变量造成出错。

---

         对于尾插，我们需要先找到链表的尾结点，然后将尾结点的next指向新结点，动态效果如下：

        代码如下： 

1.  
   //尾插，初稿
2.  
   void SListPushBack(SLNode** pphead, SLDateType x)
3.  
   {
4.  
   SLNode* NewNode = CreateNode(x);
5.  
   SLNode* tail = *pphead;
6.  
   while (tail->next != NULL) //不为尾结点
7.  
   {
8.  
   tail = tail->next; //tail指向下一结点
9.  
   }
10.  
     
11.  
    //找到尾结点
12.  
    tail->next = NewNode;
13.  
    }

        但是，上述代码是存在问题的。我们知道->相当于是一种解引用，当链表为空时，即tail==NULL时，此时我们进行tail->next操作显然是非法的，所以我们还需对链表为空的情况做出讨论，最终代码如下：

1.  
   //尾插，终稿
2.  
   void SListPushBack(SLNode** pphead, SLDateType x)
3.  
   {
4.  
   SLNode* NewNode = CreateNode(x);
5.  
   if (*pphead == NULL)
6.  
   {
7.  
   *pphead = NewNode; //为空就直接修改头指针指向新结点，因此需要传二级指针
8.  
   }
9.  
   else
10.  
    {
11.  
    SLNode* tail = *pphead;
12.  
    while (tail->next != NULL) //不为尾结点
13.  
    {
14.  
    tail = tail->next; //指向下一结点
15.  
    }
16.  
     
17.  
    //找到尾结点
18.  
    tail->next = NewNode;
19.  
    }
20.  
    }

        2. 接口3，4---头删，尾删

        对于头删，我们只需要将头指针指向下一个位置，然后将原来指向的空间free()掉即可。如果链表为空，我们就让函数直接返回，具体动态效果如下：

        在代码实现中，我们需要先创建一个临时变量next来保存下一个结点的地址，这是因为free()后就无法通过->得到下一个结点的地址了。具体代码如下：

1.  
   //头删
2.  
   void SListPopFront(SLNode** pphead)
3.  
   {
4.  
   if (*pphead == NULL)
5.  
   {
6.  
   return; //链表为空直接返回
7.  
   }
8.  
   else
9.  
   {
10.  
    SLNode* next = (*pphead)->next; //存储下一个结点地址
11.  
    free(*pphead);
12.  
    *pphead = next; //改变头指针指向，因此需要传二级指针
13.  
    }
14.  
    }

---

        对于尾删，我们同样需要找到尾结点。这里和尾插不同的是，我们除了要找到尾结点，还需找到尾结点的前一个结点并使其next置为空，因此我们可以使用两个指针prev和tail进行移动，prev指向tail的上一个结点，具体动图如下：

        具体代码如下：

1.  
   //尾删，初稿
2.  
   void SListPopBack(SLNode** pphead)
3.  
   {
4.  
   if (*pphead == NULL) //没有结点
5.  
   {
6.  
   return;
7.  
   }
8.  
   else //一个以上结点
9.  
   {
10.  
    SLNode* tail = *pphead;
11.  
    SLNode* prev = NULL;
12.  
    while (tail->next != NULL) //tail不为尾结点
13.  
    {
14.  
    prev = tail;
15.  
    tail = tail->next; //tail指向下一结点
16.  
    }
17.  
     
18.  
    //tail为尾结点，此时prev为尾结点的前一个结点
19.  
    free(tail); //释放掉尾结点
20.  
    tail=NULL;
21.  
    prev->next = NULL;
22.  
    }
23.  
    }

        这里和头删一样，当链表为空时直接让函数返回。但是以上代码依旧存在着一个问题，就是当链表只有一个结点时，tail直接指向尾结点，此时prev为NULL，禁止对其进行->操作。所以我们还需要对只有一个结点的情况进行讨论，最终代码如下：

1.  
   //尾删，终稿
2.  
   void SListPopBack(SLNode** pphead)
3.  
   {
4.  
   if (*pphead == NULL) //没有结点
5.  
   {
6.  
   return;
7.  
   }
8.  
   else if ((*pphead)->next == NULL) //只有一个结点
9.  
   {
10.  
    free(*pphead);
11.  
    *pphead = NULL; //直接将结点释放掉，头指针改为NULL，因此需要传二级指针
12.  
    }
13.  
    else //一个以上结点
14.  
    {
15.  
    SLNode* tail = *pphead;
16.  
    SLNode* prev = NULL;
17.  
    while (tail->next != NULL) //tail不为尾结点
18.  
    {
19.  
    prev = tail;
20.  
    tail = tail->next; //tail指向下一结点
21.  
    }
22.  
     
23.  
    //tail为尾结点，此时prev为尾结点的前一个结点
24.  
    free(tail); //释放掉尾结点
25.  
    tail=NULL;
26.  
    prev->next = NULL;
27.  
    }
28.  
    }

        3. 接口5---查找

        对于查找，我们只需遍历链表的所有结点即可，故不需要头指针，只需传一级指针即可。当找到需要查找的date时，返回对应结点的指针，若没找到或者链表为空时，返回NULL，代码如下：

1.  
   //查找
2.  
   SLNode* SListFind(SLNode* phead, SLDateType x)
3.  
   {
4.  
   while (phead)
5.  
   {
6.  
   if (phead->date == x)
7.  
   {
8.  
   return phead; //找到了，返回结点指针
9.  
   }
10.  
    phead = phead->next; //向后查找
11.  
    }
12.  
     
13.  
    //没有找到，返回空指针
14.  
    return NULL;
15.  
    }

         4. 接口6，7---插入，删除

        对于插入，我们可以实现一个在指定结点前插入一个新结点的接口，而这个指定结点我们可以通过查找接口来获取。相同的，在进行插入操作时我们还需要得到前一个结点的地址，我们用prev来存储，然后将prev->next改为新结点地址，新结点的next为我们传入的结点的地址。动态效果如下：

1.  
   //插入，初稿
2.  
   void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
3.  
   {
4.  
   if (pos == NULL) //指定结点为空直接返回
5.  
   {
6.  
   return;
7.  
   }
8.  
   SLNode* NewNode = CreateNode(x); //获取新结点
9.  
   SLNode* prev = *pphead;
10.  
    while (prev->next != pos) //prev不指向pos上一结点
11.  
    {
12.  
    prev = prev->next; //prev指向下一结点
13.  
    }
14.  
     
15.  
    //当prev指向pos上一结点，插入新结点
16.  
    prev->next = NewNode;
17.  
    NewNode->next = pos;
18.  
    }

         (嘿嘿，我又来了qwq)，上述的代码其实还是存在bug的，就是当我们传入的指定结点为头结点时，prev->next永远不可能等于pos，prev不断向后更新，最终为NULL导致程序崩溃。动态分析如下：

         因此我们需要进行分类讨论，而我们发现如果pos指向头结点，那在其前面插入不就相当于头插吗？所以我们可以直接调用头插接口，改进后的代码如下：

1.  
   //插入，终稿
2.  
   void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
3.  
   {
4.  
   if (pos == NULL) //指定结点为空直接返回
5.  
   {
6.  
   return;
7.  
   }
8.  
   if (*pphead==pos) //pos为头结点指针，直接头插
9.  
   {
10.  
    SListPushFront(pphead,x);
11.  
    }
12.  
    else
13.  
    {
14.  
    SLNode* NewNode = CreateNode(x); //获取新结点
15.  
    SLNode* prev = *pphead;
16.  
    while (prev->next != pos) //prev不指向pos上一结点
17.  
    {
18.  
    prev = prev->next; //prev指向下一结点
19.  
    }
20.  
     
21.  
    //当prev指向pos上一结点，插入新结点
22.  
    prev->next = NewNode;
23.  
    NewNode->next = pos;
24.  
    }
25.  
    }

---

        对于删除，我们同样可以实现一个删除指定结点的接口，而这个指定结点我们依旧可以通过查找接口来获取。同样，除了将指定的结点free()掉，还需将其上一个结点的next指向pos的下一结点。与插入一样都需要找到上一个结点的位置，在这过程中可能引发的问题也是一样的，这里就不再赘述了，直接上代码：

1.  
   //删除
2.  
   void SListErase(SLNode** pphead, SLNode* pos)
3.  
   {
4.  
   if (pos == NULL) //指定结点为空直接返回
5.  
   {
6.  
   return;
7.  
   }
8.  
   if (*pphead == pos) //pos为头结点指针，直接头删
9.  
   {
10.  
    SListPopFront(pphead);
11.  
    }
12.  
    else
13.  
    {
14.  
    SLNode* prev = *pphead;
15.  
    while (prev->next != pos) //prev不指向pos上一结点
16.  
    {
17.  
    prev = prev->next; //使prev指向下一个结点
18.  
    }
19.  
     
20.  
    //当prev指向pos上一结点，删除pos指向结点，更新prev->next
21.  
    prev->next = pos->next;
22.  
    free(pos);
23.  
    }
24.  
    }

        5. 接口8---打印

        对于打印，只需从头结点开始，向后遍历链表，打印每个结点的date直到走到链表尾即可，此时指针指向NULL。由于不修改头指针指向，因此采用值传递即可，用一级指针接收。代码如下：

1.  
   //打印
2.  
   void SListPrint(SLNode* phead)
3.  
   {
4.  
   while (phead != NULL) //遍历链表直到链表尾
5.  
   {
6.  
   printf("%d->", phead->date);
7.  
   phead = phead->next;
8.  
   }
9.  
    
10.  
    //到达链表尾，打印NULL
11.  
    printf("NULL");
12.  
    }

         6. 注意事项总结

通过上面一个个接口的实现，我们得出以下两个值得注意的地方：

1. 当我们需要修改头指针时，如插入删除操作时，需要使用址传递，用二级指针来接收头指针的地址。而如果我们不需要修改头指针时，如打印，查找等，建议使用值传递，用一级指针来接收，避免头指针被意外修改。
2. 在实现链表接口时，需要时刻考虑到当链表为空，链表只有一个结点，对头结点进行操作，对尾结点进行操作等特殊情况是否会出现bug。

3.完整代码及效果展示 

        我们可以采用多文件编写的形式，将上述接口的定义实现放在SList.c文件中，然后将接口的声明和结构体的定义放于SList.h头文件中，以达到封装的效果。这样我们如果需要使用单向链表，就只需要在文件中包含对应的头文件SList.h就可以使用我们上面定义的各种接口。以下为本文实现的单向链表完整代码以及效果展示：

1.  
   //SList.h文件，用于声明接口函数，定义结构体
2.  
   #pragma once
3.  
   #include<stdio.h>
4.  
   #include<stdlib.h>
5.  
   typedef int SLDateType;
6.  
   struct SListNode
7.  
   {
8.  
   SLDateType date;
9.  
   struct SListNode* next;
10.  
    };
11.  
    typedef struct SListNode SLNode;
12.  
     
13.  
     
14.  
    // 不会改变链表的头指针，传一级指针
15.  
    void SListPrint(SLNode* phead);
16.  
    SLNode* SListFind(SLNode* phead, SLDateType x);
17.  
     
18.  
    // 可能会改变链表的头指针，传二级指针
19.  
    void SListPushBack(SLNode** pphead, SLDateType x);
20.  
    void SListPushFront(SLNode** pphead, SLDateType x);
21.  
    void SListPopFront(SLNode** pphead);
22.  
    void SListPopBack(SLNode** pphead);
23.  
    // 在pos的前面插入x
24.  
    void SListInsert(SLNode** phead, SLNode* pos, SLDateType x);
25.  
    // 删除pos位置的值
26.  
    void SListErase(SLNode** phead, SLNode* pos);

1.  
   //SList.c文件，用于定义接口函数
2.  
   #define _CRT_SECURE_NO_WARNINGS 1
3.  
   #include "SList.h"
4.  
   void SListPrint(SLNode* phead)
5.  
   {
6.  
   while (phead != NULL)
7.  
   {
8.  
   printf("%d->", phead->date);
9.  
   phead = phead->next;
10.  
    }
11.  
    printf("NULL");
12.  
    }
13.  
    SLNode* CreateNode(SLDateType x)
14.  
    {
15.  
    SLNode* cur = (SLNode*)malloc(sizeof(SLNode));
16.  
    cur->date = x;
17.  
    cur->next = NULL;
18.  
    return cur;
19.  
    }
20.  
     
21.  
    void SListPushBack(SLNode** pphead, SLDateType x)
22.  
    {
23.  
    SLNode* NewNode = CreateNode(x);
24.  
    if (*pphead == NULL)
25.  
    {
26.  
    *pphead = NewNode; //为空就直接修改头指针指向新结点，因此需要传二级指针
27.  
    }
28.  
    else
29.  
    {
30.  
    SLNode* tail = *pphead;
31.  
    while (tail->next != NULL) //不为尾结点
32.  
    {
33.  
    tail = tail->next; //指向下一结点
34.  
    }
35.  
    //找到尾结点
36.  
    tail->next = NewNode;
37.  
    }
38.  
    }
39.  
     
40.  
    void SListPushFront(SLNode** pphead, SLDateType x)
41.  
    {
42.  
    SLNode* NewNode = CreateNode(x); //获取新结点
43.  
    NewNode->next = *pphead;
44.  
    *pphead = NewNode; //修改头指针
45.  
    }
46.  
     
47.  
    void SListPopFront(SLNode** pphead)
48.  
    {
49.  
    if (*pphead == NULL)
50.  
    {
51.  
    return; //链表为空直接返回
52.  
    }
53.  
    else
54.  
    {
55.  
    SLNode* next = (*pphead)->next; //存储下一个结点地址
56.  
    free(*pphead);
57.  
    *pphead = next; //改变头指针指向，因此需要传二级指针
58.  
    }
59.  
    }
60.  
     
61.  
    void SListPopBack(SLNode** pphead)
62.  
    {
63.  
    if (*pphead == NULL) //没有结点
64.  
    {
65.  
    return;
66.  
    }
67.  
    else if ((*pphead)->next == NULL) //只有一个结点
68.  
    {
69.  
    free(*pphead);
70.  
    *pphead = NULL; //直接将结点释放掉，头指针改为NULL，因此需要传二级指针
71.  
    }
72.  
    else //一个以上结点
73.  
    {
74.  
    SLNode* tail = *pphead;
75.  
    SLNode* prev = NULL;
76.  
    while (tail->next != NULL) //tail不为尾结点
77.  
    {
78.  
    prev = tail;
79.  
    tail = tail->next; //tail指向下一结点
80.  
    }
81.  
    //tail为尾结点，此时prev为尾结点的前一个结点
82.  
    free(tail); //释放掉尾结点
83.  
    tail = NULL;
84.  
    prev->next = NULL;
85.  
    }
86.  
    }
87.  
     
88.  
    SLNode* SListFind(SLNode* phead, SLDateType x)
89.  
    {
90.  
    while (phead)
91.  
    {
92.  
    if (phead->date == x)
93.  
    {
94.  
    return phead; //找到了，返回结点指针
95.  
    }
96.  
    phead = phead->next; //向后查找
97.  
    }
98.  
    //没有找到，返回空指针
99.  
    return NULL;
100.  
     }
101.  
      
102.  
     void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
103.  
     {
104.  
     if (pos == NULL) //指定结点为空直接返回
105.  
     {
106.  
     return;
107.  
     }
108.  
     if (*pphead == pos) //pos为头结点指针，直接头插
109.  
     {
110.  
     SListPushFront(pphead, x);
111.  
     }
112.  
     else
113.  
     {
114.  
     SLNode* NewNode = CreateNode(x); //获取新结点
115.  
     SLNode* prev = *pphead;
116.  
     while (prev->next != pos) //prev不指向pos上一结点
117.  
     {
118.  
     prev = prev->next; //prev指向下一结点
119.  
     }
120.  
     //prev指向pos上一结点，插入新结点
121.  
     prev->next = NewNode;
122.  
     NewNode->next = pos;
123.  
     }
124.  
     }
125.  
      
126.  
      
127.  
      
128.  
     void SListErase(SLNode** pphead, SLNode* pos)
129.  
     {
130.  
     if (pos == NULL) //指定结点为空直接返回
131.  
     {
132.  
     return;
133.  
     }
134.  
     if (*pphead == pos)
135.  
     {
136.  
     SListPopFront(pphead);
137.  
     }
138.  
     else
139.  
     {
140.  
     SLNode* prev = *pphead;
141.  
     while (prev->next != pos)
142.  
     {
143.  
     prev = prev->next;
144.  
     }
145.  
     prev->next = pos->next;
146.  
     free(pos);
147.  
     }
148.  
     }
149.  
      

       最后， 我们在text.c文件调用单向链表各个接口进行测试，如下：

1.  
   //text.c文件，用于测试
2.  
   #define _CRT_SECURE_NO_WARNINGS 1
3.  
   #include "SList.h"
4.  
   void SListText()
5.  
   {
6.  
   SLNode* phead = NULL;
7.  
   printf("起始数据: \n");
8.  
   SListPrint(phead);
9.  
   //头插
10.  
    SListPushFront(&phead, 1);
11.  
    SListPushFront(&phead, 2);
12.  
    SListPushFront(&phead, 3);
13.  
    printf("\n头插入数据后: \n");
14.  
    SListPrint(phead);
15.  
    //尾插
16.  
    SListPushBack(&phead, 4);
17.  
    SListPushBack(&phead, 5);
18.  
    SListPushBack(&phead, 6);
19.  
    printf("\n尾插入数据后: \n");
20.  
    SListPrint(phead);
21.  
    //头删
22.  
    SListPopFront(&phead);
23.  
    printf("\n头删数据后: \n");
24.  
    SListPrint(phead);
25.  
    //尾删
26.  
    SListPopBack(&phead);
27.  
    printf("\n尾删数据后: \n");
28.  
    SListPrint(phead);
29.  
    //找出数据为5的结点并在其前面插入8
30.  
    SLNode* cur1 = SListFind(phead, 5);
31.  
    if (cur1)
32.  
    {
33.  
    SListInsert(&phead, cur1, 8);
34.  
    }
35.  
    printf("\n5前面插入数据后: \n");
36.  
    SListPrint(phead);
37.  
    //删除数据为1的结点
38.  
    SLNode* cur2 = SListFind(phead, 1);
39.  
    if (cur2)
40.  
    {
41.  
    SListErase(&phead, cur2);
42.  
    }
43.  
    printf("\n删除数据1的结点后: \n");
44.  
    SListPrint(phead);
45.  
    }
46.  
    int main()
47.  
    {
48.  
    SListText();
49.  
    return 0;
50.  
    }

        以下就是测试的最终效果：

---

 以上，就是本期的全部内容。

制作不易，能否点个赞再走呢qwq

这篇好文章是转载于：学新通技术网