单链表实现

  • 一、为什么会存在单链表？
  • 二、什么是单链表？
  • 三、单链表结构定义
  • 四、单链表的基本操作
    • 1、 创建结点
    • 2、 销毁链表
    • 3、 打印链表
    • 4、 尾插节点
    • 5、 头插结点
    • 6、 尾结点的删除
    • 7、 头结点的删除
    • 8、 单链表的查找
    • 9、 单链表在pos位置之后插入
    • 10、单链表在pos位置之后删除
  • 五、链表功能实现汇总

一、为什么会存在单链表？

前文我们介绍了顺序表，可以知道顺序表并不是完美的，也是有有一些缺陷的：

比如：
1、顺序表的头插、头删、中间插入、删除元素的操作所花费的时间开销很大，时间复杂度都是O（N^2）;
2、动态顺序表尽管已经尽可能的减少空间开销了，但是还是存在一定的空间开销，并不能保证所开辟的空间能够完全被利用；
3、空间增容是有时间消耗的，拷贝数据，释放旧空间。会有不小的消耗；

为此为了解决这些问题，单链表就应运而生了；

二、什么是单链表？

单链表逻辑图：


单链表同顺序表一样，都是线性表，除了首尾节点之外，任何一个节点都有自己的前驱和后继；但是单链表每个节点在物理上的地址是不连续的或者说是随机的，也就是说单链表的节点是要一个就开一个，不会过多的开辟空间；这一点正是弥补了顺序表的不足；

三、单链表结构定义

从上面的逻辑图我们就可以看出，每个节点的类型应该是一样的，节点主要分为数据域和指针域，同时对于一串链表来所，最后一个节点的指针域一定是NULL，以此来标记这是链表的结尾；同时我们只需要知道单链表的头节点，就可以很好的管理整个链表；
同时我们给出结点类型：

四、单链表的基本操作

与顺序表一样具备增删查改的基本功能：

我们先实现一些简单的操作：

1、 创建结点

我们前文说了管理一个链表需要一个头节点的指针就可以了；
为此我们可以专门设置一个SListNode*head=NULL;
来维护我们的单链表，该指针就保存头节点的指针就行了；
当然我们能进行这些操作，我们得先写一个函数来进行创建节点的操作，只有有了节点，我们才能开展后续操作：

// 动态申请一个节点SListNode* BuySListNode(SLTDateType x)//我们可以将数据在创建节点的时候就存入结点{SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));if (!tmp)//节点开辟失败，程序直接结束exit(-1);tmp->val = x;tmp->next = NULL;return tmp;}

2、 销毁链表

我们的节点都是从堆区开辟的，当我们不在使用单链表时，我们应该将单链表销毁（也就是将所开辟的每个节点进行释放，否则容易找出内存泄漏）；
思路：
当然我们要考虑一下特殊情况，看看我们的思路能不能解决特殊情况，假设我是个空表，我的逻辑能不呢处理？
表为NULL，按照刚才逻辑，cur==NULL，cur都为NULL不会进入循环，也就是说代码什么也不会左，不会造成对NULL指针释放（对NULL释放也没事），也就是说，我们刚才的逻辑适合，无需对空表特殊处理；
代码实现：

// 单链表的销毁void SListDestroy(SListNode* plist){SListNode* cur = plist;SListNode* next = NULL;while (cur)//空表不会进入循环{next = cur->next;free(cur);cur = next;}}

3、 打印链表

打印链表和销毁链表的逻辑是一样的，只要cur初始化为头节点，只要cur不等于NULL，我们就打印cur所指结点的指针域，然后cur往后走，当cur走到NULL的时候，我们就不用打印了，就可以结束打印了，同时也不需要对空表特殊处理：
代码实现：

// 单链表打印void SListPrint(const SListNode* plist)//我们最好加上const修饰，这样更严谨；因为我们指向读取结点里面的值，并不想修改{const SListNode* cur = plist;while (cur){printf("%d->",cur->val);cur = cur->next;}printf("NULL\n");}

4、 尾插节点

尾插结点故名思意就是在链表的尾部加入一个结点，然后再把链表的结点串起来，得到一个新链表；
当然我们要在尾部插入，就得找到最后一个结点对吧，最后一个结点有什么特点？
是不是最后一个结点的指针域为NULL啊，我们只要找到某个结点的指针域为NULL的就是最后一个结点，按照此思路，我们画图理解：
画图演示：

最后我们将开辟好的以初始化好的新节点直接连在最后一个结点末尾即可；
至此我们需要考虑一下特殊情况，假设传过来的是空表？
cur=NULL；
我们在判断cur->next等不等于NULL时会对NULL解引用，会报错，
这是编译器不能容忍的；
因此我们需要对空表这种情况需要单独处理；
为什么参数要设计成二级指针？

当然这两种情况混合在一起的话，我的链表的头指针就会发生变化；我们上面不是说了嘛，我们利用一个SListNode*head=NULL；head变量来维护整个链表，既然我们会该表head变量里面的值，我们是不是就需要传其地址才可以（才可以在另一个作用域，操作head变量里面的内容，可以这么理解head也是一个变量，也是在栈上开辟的，因此也是一块空间，只不过这块空间的名字叫做head，我们现在想在另一个作用域对该作用域下的head进行更改内容的操作，只能传这个空间的地址，只有这样，我们在另一个作用域的改变才能影响到head的取值，这也是为什么函数参数要设计成二级指针的原因），又由于head本身就是一个一级指针变量，我们对一级指针变量取地址，就再次得到一个地址，这个地址叫做二级指针，因此我们在参数设计时，应当串以二级指针；

代码实现：

// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x){assert(pplist);//为了避免使用者乱传，先断言一下SListNode* cur = *pplist;SListNode* NewNode = BuySListNode(x);if (cur)//表不为NULL{while (cur->next){cur = cur->next;}cur->next = NewNode;}else//空表{*pplist = NewNode;}}

5、 头插结点

顾名思义，就是在头部插入结点，因此我们的头指针也会发生改表，为了便于管理，我们参数也应该设计成二级指针；
思路分析：cur表示没插入之前的头节点，NewNode表示新结点，那么只需把新节点的指针域，保存一下上一次的头节点cur，就完成了链表的头部插入，最后在更新一下头节点就完成了；
同时考虑一下NULL表能不能实现？
事实上空表，按照这个逻辑也是OK的（读者可以自行验证）为此我们无需对空表进行特殊处理；
代码实现：

// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x){assert(pplist);SListNode* cur = *pplist;SListNode* NewNode = BuySListNode(x);NewNode->next = cur;*pplist = NewNode;}

6、 尾结点的删除

上面讲了头节点的插入和尾结点的插入，接下来我们来讲讲尾结点的删除；
首先先讲解尾结点的删除：
首先想要删除尾结点，我们得首先知道尾结点，其次还得知道尾结点的下一个结点，这个好说，只要找到了尾结点，就找到了尾结点的下一个，关键是我们最后想把链表链接起来就得知道尾结点的上一个结点，为此我们得定义一个prev指针来记录尾结点的前一个结点；
同时cur找尾，cur找尾与尾插思想基本一直，只不过多了一步prev=cur
当然我们能删除结点的前提条件就是表不为NULL，如果表都为空了，那还删个屁，直接给你报错提醒；
所以我们最好断言一下链表是否为空！！！
画图理解：


当然我们考虑一下特殊情况，只有一个结点时是否能狗满足我们上述的逻辑？

代码实现：

// 单链表的尾删void SListPopBack(SListNode** pplist){assert(pplist);assert(*pplist);//链表为NULL就不要在删除了SListNode* cur = *pplist;SListNode* prev = NULL;if (!cur->next)//只有一个节点需要单独处理{free(cur);*pplist = NULL;}else{while (cur->next){prev = cur;cur = cur->next;}free(cur);prev->next = NULL;}}

7、 头结点的删除

也就是删除第一个结点，我们的头指针肯定该表，为了便于维护该链表，我们的参数也应该使用二级指针；
当然删除操作的前提条件就是要有的删，对于空表来说，我们删个毛！！
为此我们最好断言一下；
头节点的删除比较简单，我们可以先根据现有的头结点，找到它的下一个结点next，然后再释放掉头节点，就完成了头节点的删除操作，最后再将新的头节点跟新一下，我们不就完美实现了头节点的删除操作！！
画图：

当然我们依旧考虑一下特殊情况，只有一个结点的时候，上述逻辑是否能正常完成：
显然是可以的：

代码实现：

// 单链表头删void SListPopFront(SListNode** pplist){assert(pplist);SListNode* cur = *pplist;assert(cur);//链表为NULL就不再删除了*pplist = cur->next;free(cur);}

8、 单链表的查找

对于查找功能来说，我们并不需要更改链表里面的任何内容，我们只会读取数据，更不会修改头节点，因此此我们函数参数设计时就不必传二级指针了，就只需要一级指针就可以了，当然为了严谨，最好加上const修饰；
我们查找的思路也很简单，就是遍历链表，一个一个比较，只要找到了等于目标值的就返回该节点的指针；

当然如果链表都遍历完了都没找到的话，我们就返回NULL，表示没找到；
代码实现：

// 单链表查找SListNode* SListFind(const SListNode* plist, SLTDateType x){assert(plist);//链表为空就不在找了const SListNode* cur = plist;while (cur){if (cur->val == x)break;elsecur = cur->next;}return (SListNode*)cur;//避免返回类型不一致，抱警告}

9、 单链表在pos位置之后插入

也就是说现在我给你一个合法的结点指针（保证该指针再链表中存在），然后你在该结点的后面加一个指针；这不简单？
现在我们通过pos可以知道它的下一个结点next（next=pos->next），我们就把新节点插在pos位置后面，然后再把next插在next前面就行了：
画图：

如果pos位置就在表尾？
那么next=NULL；
pos->next=NewNode;
NewNode->next=next;
代码还是跑的通；
当然如果pos为NULL的话有两种处理方式：
1、直接尾插；
2、直接报警告，因为我是再pos的后面插入，我怎么能再NULL后面插入呢？
本文采用第二种；
代码实现：

// 单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x){assert(pos);//NULL指针可不能链接下一个数据;SListNode* next = pos->next;SListNode* NewNode = BuySListNode(x);pos->next = NewNode;NewNode->next = next;}

现在我们可以思考一个问题？
为什么不在pos位置之前插入？

再pos之后插入，操作更简单；函数参数太少，由于这是单链表，我们无法知道pos的前一个节点，就无法将新节点在pos节点和pos前一个节点之间链接起来；
那如果我现在给定链表的头指针，那么我们又该怎么做？
当然既然要在pos前面解决我们就必须知道pos的前一个指针；

还是画图解决：

这是大概思路，当然我们需要
考虑一下特殊情况：
1、表为NULL的是时候，prev=NULL;cur=NULL;直接进行尾插或头插；
2、pos刚好为头指针的时候；prev=NULL；cur=pos；直接进行头插；这时候头节点会被改变，所以我们的函数参数应该设计成二级指针；

综上述两种情况，我们建议直接使用头插；
这便是再pos之前插入的大概思路，读者可以自己研究一下代码如何写？

10、单链表在pos位置之后删除

与pos位置之后插入一个道理，我们能轻松找到pos下一个结点；
（我们同样保证pos合法）

考虑一下特殊情况，pos刚好等于尾指针？
是不是就没有东西可删了，直接报警告就可以了；
代码实现：

void SListEraseAfter(SListNode* pos){assert(pos);//不要对NULL指针操作;assert(pos->next);//如果pos是尾节点，就没东西可删SListNode* Next = pos->next->next;free(pos->next);pos->next = Next;}

还是同样的问题：

为什么不删除pos位置？
理由和上一个pos位置之前插入一样；
那么我先在给你头结点嘞？又该如何操作？
那么我就需要取寻找pos的前前一个结点；
cur还是从头节点开始遍历，然后我们怕段cur->next->next与pos的关系：

考虑特殊情况：
1、pos为头节点，前面没有可删除的直接报警告；assert(*pplist!=pos);//我们必须传二级指针，因为我们头节点时可能被改变的；

2、pos为第二个结点，直接实施头删；if(*pplist->next==pos)

当然我们最先得保证链表有的删的；
（读者可以自行尝试写出相关代码）

五、链表功能实现汇总

函数、类型、变量、声明\头文件的包含：

#pragma once#include#include#includetypedef int SLTDateType;typedef struct SListNode{SLTDateType val;struct SListNode* next;}SListNode;// 动态申请一个节点SListNode* BuySListNode(SLTDateType x);// 单链表打印void SListPrint(const SListNode* plist);// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删void SListPopBack(SListNode** pplist);// 单链表头删void SListPopFront(SListNode** pplist);// 单链表查找SListNode* SListFind(const SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入？void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置？void SListEraseAfter(SListNode* pos);// 单链表的销毁void SListDestroy ( SListNode* plist);

功能实现：

// 动态申请一个节点SListNode* BuySListNode(SLTDateType x){SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));if (!tmp)exit(-1);tmp->val = x;tmp->next = NULL;return tmp;}// 单链表打印void SListPrint(const SListNode* plist){const SListNode* cur = plist;while (cur){printf("%d->",cur->val);cur = cur->next;}printf("NULL\n");}// 单链表的销毁void SListDestroy(SListNode* plist){SListNode* cur = plist;SListNode* next = NULL;while (cur){next = cur->next;free(cur);cur = next;}}// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x){assert(pplist);SListNode* cur = *pplist;SListNode* NewNode = BuySListNode(x);if (cur){while (cur->next){cur = cur->next;}cur->next = NewNode;}else{*pplist = NewNode;}}// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x){assert(pplist);SListNode* cur = *pplist;SListNode* NewNode = BuySListNode(x);NewNode->next = cur;*pplist = NewNode;}// 单链表的尾删void SListPopBack(SListNode** pplist){assert(pplist);assert(*pplist);//链表为NULL就不要在删除了SListNode* cur = *pplist;SListNode* prev = NULL;if (!cur->next)//只有一个节点需要单独处理{free(cur);*pplist = NULL;}else{while (cur->next){prev = cur;cur = cur->next;}free(cur);prev->next = NULL;}}// 单链表头删void SListPopFront(SListNode** pplist){assert(pplist);SListNode* cur = *pplist;assert(cur);//链表为NULL就不再删除了*pplist = cur->next;free(cur);}// 单链表查找SListNode* SListFind(const SListNode* plist, SLTDateType x){assert(plist);//链表为空就不在找了const SListNode* cur = plist;while (cur){if (cur->val == x)break;elsecur = cur->next;}return (SListNode*)cur;}// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入？参数太少，由于这是单链表，我们无法知道pos的前一个节点，就无法将新节点在pos节点和pos前一个节点之间链接起来void SListInsertAfter(SListNode* pos, SLTDateType x){assert(pos);//NULL指针可不能链接下一个数据;SListNode* next = pos->next;SListNode* NewNode = BuySListNode(x);pos->next = NewNode;NewNode->next = next;}// 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置？参数太少void SListEraseAfter(SListNode* pos){assert(pos);//不要对NULL指针操作;assert(pos->next);//如果pos是尾节点，就没东西可删SListNode* Next = pos->next->next;free(pos->next);pos->next = Next;}