链表在生活中随处可见。比如火车车厢，是一节一节连在一起的；脊椎动物脊椎骨的骨骼结构，也是一节一节构成一个链表结构；还有责任链、证据链等。凡是有1个头和1个尾，中间环环相接的结构都可称为链表结构。链表结构常会和数组结构混淆，很多编程语言中甚至把链表当成数组用，称为可变长数组。链表与数组最大的区别在于是否可以自由伸缩，数组一经声明，长度就被确定，不可伸缩了；而链表则可以自由增加或删除自身的节点，让自己的长度变化，这是数组做不到的。另外，因为数组是定长的，所以在声明时需要指定自身元素的类型，而链表是变长的，任何类型都可以往链表上放。

　　链表结构

　　链表是由多个节点构成的线性的存储结构，每个节点都至少包含如下两部分：

　　(1)数据部分：保存该节点的实际数据引用。

　　(2)地址部分：保存的是下一个节点的内存地址，如下图所示。

　　链表结构链表结构的特点如下：

　　(1)节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

　　(2)访问时只能通过头指针进人链表（无尾指针的情况下），并通过每个节点的指针域向后扫描其余节点，所以寻找第一个节点和最后一个节点所花费的时间不等。

　　链表结构的优缺点如下：

　　优点：数据元素在链表中进行扩充、插人、删除等操作时不必移动数据，只需修改链接指针，修改效率较高。

　　缺点：存储密度小，存取效率不高，必须采用顺序存取，即存取数据元素时，只能按从头到尾的顺序逐个进行访问。

　　链表种类包括：单向链表、双向链表，单向循环链表和双向循环链表。

　　单向链表

　　单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，其中每个节点都有指针成员变量指向列表中的下一个节点，对链表的访问要通过顺序读取从头部开始。其程序构成结构包括如下：

　　(1)节点类：包含数据（数据元素的指针或映像）和指针（指示后继节点存储位置）。

　　(2)单链表类：包含指向头部的头指针phed和链表长度length。

　　单向链表包括如下方法：

　　(1)追加：在链表尾部追加数据节点。

　　(2)遍历：扫描整个链表，依次获取链表中的全部数据。

　　(3)随机访问：任意获取链表指定下标的节点数据。

　　(4)随机插入：在链表的任意指定位置插入节点。

　　(5)随机删除：删除链表中指定位置的节点。

　　单向链表的追加和遍历

　　单向链表的追加（append）方式包括头插法和尾插法。

　　(1)头插法：新加入的节点插在链表头部，头指针始终指在最后插入的一个节点，链表方向与输入顺序相反。遍历时先得到的是最后输入的节点。

　　(2)尾插法：新加入的节点追加在链表尾部，头指针始终指在最先插入的第一个节点，链表方向与输入顺序相同。遍历时先得到的是最先输入的节点。

　　例题１：尾插法单向链表的追加和遍历。

　　分析：尾插法是最常用的插入方式。尾插法的算法逻辑：需要插入链表的数据首先被实例化到节点中（即实例化一个节点，搭载待入链数据）；然后判断是不是头节点（即链表没有节点），如果是，直接将头指针指向这个入链节点；如果不是，声明临时指针，通过循环我到链表中的尾节点，把尾节点的后续指针指向这个入链节点。

　　单向链表尾插法的算法图解分析如下图所示。

　　程序代码：

　　运行结果：

　　例题２：单向链表的随机访问。

　　所谓单向链表的随机访问：是指输入要获取的节点的序号，获得指定序号节点上的数据。随机访问的算法逻辑：传入需要获取的节点序号seqnum，定义一个临时指针和一个计数器，临时指针从头指针所指向的节点向后顺序查找；计数器随着指针每经过一个节点计数加１,从0开始累加，直到累加到seqnum为止，此时临时指针指向的节点就是要获取的节点。单向链表随机访问算法的图解分析如下图所示。

　　程序代码：

　　运行结果：

　　例题３：单向链表的随机插入。

　　单向链表的随机插入：是指用户可以在单向链表的任意指定节点位置前端插入数据（换句话说，就是用新节点放在任意指定位置，原来位置的节点在新节点之后），链表结构保存完好。

　　单向链表的随机插入算法逻辑：根据传来的数据生成节点，然后根据传来的下标位置，声明计数器和临时指针，临时指针根据计数器累加从头部移动到下标位置节点的前一个节点，然后将待插入节点的next指针指向下标位置节点，而前一个节点的next指针转指向待插入节点，新节点完成入链。单向链表的随机插入算法图解分析如下图所示。

　　程序代码：

　　运行结果：

　　例题４：单向链表的随机删除。

　　单向链表的随机删除：是指用户输入索引位置，可以在单向链表的对应节点位置删除索引节点，链表结构保存完好。

　　单向链表的随机删除算法逻辑：根据传来的下标位置，找到待删除的索引节点的前个节点（头节点特殊处理），把前一个节点的next指针，指向待删除节点的next节点，然后把待删除的next指针置空，待删除节点从链表中移除。单向链表的随机删除算法图解分析如下图所示。

　　程序代码：

　　运行结果：

　　思考练习题：本文的链表采用的是尾插法。请改用头插法修改例题１的追加（append）方法。然后把例题１到４重做一次，看看结果有何不同。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社