【数据结构】线性表-单链表
编程语言：C++
前言：
- 节点：节点是链表的一个基本单元，包含两部分——数据域和指针域，数据域用于存储数据，指针域存储下一个节点的地址，形成链结。
- 什么是单链表：n个节点链结成一个链表，即为线性表（a1,a2,a3……）的链式存储结构，每个节点只包含一个指针域的链表叫做单链表。
- 链表组成：头节点、头指针、节点。头结点顾名思义就是第一个节点，并且头结点的数据域一般为空，有时用来存储链表的节点数等信息，在链表中，头结点不是必需要素。头指针就是指向头结点的指针，头指针一般冠以链表的名字，并且头指针是链表的必需要素。
- 空链表：没有任何有效数据的节点的链表。例：
- 单链表的创建
创建单链表之前先要创建节点：
然后开始创建链表：
我们将创建链表的功能包装成一个函数，参数如下：
第一个参数是我们在函数外创建的一个头指针（也即一张空链表（包含头结点）），第二个参数是我们希望链表所包含的节点个数
在此基础上，我们有两种创建链表的方式：头插法、尾插法。
头插法：
原理如下：将每次创建的新节点插入头节点和上一个创建的节点之间。
步骤：
- 声明一个指针p（用来生成新节点），和一个计数器变量i
- 初始化一张空链表（也就是创建一个头指针），让头结点指针指向NULL
- 循环：
①生成一个新节点赋给p
②给节点赋值（例子中生成一个随机数存入p->data）
③将节点插入头结点和上一节点之间
代码实现：
尾插法：
原理如下：每次创建的新节点插在上一个节点后面（链表尾部）。
步骤：
- 声明一个指针p（用来生成新节点），声明一个尾指针r（方便往链表尾部插入新节点），一个计数器变量i
- 初始化一张链表（也就是创建一个头指针)，让头结点的指针指向NULL
- 让尾指针r指向头结点
- 循环：
①生成一个新节点赋给p
②给节点赋值
③将节点插入链表尾部
④保持尾节点的指针指向NULL（方便作为查找等操作的判断标志）
代码实现：
-
链表数据的读取
读取指定节点存取的数据，必需从头结点开始遍历链表，直到找到指定节点然后读取数据。
步骤：
①创建一个指针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”替代，效果相同。
注：
- 涉及到改变链表数据的操作时，应当使用引用传递
- 对于链表的各种操作并非一成不变，应当根据实际情况灵活变换
热门相关：帝少宠妻有点甜 修罗武帝 明尊 惹火小辣妻：老公，用力点 美漫之大冬兵