冰冰学习笔记：一步一步带你实现《单链表》

欢迎各位大佬光临本文章！！！

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool

系列文章推荐

冰冰学习笔记：一步一步带你实现《顺序表》

冰冰学习笔记：一步一步带你实现《通讯录》

前言

前面的文章我们学习了一种数据结构，线性表。线性表是物理空间连续的存储数据的结构，但是顺序表存储数据是每次扩容都需要开辟额外的空间，这就存在一个问题，开辟的空间太多造成浪费，开辟的空间太小频繁扩容消耗时间；头插，任意位置插入需要移动数据不方便，那有没有存一个数据我就开辟一个空间的数据结构呢？我也不用要求它一定连续存放，哪里有空间就放在哪里，只要我能找到就行。答案是肯定的，就是接下来我们要学习的链表。

一、什么是链表

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

也就是说，链表在逻辑上是连续的，但是物理空间上不一定连续。因为链表中的每个结点都是从堆栈上开辟出来的，每个都是独立的空间，不一定是连续开辟的。

链表有很多结构，单向或者双向，带头或者不带头，循环或者非循环，各种情况组合起来共有8种链表结构，当然常用的还是两种。

（1）无头单向非循环链表：

结构简单，一般不会单独用来存储数据，实际上作为学习其他数据结构的子结构。

（2）带头双向循环链表：

结构最复杂，一般用于单独的数据存储。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

下面我们介绍的就是简单的单链表结构，为以后的数据结构学习做铺垫。

二、单链表的实现

单链表的实现和顺序表既有相同之处也有不同之分，相同之处还是那些数据存储的基本功能，增删查改。但是我们要特别注意，单链表的连接和数据访问基本都是依靠指针进行，因此我们对指针的学习要掌握的牢固，学习起来才能得心应手。

单链表的结构如下：

我们可以通过每个结点中存储的指针来找到下一个数据的存储位置。

与顺序表的实现方式类似，我们将文件分为三个进行实现，SList.h、SList.c、test.c.

2.1结构创建与单链表的使用

2.1.1单链表的结构创建

通过图片分析我们知道，每个结点犹如一节一节的火车车厢，由一个开头的数据指引，并且一节一节的连接起来，那么我们创建的单链表结点就需要由两部分组成。一部分为数据的存储，另一部分为指向下一个结点的地址。

在这里我们创建的结构体使用了结构体的自引用，每个SLTNode类型的结构体中还包含一个指向SLTNode类型结构体的指针next。最后一个结点的next指向为NULL。

2.2.2单链表的使用

现在我们创建了单链表的每个结点，怎么使用呢？例如我要将数据1，2，3，4 存储到单链表的节点中。

既然要创建结点来存储，那么我们就需要用malloc开辟空间存储，使用malloc开辟空间后，对STLNode*类型的指针增加断言操作，避免空间开辟失败还进行存储。

所以我们开辟了下面的结点来存储数据

结点开辟完毕，现在开始存放数据，将数据1，2，3，4放进去，就是将n1到n2中date赋值为1到4，然后需要将每个指针连接起来。

我们可以看到每个结点的地址均不是连续的。但是我们将结点中的next赋值为下一个结点的地址，这些结点彼此之间就联系在一起了。

2.2单链表的打印函数

单链表的打印函数和以往写的打印函数都不相同。以前我们写的打印函数都是用变量 i 来控制循环，通过下标访问操作符来访问 i 处对应的元素，但是单链表中元素并不是连续存放的，就没法使用单一的变量来控制。

但是每个结点是通过指针相互连接在一起的，所以我们可以通过指针来寻找每个结点，并且将其保存的date打印出来。

什么时候停止呢？我们知道，每一个单链表的最后一个结点的next都指向空指针，当我们遇到空指针的时候就意味着结点走到了最后，这是最后一个保存的元素，打印后就该截止。

所以代码如下：

void SLTPrint(const SLTNode* const plist)
{
    SLTNode* cur = plist;
    while ( cur != NULL )
    {
        printf("%d->", cur->date);
        cur = cur->next;
    }
    printf("NULL\n");
}

cur保存传过来的单链表开头的数据，通过不断的访问结点中的next来找寻下一个结点，并打印数据。

结果如下：

2.3数据的尾部增加和删除

和顺序表一样，我们不能添加一次数据就自己创建一个结点，我们应该写一个函数，能够让我们自由的从尾部增加数据，并将其自动连接到已有的数据后面。当我们想删除保存的数据时还可以从尾部删除，这就需要尾插和尾删的实现。

2.3.1增加结点函数

既然要增加结点，就不可避免的需要用malloc开辟空间。无论是尾插还是头插，都需要开辟新结点，为了方便书写和代码整洁，我们将其封装成一个函数，需要时调用即可，开辟成功后返回SLTNode*类型的数据存储空间。

该函数只需要将需要保存的新数据传递过来，然后开辟一个新的结点，将其保存进去，将结点中的next置为空，具体的连接交给其他函数实现。

函数代码如下：

SLTNode* BuySLTNode(SLTDateType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    assert(newnode);
    newnode->date = x;
    newnode->next = NULL;
    return newnode;
}

2.3.2数据尾插函数

尾增就是将数据连接到已有的链表后面，让原本指向空指针的最后一个结点指向新开辟的结点。

我们需要考虑两种情况：

（1）原有的链表plist存有数据，将新插入的数据newnode连接在后面。

（2）原有的链表没有数据，plist是一个空指针，需要将新开辟的结点视为第一个数据插入，所以需要将plist原本指向的空改为指向newnode。

第一种情况比较好实现，我们只需要找到原链表的最后一个结点即可，最后一个结点的next必定指向NULL，将其作为判定条件，tail开始指向plist，判断tail->next是否为空；不为空，tail赋值为当前结点的next，直到找到tail->next为空停下来。停下来之后让tail->next=newnode。

newnode的next不用再次赋值给NULL，因为在开辟newnode的时候已经将其改为NULL了。

当原有链表plist为空的时候，我们就得小心了。

有人会说，那有啥注意的，不就是加个判断语句吗？

那我们运行一下

什么情况，怎么只有一个NULL，我明明插入了 1。

调试看看

这就奇怪了，难不成还是形参和实参的问题？

但是我传过去的就是指针呀！

没错，这还是传值调用，传过去的plist只是调用处的一份临时拷贝，并不是想要改变的plist的本身。不对呀，我传的是地址呀？是地址没错，但是我们将指向NULL的plist更改，plist本身就是指针；就好比以前我们传递的参数是int类型的变量a，如果采用int类型的变量传递，我们无法改变a本身，所以我们需要传递a的地址，就需要用int类型的指针来接收，然后才能改变int类型的a。此时我们要改变的是SLTNode类型的plist本身，就需要传递plist的地址，也就是指针的地址，那就是二级指针，因此我们接收得用SLTNode**类型的二级指针接收。

有了以上的分析，那我们的代码就可以实现为下面这样：

void SLTPushBack(SLTNode** pplist, SLTDateType x)
{
    assert(pplist);
    SLTNode* newnode=BuySLTNode(x);//创建新结点
    SLTNode* tail = *pplist;
    //空链表情况
    if ( *pplist == NULL )
    {
        *pplist = newnode;
    }
    else//链表不为空
    {
        while ( tail->next != NULL )
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

此时我们进行尾插就不会存在问题了。

2.3.3数据尾删函数

尾删就是将链表中存储最后一个数据的结点释放掉，需要注意的是，我们需要将前一个结点的next更新为NULL，要不然就会出现空指针的问题。

尾删要分为三种情况：

（1）链表为空，一个结点也没有，此时应该报错，没有元素怎么删除，直接用assert报错。

（2）链表只有一个元素，释放后链表为空，那plist就应该更改为指向NULL，需要更改plist本身，因此我们需要使用二级指针。

（3）链表有多个元素，找到最后一个元素所在的结点，该结点的next指向NULL，释放掉该结点的内存，将前一个结点的next指向NULL。

前两个比较好解决，关键是在有多个元素的时候如何找到最后结点的前一个结点呢？

其实我们只需要创建两个临时变量就好了，一个用来找需要释放的结点，一个寻找前一个结点。

有了以上的分析，我们的代码如下：

void SLTPopBack(SLTNode** pplist)
{
    assert(pplist&&*pplist);//*pplist==NULL表明为空链表，不需要删除
    //只有一个元素
    if ( (*pplist)->next == NULL )
    {
        free(*pplist);
        *pplist = NULL;
    }
    else//多个元素
    {
        SLTNode* tail = *pplist;
        SLTNode* pretail = NULL;
        while ( tail->next != NULL )
        {
            pretail = tail;
            tail = tail->next;
        }
        free(tail);
        pretail->next = NULL;
    }
}

当然我们还有一种写法，原理和上面双指针的一样，只不过没有创建pretail。

2.4数据的头部增加和删除

只有尾增尾删远远达不到我们想要的目的，和顺序表一样，我们也需要头增头删。

2.4.1数据头增函数

数据的头增函数相比于尾增函数来说，实现方式比较简单。我们只需要创建新的结点将其放入即可，无论原链表是否存有结点，我们只需要将newnode的next指向原链表的plist，plist在重新指向newnode即可。

实现代码：

void SLTPushFront(SLTNode**pplist,SLTDateType x)
{
    assert(pplist);
    SLTNode* newnode = BuySLTNode(x);//创建新结点
    newnode->next = *pplist;
    *pplist = newnode;
}

2.4.2数据头删函数

数据的头删函数相对来说也比较简单， 和尾删一样，需要检查链表是否为空链表，空链表的情况下不需要删除。

需要注意的是，我们需要先将plist指向plist的结点中next的地址保存到临时变量tmp中，然后才能将其释放掉，再将tmp中存放的地址赋值给plist。

代码：

void SLTPopFront(SLTNode** pplist)
{
    assert(pplist&&*pplist);//*pplist==NULL表明为空链表，不需要删除
    SLTNode* tmp = (*pplist)->next;
    free(*pplist);
    *pplist = tmp;
}

2.5查找和更改

链表中的元素也需要查找和修改，查找函数还是和顺序表中类似的实现逻辑，找到了返回结点地址，找不到返回NULL指针。指针遍历方式与打印函数相同。

SLTNode* SLTFind(const SLTNode* const plist, SLTDateType x)
{
    SLTNode* cur = plist;
    while ( cur!= NULL )
    {
        if ( cur->date == x )
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

修改函数不需要特定的编写，我们通过查找可以得到需要修改元素的存储位置的指针，直接通过指针就可以修改数据。

2.6任意位置之前 / 之后的插入

任意位置的插入分为两种，在提供的位置pos的前面插入一个结点，或者在pos之后插入一个结点。两种插入方式看似差不多，实则不然，两种方式的实现方式以及效率都截然不同。

2.6.1任意位置之前插入函数

既然要将一个数据放到pos的前面，那我们就得从头遍历，找到pos的位置，然后将newnode的next指向pos，将原本pos之前的结点的next变更为newnode。

还有一种情况，那就是pos指向的位置就是链表开头，此时实际上就是头插，我们只需要调用即可。当pos传过来是NULL但是plist不为NULL时，此时视为在最后进行数据插入。

最终我们实现的代码如下所示：

void SLTInsertBefor(SLTNode** pplist, SLTNode* pos, SLTDateType x)
{
    assert(pplist);
    SLTNode* newnode = BuySLTNode(x);//创建新结点
    if ( pos == *pplist )//头插
    {
        SLTPushFront(pplist, x);
    }
    else
    {
        SLTNode* cur = *pplist;
        while ( cur->next != pos )
        {
            cur = cur->next;
        }
        SLTNode* tmp = cur->next;
        cur->next = newnode;
        newnode->next = tmp;
    }
}

2.6.2任意位置之后插入函数

任意位置之后的插入函数比起任意位置之前插入的函数来说简直容易多了，而且不需要进行遍历，也不需要更改原链表的指针plist。

如果原链表指针为NULL，我们进行报错，原链表一个元素都没有怎么在元素之后进行插入呢？

至于其他情况，我们只需要将newnode->next改为pos->next，再将pos->next改为newnode。

我们发现整个过程不需要改变plist的指向，也不需要遍历链表。即便是在最后一个结点后面增加，也毫无影响，只不过是pos->next为NULL，插入后newnode->next指向NULL ，pos->next指向newnode。所以我们函数的参数只需要pos和数据x即可，不需要接收plist地址的二级指针。

我们会清楚的发现，任意位置之后的代码时间复杂度相比于任意位置之前的代码简化的太多，任意位置之前的删除时间复杂度为O(N)，任意位置之后的删除时间复杂度为O(1)。

代码：

void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);//创建新结点
    newnode->next = pos->next;
    pos->next = newnode;
}

2.7任意位置的删除和任意位置之后的删除

有了任意位置的插入我们还需要任意位置的删除，但有些人肯定会疑惑，我都可以任意位置的删除了，干嘛要写个任意位置之后的删除函数呢？我们通过两个函数的对比来回答这个问题。

2.7.1任意位置的删除

任意位置的删除，分为四种情况：

（1）pos==plist，即删除plist指向的链表的第一个元素，实际上就是头删，调用头删即可。

（2）plist==NULL，链表没有元素，不需要删除，直接报错。

（3）pos==NULL，删除NULL指向的结点？不存在，报错。

（4）pos为正常值，将pos指向的next保存到tmp，然后释放掉pos结点，最后将pos之前的结点的next赋值为tmp。

代码如下：

void SLTErase(SLTNode** pplist, SLTNode* pos)
{
    assert(pplist&&*pplist&&pos); //*pplist == NULL表明为空链表，不需要删除
                                  //pos==NULL无法删除指定节点
    SLTNode* cur = *pplist;
    if ( cur == pos )//删除第一个-->头删
    {
        SLTPopFront(pplist);
    }
    else//多结点情况
    {
        while ( cur->next != pos )
        {
            cur = cur->next;
        }
        SLTNode* tmp = cur->next->next;
        free(cur->next);
        cur->next = tmp;
    }
}

2.7.2任意位置之后的删除

任意位置之后的删除和任意位置之后的插入极其相似，我们不需要二级指针pplist来更改plist，也不需要遍历链表找删除的元素，我们只需要保证pos不为NULL以及pos后面有元素可以删除即可。

实现代码：

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos&&pos->next);//pos为NULL或者pos后面没有元素可删除，报错
    SLTNode* tmp = pos->next->next;
    free(pos->next);
    pos->next = tmp;
}

我们发现任意位置之后的删除的时间复杂度依然为O(1)任意位置的删除则为O(N)。所以通常使用任意位置之后的插入和删除。

三、主逻辑函数框架和测试结果

主逻辑函数就是为了调用各功能所搭建的主体框架，该框架的搭建仅凭个人喜好进行搭建，下面展示的是博主自己搭建的主逻辑代码的运行视频，具体链表代码已上传gitee仓库，如有需要可以自行下载。

单链表运行视频：运行视频

代码仓库地址：单链表实现代码

获取数据函数与数据更改函数：

SLTDateType Get()
{
    printf("请输入你要插入的数字：\n");
    SLTDateType x = 0;
    scanf("%d", &x);
    return x;
}

SLTNode* find(SLTNode* plist, SLTDateType* y)
{
    SLTDateType x;
    printf("请输入参考位置数据和在此插入或更改的数据：\n");
    scanf("%d %d", &x,y);
    SLTNode* ret = SLTFind(plist, x);
    return ret;
}

总结

单链表的一些功能并没有达到我们想要简化的目的，但是这不代表单链表就没有用处，它是我们学习其他链表的基础，正所谓基础不牢，地动山摇。我们将单链表的知识熟稔于心，学习其他链表才能得心应手。后面介绍的双向循环链表才是我们最常用的数据存储结构。