我们学习过顺序表时，一旦对头部或中间的数据进行处理，由于物理结构的连续性，为了不覆盖，都得移，就导致时间复杂度为O（n），另有一个潜伏的题目就是扩容，假如我们扩容前是100个大小的元素空间，一旦扩容以后（我们就说二倍的扩），那就是200，但我们现实上就只存105个元素，那不就有95个元素所对应的空间被浪费了吗？怎样才气解决如许的题目呢？
带着疑问，来学习线性表的其中之一，链表。
一、链表
链表是物理存储结构上非连续的线性表，数据元素的逻辑顺序是通过链表中的指针来实现的。
按照指针方向链表分为单向链表，双向列表和循环链表。
按内存管理的话还是静态链表和动态链表
二、单链表
本次就进行单链表的学习。
1.单链表概述
单链表一般作Single List
单链表是什么东西呢？
单链表就好像是火车一样，火车的每个单位是车厢，车头是动力，车厢与车厢之间存在有结构毗连。
为什么要这么对比呢？
单链表的基本单位就是结点，结点与结点之间由指针毗连起来，这是静态的看；火车在淡旺季可以选择加车厢和减车厢，而我们的单链表对应的操纵就是增加大概删除结点。
单链表属于链表，根据指针的方向取名单链表，单链表结点间的指针方向是只有一个的。
我们在申请顺序表的大小的时候用的是realloc，第一个参数是必要修改的内存的所在，第二个参数是改为的内存空间的大小，这个内存空间我们申请的时候直接是一整块全部申请下来，但是对于单链表则不同，如上面画的图，我们每次申请都仅仅申请一个结点，任意取出来逻辑上相邻的两个结点：
现在视角落在存储了整型2的这个结点上，这个结点存储了两个东西，一个是数据，一个是下一个结点的所在，由此我们的单链表的结点就是一个结构体变量，一个是存储的数据，一个是结点结构体范例的指针（因为通过这个指针访问下一个结点时，还是一个结点结构体，以是必须是结点结构体范例的指针变量）。
2.链表的性质
由这个大略图给出链表的通用特性：
①链表在逻辑上是连续的，物理空间上不肯定连续
②结点一般是在堆上申请的
③从堆上申请的空间不肯定连续
相识即可。
3.单链表结点结构的创建
非常清晰了，直接给出来：
为了单链表存储数据范例的可修改性，一个typedef，为了后续与结点这个结构体操纵的简便性，再来一个typedef，这点在顺序表中已经见过了，不多解释。
不管是先前的图片还是后续的创建，都展示出告终点的两个属性，一般存放数据的被称作数据域，存放下一个结点所在的叫做指针域。
4.单链表的打印
有了单链表的结点，假如要实现我们所画的图片的效果应该是如许的：
为每一个结点创建内存空间，而且赋值，现实上发现，我们逻辑上的1,2,3,4是通过指针来实现的。
假如对于如许的一个链表，我们该怎样实现遍历打印呢？
通过plist开始访问链表的数据，进去打印该结点的数据，而且将指针该为下一个结点的所在，终极下一个结点的next指针为空则遍历完成。
进去就打印，而且跳到下一个链表结点里，假如不为空则继承打印，为空阐明已经遍历到尾，可以停止。
固然，其实可以把assert换一下，因为假如链表为空，直接打印个NULL，也可以：
5.单链表的插入结点操纵
①单链表的尾插
先想尾插的参数，肯定得把单链表的所在传已往吧，然后你插什么总得告诉我吧。
以是就俩参数，一个是单链表的所在（如上面的plist），另有想要插入的元素是什么。
进去第一件事可不是去插入，就像顺序表插入一样，你总得看看有没有地方让你插入吧，类比过来，就得先生成个结点，这个结点专门用来存放本次插入的值，指针的话由于尾插，以是肯定是NULL。
有了这个结点以后就得把它像毗连火车车厢一样接上去，很显然，必要先找到链表尾，其实我们打印的时候用的while循环竣事后，指针已经到了单链表的尾了，以是拿过来即可，找到尾以后把原来的尾的指针从NULL酿成新创建的结点的所在即可。
思绪有了，代码表达：
逢开辟必查抄。
而链表的插入分为空链表的尾插和非空链表的尾插，至于为什么，先往下看：
非空：
拿着链表所在，遍历到最后，把创建的新结点所在赋给尾结点即可。
但是假如是空链表呢：
你非空确实传过来所在，我顺着所在修改值就行，但是假如是空的链表呢？你传过来的是什么，是NULL，那你再修改，对现实的链表根本就是无济于事啊。以是为了对真正的链表的里面的值进行修改，我们不能传值了，只能传过来这个空链表的指针的所在（为了通过这个所在去修改这个指针）
所在的所在，大概说一级指针的所在应该用二级指针来承接，以是形参写的时候应该是二级指针，修改为：
其中，链表不为空必要遍历到链表尾部的所在，因为后续必要用这个所在去修改NULL，如许的话到尾结点就该停，而尾结点与其他结点的不同就是下一个结点的所在为空。
测试代码如下：
阐明确实插入了。
固然，还得防范一下传过来的指针，究竟plist可以为空（即链表为空），但是pplist存的但是链表的所在的啊，这玩意为空算哪门子事：
加个assert防范一下。
②单链表的头插
还是有了履历以后，参数还是pplist，而且分开链表为空和链表不为空的环境：
起首还是不为空：
让plist指向我们的newnode，newnode指向我们的第一个结点，如许的话赋值就得先把plist的值赋给newnod->next了，然后再把plist的值修改了：
而且发现，假如链表为空，plist为NULL，赋已往，newnode所在给plist，也没毛病。
调试完毕，没啥题目
6.单链表的删除结点操纵
①单链表的尾删
开释最后一块空间，并将尾结点的前一个结点的next指针改成NULL。
这就要求你必须找到两个位置的指针，一个是ptail，一个是ptail前的prev，我们以如许的思绪来想办法遍历，示意图：
ptail开始指向第一个元素，prev由于必须在ptail前，此时应该为空；
进入检测以后看看这个结点是不是尾结点，是的话就该停止遍历了，即判断条件为ptail->next != NULL。
题目就在于循环体怎样实现ptail以后走的同时来让prev在ptail前，很简单，可以说是keep up with：
假如不是尾结点的话，prev先站到现在ptail的位置，因为下一步就是后移，如许出了循环就是一个在前一个在后的效果，如：
固然不能忘了开释空间和防范野指针：
最后三条解释一下，prev->next = NULL确实是修改了链表的现实结构，因为prev是尾结点前那个结点的所在，顺着所在肯定能修改乐成现实的链表；有了尾结点所在，free不消多解释；重点在于ptail = NULL，它可不是真的把尾结点指针置空了，大概说它纵然置空也不影响现实链表中的所在还存在（假如存了的话），只是free以后风俗置空，作用是防止在函数内部再被调用。
画图解释：
正如我们插入操纵的时候必要防范链表是不是空链表一样，对应过来就是，我们删除的恰恰就是唯一的一个结点，即第一个结点，代码思绪还行不行得通：
就盯着这个看，很显着，上来就是NULL，这么一搞，prev直接就是随机值。
以是假如只有一个结点的话，直接free而且赋plist为空即可（固然，在函数里是*pplist）。
完善：
测试：
两头代码都乐成。
②单链表的头删
头删其实没什么可多说的，把plist修改为原plist->next，再对原plist的空间开释即可：
测试代码：
没啥好讲的，连图都不消画，空想一下就能想出来。
7.单链表的查找操纵
参数：你想查哪个链表，所在给我，你想查链表里哪个元素，元素也给我，以是就俩参数，而且不会对链表的结构产生改变，传值即；上面都没说返回值的事，因为不管是打印还是对链表结构的改变，不必要返回什么，但是查找，你找到了给我个所在让我知道啊，找不到你总得告诉我找不到吧。
查找我写了两个版本：
第一个版本是如许的：
最开始现实上我写的是：
while (phead->data != x)
{
phead = phead->next;
}
if(phead == NULL)
return NULL;
else
return phead;
思绪就是，要是这个结点的值不是我要的值，就往死里给我遍历，跳出循环以后有俩环境，一个就是为空了都，那阐明找完都没找到，直接返回NULL就行；一个就是找到了，跳出循环即可。
题目有俩，一个是遍历到尾了，phead就是NULL，再解引用去判断data与x相称不相称就不礼貌了，再来就是其实我写的if-else语句其实就是return phead的意思，（我刚开始就意识到了if-else的化简，丝毫没有发现第一个题目，最后代码报错查抄了查抄才发现）
第一次查抄修改为：
while (phead->data != x)
{
phead = phead->next;
}
return phead;
然后发现空指针解引用题目：
while (phead->data != x && phead != NULL)
{
phead = phead->next;
}
return phead;
加上了还给我整事，后来想了想，这就是当时学逻辑运算符的短路题目，假如遍历完都找不到你先解引用才去检验是不是空，如许代码固然还是会报错，以是还得：
while (phead != NULL && phead->data != x)
{
phead = phead->next;
}
return phead;
才没毛病。
第二个版本是如许的：
while循环疯狂遍历，每次遍历到的结点去检测一下data，假如遍历完都没找到，直接返回NULL。
这个版本写出来其实是因为想放弃第一个版本了，但是又因为自己不服气，就有了上面的修改过程。
8.单链表指定位置的插入和删除操纵
①指定位置之前插入数据
指定位置的插入和删除，肯定是在某个特定的值前才进行，以是链表在这种环境下不会为空
这点意味着要在3这个结点前插结点，创建新结点就不说了，来看指针怎么变，这种环境下传的肯定是链表中某个节点的所在，如许看来的话newnode->next不成题目，但是前面一个结点的next指针可就炸缸了啊，因为你给我的是3的指针，给了这个我以后遍历顺着走就行，往前遍历可就得想想办法了，还是得写一循环遍历，当该指针next为3这个结点就停手，给目的节点起名pos，给目的节点前一个结点起名prev（取自previous）。
预备工作：
预备好结点，预备好要改变的值以后，就是赋值
最后：
但有一特例，假如指定位置前是链表的头呢：
这个时候的prev->next永久不会是pos，就会无休止的找下去，如许的话会导致出错，干脆假如plist==pos，直接调头插去，懒得再写逻辑了，反正也跟写头插一样：
测试代码：
不管头插还是中间的插入都没啥大毛病。
②指定位置之后插入数据
注意参数即可，因为链表的结点的成员是一个data，一个next指针，以是以后插根本不必要指定位置的前一结点的所在，也就不必要链表的头结点所在。
先按照正常元素往中间插的思绪写：
newnode->next指向pos->next，pos->next指向newnode即可，肯定要注意顺序。
newnode->next = pos ->next;
pos->next = newnode;
和
pos->next = newnode;
newnode ->next= pos ->next;
真按照下面的干了，直接炸了，因为pos->next直接被你用newnode覆盖了，导致第二句代码newnode->next指的还是newnode自己。
直接写出来就行，但是插入还得小心点（空就不消考虑了，肯定是查找后的指针，不大概为空，即有pos就不消验空），想想第一个结点插入，由于是之后，那跟找中间的插也没啥区别；想想尾结点插入：
对着代码看，也没啥毛病。
测试一下：
没犯啥毛病，乐成了。
③删除指定位置的结点
一个遍历到pos前，一个赋值改指针指向，一个开释：
然后就是看看首大概尾会不会出幺蛾子：
上来就发现了，我们的逻辑是prev->next是不是pos，根本无法检测pos刚好为头的环境，以是还是写个if-else去头删：
尾结点没炸。
测试：
④删除指定位置后的结点
还是说，指定位置后可以直接通过pos找到，就不必要传plist了。
不想写那么多next就将要删去的结点的所在存到del里，方便自己看以及方便改指针和开释：
这么写增加代码可读性。
想想头尾会不会出啥题目，头的话头后删，跟我们从中间找一个结点删效果一样；尾结点背面没结点，想了想指定位置后结点删去不能有尾结点，以是加到assert里：
测试：
9.单链表的烧毁
烧毁单链表就把头结点的所在传过来。
很显着，假如直接free掉plist那么背面的结点全部都丢了，以是在free结点前记载下一个结点，直到下一个结点为NULL再停止：
三、对比顺序表和单链表
刚刚学完，可谓是手感火热，顺序表和单链表都有插入和删除操纵。
其中顺序表的头插头删由于其空间的连续性，以是必须先将已有元素后移，才气插入，后移就会用一个循环，时间复杂度是O（n）；
顺序表的尾插尾删，不必要移动数据，以是也不必要循环，插就一句根据所在赋值的事，尾删更简单，直接size--即可。时间复杂度是O（1）
单链表的头插头删，头插由于不必要将其他元素后移，直接针对链表头结点所给指针改变一下next指针；头删就先改头结点指向所在，再free即可。
单链表的尾插尾删，最影响时间复杂度的就是while循环去找尾结点的指针ptail，导致时间复杂度为O（n）。
我们现在就学了这两种数据结构，已经可以看出来，没有哪一种数据结构就能一招鲜吃遍天，各有各的长处，你尾部频繁的增删改，那就用顺序表，头部频繁增删改那就单链表。
解释这个就是为相识释我最开始所说的，学习各种各样的数据结构，是为了算法里选择最优的数据结构。
另外，单链表由于每个结点都是在堆区申请独立的空间，以是不会存在内存浪费的环境，这种优势是针对顺序表来说的，因为在顺序表里有一开辟内存的函数叫CheckCapacity，二倍扩容空间假如不消，那就会浪费。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
