【数据结构】线性表-单链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】线性表-单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

编程语言：C++

前言：

节点：节点是链表的一个基本单元，包含两部分——数据域和指针域，数据域用于存储数据，指针域存储下一个节点的地址，形成链结。
什么是单链表：n个节点链结成一个链表，即为线性表（a1,a2,a3……）的链式存储结构，每个节点只包含一个指针域的链表叫做单链表。
链表组成：头节点、头指针、节点。头结点顾名思义就是第一个节点，并且头结点的数据域一般为空，有时用来存储链表的节点数等信息，在链表中，头结点不是必需要素。头指针就是指向头结点的指针，头指针一般冠以链表的名字，并且头指针是链表的必需要素。
空链表：没有任何有效数据的节点的链表。例：

然后开始创建链表：
我们将创建链表的功能包装成一个函数，参数如下：
第一个参数是我们在函数外创建的一个头指针（也即一张空链表（包含头结点）），第二个参数是我们希望链表所包含的节点个数
【数据结构】线性表-单链表

在此基础上，我们有两种创建链表的方式：头插法、尾插法。

头插法：
原理如下：将每次创建的新节点插入头节点和上一个创建的节点之间。
【数据结构】线性表-单链表
步骤：

代码实现：
【数据结构】线性表-单链表

尾插法：
原理如下：每次创建的新节点插在上一个节点后面（链表尾部）。
【数据结构】线性表-单链表

步骤：

代码实现：
【数据结构】线性表-单链表

链表数据的读取
读取指定节点存取的数据，必需从头结点开始遍历链表，直到找到指定节点然后读取数据。
步骤：
①创建一个指针p（用来遍历链表），和一个计数器i（p当前指向的节点）
②让p指向第一个节点开始遍历链表，同时i自增
③如果找到了指定节点，则读取节点数据，并反馈信息（以1为例）
④如果没找节点，则反馈信息（以返回0为例）
代码实现：
单链表数据的插入
遍历链表到达指定位置后将数据插入即可。
步骤：
①创建指针p（遍历链表），创建指针s（插入的节点），创建计数器变量i
②遍历链表，到达指定位置将s插入
代码实现：
单链表数据的删除
用一个指针遍历到达指定节点处，然后进行删除操作（改变节点指针指向，绕过待删除节点即可），并索回所删除的数据。
步骤：
①创建一个指针p遍历链表，创建一个指针辅助删除，一个计数器变量i
②遍历至指定位置进行删除操作
代码实现：

补充：其实完全可以不需要创建指针q，“q = p->next;p->next = q->next;”两步可用“p->next = p->next->next”替代，效果相同。