单链表是个小难点，所以必须多图多真相！
单链表的读取
在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪没办法一开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem，在算法上，相对要麻烦一些。
获得链表第i个数据的算法思路：（1）声明一个指针p指向链表第一个结点，初始化j从1开始；
（2）当ji时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；（3）若到链表末尾p为空，则说明第i个结点不存在；（4）否则查找成功，返回结点p的数据。实现代码算法如下：
说白了，就是从头开始找，直到第i个结点为止。由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是“工作指针后移”，这其实也是很多算法的常用技术。此时就有人说，这么麻烦，这数据结构有什么意思！还不如顺序存储结构呢。哈，世间万物总是两面的，有好自然有不足，有差自然就有优势。下面我们来看一下在单链表中如何实现“插入”和“删除”。单链表的插入与删除
单链表的插入
1
先来看单链表的插入。假设存储元素e的结点为s，要实现结点p、p-next和s之间逻辑关系的变化，只需将结点s插入到结点p和p-next之间即可。可如何插入呢（如下图所示）？
根本用不着惊动其他结点，只需要让s-next和p-next的指针做一点改变即可。
解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点（如下图所示）。考虑一下，这两句的顺序可不可以交换？
如果先p-next=s；再s-next=p-next；会怎么样？因为此时第一句会将p-next给覆盖成s的地址了。那么s-next=p-next，其实就等于s-next=s，这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的，这点初学者一定要注意。
插入结点s后，链表如下图所示。
对于单链表的表头和表尾的特殊情况，操作是相同的，如下图所示。
单链表第i个数据插入结点的算法思路：
（1）声明一指针p指向链表头结点，初始化j从1开始；
（2）当ji时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；（3）若到链表末尾p为空，则说明第i个结点不存在；（4）否则查找成功，在系统中生成一个空结点s；（5）将数据元素e赋值给s-data；（6）单链表的插入标准语句s-next=p-next;p-next=s；（7）返回成功。实现代码算法如下：
在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据e的s结点。
单链表的删除
2
现在我们再来看单链表的删除。设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。
我们所要做的，实际上就是一步，p-next=p-next-next，用q来取代p-next，即是
解读这两句代码，也就是说把p的后继结点改成p的后继的后继结点。有点拗口呀，那我再打个形象的比方。本来是爸爸左手牵着妈妈的手，右手牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸一下子看呆了，此情景被妈妈逮个正着，于是她生气地甩开牵着的爸爸的手，绕过他，扯开父子俩，拉起宝宝的左手就快步朝前走去。此时妈妈是p结点，妈妈的后继是爸爸p-next，也可以叫q结点，妈妈的后继的后继是儿子p-next-next，即q-next。当妈妈去牵儿子的手时，这个爸爸就已经与母子俩没有牵手联系了，如下图所示。
单链表第i个数据删除结点的算法思路：
（1）声明一指针p指向链表头结点，初始化j从1开始；
（2）当ji时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；（3）若到链表末尾p为空，则说明第i个结点不存在；（4）否则查找成功，将欲删除的结点p-next赋值给q；（5）单链表的删除标准语句p-next=q-next；（6）将q结点中的数据赋值给e，作为返回；（7）释放q结点；（8）返回成功。实现代码算法如下：
这段算法代码里，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。
分析一下刚才我们讲解的单链表插入和删除算法，可以发现，它们其实都是由两部分组成：第一部分就是遍历查找第i个结点；第二部分就是插入和删除结点。
从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果我们不知道第i个结点的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果我们希望从第i个位置，插入10个结点，对于顺序存储结构意味着，每一次插入都需要移动n-i个结点，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。
单链表的整表创建
回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
单链表整表创建的算法思路：
（1）声明一指针p和计数器变量i。
（2）初始化一空链表L。（3）让L的头结点的指针指向NULL，即建立一个带头结点的单链表。（4）循环：①生成一新结点赋值给p；②随机生成一数字赋值给p的数据域p-data；③将p插入到头结点与前一新结点之间。实现代码算法如下：
这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法。
可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。
实现代码算法如下：
注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
这里需解释一下，r-next=p;的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如下图所示，当中①位置的连线就是表示这个意思。
r-next=p;这一句应该还好理解，我以前很多学生不理解的就是后面这一句r=p;是什么意思？请看下图。它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该让p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。
循环结束后，那么应该让这个结点的指针域置空，因此有了“r-next=NULL;”，以便以后遍历时可以确认其是尾部。
单链表的整表删除
当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。
单链表整表删除的算法思路如下：
（1）声明一指针p和q。
（2）将第一个结点赋值给p。（3）循环：①将下一结点赋值给q；②释放p；③将q赋值给p。实现代码算法如下：
这段算法代码里，常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(p);p=p-next;即可。可这样会带来什么问题？
要知道p指向一个结点，它除了有数据域，还有指针域。你在做free(p);时，其实是在对它整个结点进行删除和内存释放的工作。这就好比皇帝快要病死了，却还没有册封太子，他儿子五六个，你说要是你脚一蹬倒是解脱了，这国家咋办，你那几个儿子咋办？这要是为了皇位，什么亲兄弟血肉情都成了浮云，一定会打起来。所以不行，皇帝不能马上死，得先把遗嘱写好，说清楚，哪个儿子做太子才行。而这个遗嘱就是变量q的作用，它使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。明白了吗？
单链表结构与顺序存储结构的优缺点
简单地对单链表结构和顺序存储结构做对比：
通过上面的对比，我们可以得出一些经验性的结论：
■若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
■当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单地说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。
好了，这两天说了这么多，先消化一下，明天我们进入静态链表。
《大话数据结构溢彩加强版》
ISBN：-7---3
程杰编著
定价：元
正值双11，京东成交价56.6元，47折！一定记得领卷哦~
清华出版社微店购买，免邮~
戳下面标题回顾课程
第1天如何入门数据结构与算法
第2天数据结构与算法学习地图
第3天趣解算法从今天开始
第4天全面掌握基本概念和术语第5天谈完数据类型，该小小总结一下了第6天算法导论第7天算法效率的奥妙第8天讲完复杂度，该总结总结了第9天说说线性表第10天继续攻坚线性表▼以下课程敬请期待
第11天说说单链表
第12天静态链表最强攻坚指南
第13天最后两种表，搞定收工
第14天最后一节课啦，切入栈与队列
精彩推荐：全彩Pro/EWildfire5.0装配案例实战：美容仪图解Python经典河内塔问题附源码图说C语言灵*——指针用Unity制作一个有大脑的NPC
附视频（限免观看）预览时标签不可点收录于话题#个上一篇下一篇