单链表
单链表从出生到毕业
今天，我们来学习一下链表的基本操作，与其相关联的操作大致有9种，我们一个一个来讲解，来揭开链表的神秘面纱
单链表的操作
首先，我们要先定义一个单链表，怎样才可以定义一个单链表呢？
我们要创建一个结构体，来存储需要的数据还有该数据指向的下一个节点，因为单链表是按照创建malloc动态分配内存给它的,我们也要动态的创建链表
第一步 创建一个链表并初始化
我们要创建一个结构体来描绘我们所需要的对象，比如说，我们想描述一个游戏账号，他的id是多少，他在游戏中取得名字叫什么，这些信息需要我们来创建一个链表来依次查询的
//头文件
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1001;
typedef long long ll;
//创建一个存储信息的结构体
typedef struct List {
//游戏id
int id;
//游戏名
char name[10];
}sum[N]; //名字现在，我们的结构体创建完了，我们下一个目的就是要把两个结构体之间进行一个链接，那么要怎么链接呢？这就需要我们再额外定义一个指针变量来记录该数据指向的下一个数据是什么。因此，我们可以再创建一个新的结构体来将我们刚才定义的结构体和刚才定义的结构体所指向的下一个结构体的指针所存储下来
typedef struct Node {
//刚才定义的结构体
sum list;
//list所指向的下一个节点的指针
struct Node* next;
}node; //名字要创建一个链表，我们还需要定义一个头指针，这个头指针是链表的核心，我们之后的所有对链表的操作都是基于头指针来进行的
//创建一个头指针, 意思是 _head指向的下一个节点是NULL
node* _head = NULL; //_head的意思是 —————— _head指向的下一个节点欸，为什么头指针后面是NULL啊，这主要是因为在目前为止，我们并没有对这个链表做什么操作，仅仅只是将这个链表给创建了出来罢了，对其的初始化就是头节点指向空
_head ----> NULL到目前为止，链表就已经被我们创建好了
第二步 链表的插入操作
好的，这一步开始，就意味着我们可以对我们刚才那个链表做手脚了，嘿嘿(●ˇ∀ˇ●)
我们想给纯洁无暇的链表打上我们的颜色，那么我们需要在链表里面添加一些东西，那我们该怎么往里面添加东西呢，我们可以从链表的头部或者尾部添加呢
下面，我来依次介绍这两种插入的方法捏~(￣▽￣)~*
头插法
我们想从链表的头部添加一些东西，那我们就要从改变_head开始，一开始，我们的_head指向的下一个节点是NULL,既然是从头开始添加元素，那么我们就不能再让我们的_head指向NULL力
一开始的样子是这样的
_head ---> NULL我们想让它变成的样子
_head ---> pnewnode1 ---> NULL那么，现在我们就要先动态生成一个新节点捏
节点生成！
//生成一个新的节点
node* pnewnode = (node*)malloc(sizeof(node));
//让新节点的尾部始终是指向NULL的，防止出错
pnewnode->next = NULL;我们生成了一个新的节点，现在我们就要让_head指向我们的新节点，怎么办呢，要像这样
_head = pnewnode;现在，我们的_head指向的下一个节点就是pnewnode啦
那么，如果说，我们还想再次添加一个新节点，用头插法的形式，但是这次的链表已经不是一开始的样子了，那我们又该怎么修改呢？
现在的样子
_head ---> pnewnode1 ---> NULL我们想让他变成的样子
_head ---> pnewnode2 ---> pnewnode1 ---> NULL同理，我们还是要先生成一个新节点捏，怎么生成新节点就如上述所示
//生成一个新的节点
node* pnewnode = (node*)malloc(sizeof(node));
//让新节点的尾部始终是指向NULL的，防止出错
pnewnode->next = NULL;不过，现在的_head指向的下一个节点是pnewnode1，我们想让它指向pnewnode2，我们需要先把我们添加的新节点pnewnode2指向我们的_head指向的下一个节点pnewnode1
像这样
pnewnode->next = _head;然后，再让我们的_head指向的下一个节点指向pnewnode2
_head = pnewnode;这样一来，我们就又添加一个新的节点力(●ˇ∀ˇ●)
总的头插法如下
void add_to_head()
{
//动态分配内存
node* pnewnode = (node*)malloc(sizeof(node));
pnewnode->next = NULL;
//情况1
if (_head == NULL) {
_head = pnewnode;
}
//情况2
else {
pnewnode->next = _head;
_head = pnewnode;
}
//输入
cin >> pnewnode->list->id >> pnewnode->list->name;
}尾插法
可是，只学会一种头插法还不够，我们还要继续学习，继续改造我们的单链表，于是乎，你开始研究尾插法
现在，我们默认我们的单链表还是没有被改造的，它还是纯白无暇的
现在的样子
_head ---> NULL我们想让它成为的样子(注意，我们是从尾部插入的哦这次)
_head ---> pnewnode1 ---> NULL同理，我们动态分配内存
//生成一个新的节点
node* pnewnode = (node*)malloc(sizeof(node));
//让新节点的尾部始终是指向NULL的，防止出错
pnewnode->next = NULL;节点生成！
不过嘛，我们现在的单链表是纯洁的，其实就是我们往_head后面添加一个新节点罢了
如头插法一般即可
_head = pnewnode;但是呢，我们想再次从尾部添加一个新的节点，这时候就不可以像头插法那样进行插入了，我们得采用别的办法
链表有一个性质，就是说，它不像数组那样，你不可以通过下标这种手段直接访问到指定数组的元素，链表需要我们从头节点依次遍历，直到我们找到最后一个有效的元素，像这样
//定义一个指向头节点的指针
node* p = _head;
//依次遍历
while (p->next != NULL) p = p->next;这里的判断就会有人有疑问了，为什么是p->next!=NULL，为什么不是p!=NULL呢，你想，如果我们判断p!=NULL结束的话,那么，我们现在的p节点就是NULL了，它不是我们链表里面的节点啊，所以说，我们是要p->next!=NULL
然后，再让p指向我们所创建的新节点即可
p->next = pnewnode;这样一来，我们就又添加一个新的节点力(●ˇ∀ˇ●)
总的尾插法如下：
void add_to_fail()
{
node* pnewnode = (node*)malloc(sizeof(node));
pnewnode->next = NULL;
if (_head == NULL) {
_head = pnewnode;
}
else {
node* p = _head;
while (p->next != NULL) p = p->next;
p->next = pnewnode;
}
cin >> pnewnode->list->id >> pnewnode->list->name;
}指定位置插入
在学会了头插法插入和尾插法插入后，你感觉还不够，还不能继续改变这个单链表，于是呢，你又想到了一个新方法，想要在某个指定的id后面插入新的节点，这时候该怎么办呢？~(￣▽￣)~*
（下面的讲解默认能够找到指定的位置，总代码上的不是捏）
这时候，其实和上面两种插入方法差不多，尤其是在单链表纯洁无暇的时候是一样的
第一步，还是新建一个新节点
//生成一个新的节点
node* pnewnode = (node*)malloc(sizeof(node));
//让新节点的尾部始终是指向NULL的，防止出错
pnewnode->next = NULL;节点生成！
在链表只有_head节点的时候，我们只要_head指向我们新建的pnewnode节点即可
_head = pnewnode;但是，如果我们已经改变了这个单链表呢？
现在，这个单链表长这样
_head ---> 1 ---> 2 ---> 3 ---> NULL //1 2 3指的是节点id我们想在id为2的后面插入一个新节点，想变成下面这种样子
_head ---> 1 ---> 2 ---> 4 ---> 3 ----> NULL这时候，我们就要改变2号节点的next指针的指向了，我们要让2号节点的next指针指向我们的新节点，我们的新节点的next指针指向2号节点的next指针原来指向的
//新建一个p指向头节点
node* p = _head;
while (p != NULL) {
//找到了id为2的节点
if (p->list->id == k) {
//我们的新节点的next指针指向2号节点的next指针原来指向的
pnewnode->next = p->next;
//2号节点的next指针指向我们的新节点
p->next = pnewnode;
cin >> pnewnode->list->id >> pnewnode->list->name;
return;
}
//没找到就继续遍历
p = p->next;
}如此一来，我们就做到了指定位置插入新的节点力，好耶ヽ(✿ﾟ▽ﾟ)ノ
总的方法如下：
//指定位置插入(id为k的后面插入新节点)
void add(int k)
{
node* pnewnode = (node*)malloc(sizeof(node));
pnewnode->next = NULL;
node* p = _head;
while (p != NULL) {
//找到了这么一个值
if (p->list->id == k) {
pnewnode->next = p->next;
p->next = pnewnode;
cin >> pnewnode->list->id >> pnewnode->list->name;
return;
}
//没找到就继续遍历
p = p->next;
}
}第三步 依次输出链表元素
我们添加了一些元素进去，现在我们想看看，我们之前都添加过什么元素，那么我们就要对链表进行依次遍历，依次输出链表里面的元素呢
首先，我们要添加一个指向_head的指针
node* p = _head;第二步，依次遍历链表
while (p != NULL) {
cout << p->list->id << ' ' << p->list->name << endl;
//p指向下一个节点
p = p->next;
}这样一来，我们就完成了链表输出操作了
注意哦，我们使用头插法和尾插法的输入输出是不同的
在我们使用头插法的时候
input
1 tom
2 mike
3 jake
output
3 jake
2 mike
1 tom在我们使用尾插法的时候
input
1 tom
2 mike
3 jake
output
1 tom
2 mike
3 jake总的输出输出法如下：
void printList()
{
node* p = _head;
while (p != NULL) {
cout << p->list->id << ' ' << p->list->name << endl;
p = p->next;
}
}第四步 删除指定的节点
欸，在一次添加节点的时候，你意识到，有一个节点你添加错误了，你不想要这个节点了，这时候，你又犯难了，我还没有学会怎么删除链表节点呢，怎么办~(￣▽￣)~*
好的，现在我们就来看看该怎么删除指定的节点吧
首先，我们还是要了解链表的特性，我们现在创立的单链表是动态链表，不是数组模拟链表，我们每插入一个新节点，就要从内存里面拿一部分空间来存储链表元素。所以，在我们不想要某个节点的时候，我们需要释放我们之前的动态内存
同理，我们还是要看我们删除的节点是什么地方的
第一种地方，头节点
假如说，你在第一次创建链表的时候第一个数据就搞错了，你想删除这部分数据，这时我们需要一个替代品来代替我们原先的数据
//p指向头节点 t作为替代品
node* p = _head, * t = NULL;我们该怎么删掉节点呢？
还记得我们是怎么创建节点的嘛，我们是改变了某一个位置的节点，比如说
_head ---> 3 ---> 1 ---> 2 ---> NULL我们想删掉1这个位置，我们就需要3这个位置的next指针指向1这个位置的next指针,那么就变成这样
-------->
_head ---> 3( 1 ---> )2 ---> NULL我们改变了3的next指针指向，让现在的链表里面去掉了1，但是1其实没有改变指向的，这时候，我们把1给释放掉就可以了
//删除头节点
//_head 是 我们要删掉的节点，指向_head的next指针 是 我们要改变指向的节点
if (_head->list->id == k) {
//t是我们要删除的节点
t = _head;
//改变头节点的上一个节点的next指针的指向
_head = _head->next;
free(t);
}
//删除一般情况
else {
while (p->next != NULL) {
//p->next 是 我们要删掉的节点，p 是 我们要改变指向的节点 也是 p->next 的上一个节点
if (p->next->list->id == k) {
//t就是我们要删除的节点了
t = p->next;
//改变p的next指针的指向
p->next = p->next->next;
//释放我们不想要的节点
free(t);
break;
}
p = p->next;
}
}如此一来，我们就可以删除任意节点的元素了
总的代码如下：
//删除节点(删除id为k的节点)
void remove(int k)
{
node* p = _head, * t = NULL;
//删除头节点
if (_head->list->id == k) {
t = _head;
_head = _head->next;
free(t);
}
else {
while (p->next != NULL) {
if (p->next->list->id == k) {
t = p->next;
p->next = p->next->next;
free(t);
break;
}
p = p->next;
}
}
}第五步 重新排序链表顺序
假如说，我们现在不满意我们现在的链表，我们想对我们的链表进行排序
我们现在的链表
_head ---> 5 ---> 3 ---> 1 ---> 2 ---> 4 ---> NULL我们想让我们的链表变成的样子
_head ---> 1 ---> 2 ---> 3 ---> 4 ---> 5 ---> NULL还记得我们学习过的冒泡排序法/选择排序法吗？(这应该是大家学for循环都会遇见的一个经典循环了(作者不会嘤嘤嘤))
主要是由两个for循环进行的，一步一步进行筛选的
我们先定义几个变量，类似于冒泡排序
node* p = _head, * t = NULL, temp;然后，我们还是要判断一下的，如果这个链表是刚创建出来的，或者说只有一个新节点的，那么就不用排了，怎么排都一样
if (_head == NULL || _head->next == NULL) return;好了，现在我们可以进行排序了，这里写的是从小到大排序的，从大到小只要换一个符号就可以了
while (p->next != NULL) {
t = p->next;
while (t != NULL) {
if (p->list->id > t->list->id) {
temp = *p;
*p = *t;
*t = temp;
temp.next = p->next;
p->next = t->next;
t->next = temp.next;
}
t = t->next;
}
p = p->next;
}在进入了if语句后，就意味着两个变量要交换了，这时候就有人有疑问了，为什么要交换next指针啊，下面我来画个图，你就明白了
//没有交换前
_head ---> 5 ---> 3 ---> 1 ---> 2 ---> 4 ---> NULL
//我们交换5和3节点,5是p，3是t
//开始
5 = 5 , 5->next = 3;
3 = 3 , 3->next = 1;
//变换一次
现在的5 = 原来的3 , 5->next = 3;
现在的3 = 原来的5 , 3->next = 1;
//变换两次
现在的5 = 原来的3 , 现在的5->next = 1;
现在的3 = 原来的5 , 现在的3->next = 原来的3;就是说，第一次变换中，5和3两个结构体只是结构体里面的值变了，但是它们的next指针的指向性没有变，所以第二次交换就是要我们把它们的next指针给改变掉，这才真正完成了交换
总的代码如下：
//链表重排序(id从小到大排序)
void rearrangement()
{
node* p = _head, * t = NULL, temp;
if (_head == NULL || _head->next == NULL) return;
else {
while (p->next != NULL) {
t = p->next;
while (t != NULL) {
if (p->list->id > t->list->id) {
temp = *p;
*p = *t;
*t = temp;
temp.next = p->next;
p->next = t->next;
t->next = temp.next;
}
t = t->next;
}
p = p->next;
}
}
}第六步 查询链表元素
现在，我们想要查询某个指定的链表元素，其实呢，就跟我们的第三步，输出链表元素是一样的
第一步，我们先创建一个指向_head的指针
node* p = _head;第二步，我们依次循环，去寻找我们想要的id
while (p != NULL) {
//找到了
if (p->list->id == k) {
cout << "YES" << endl;
return;
}
//没找到继续找
p = p->next;
}总的代码如下：
//查询链表指定元素(搜索指定id)
void search(int k)
{
node* p = _head;
while (p != NULL) {
if (p->list->id == k) {
cout << "YES" << endl;
return;
}
p = p->next;
}
}第七步 输出链表元素个数
到了这里，我们又来学习链表的一个性质了，它不像数组，可以直接算出来有多少数组元素，它需要我们依次访问链表节点来一个一个计算，只是链表在内存中的存储不同于数组导致的，链表在内存中的存储是很乱的，只能通过一个个next指针来访问链表的下一个元素
第一步，我们先创建一个指向_head的指针，初始化一个变量用来记录元素
int sum = 0;
node* p = _head;第二步，遍历链表计算总数
while (p != NULL) {
sum++;
p = p->next;
}
cout << sum << endl;总的代码如下:
//输出链表长度
void length()
{
int sum = 0;
node* p = _head;
while (p != NULL) {
sum++;
p = p->next;
}
cout << sum << endl;
}第八步 清空链表
你觉得，你写的这个链表太臭了（恼，想要把这个链表给清空，重新回到那个纯洁无暇的空链表捏，在这一步，我们将会学会把整个链表给清除了
在第四步中，我们有学到如何把链表的指定节点给删除的操作，让我们来回忆一下
_head ---> 3 ---> 1 ---> 2 ---> NULL我们在删除1这个节点的时候，我们要找到id为3的这个节点，再把3这个节点的next指针给指向2，那么我们清空链表就是把_head指向NULL就可以了，
但是，真的是这样吗？
我们现在制作的链表是动态存储数据的，也就是说，我们在清空链表的时候，我们也要把链表的元素在内存中的空间给释放掉才行，所以，我们又重新回到了链表的遍历操作，因为只有链表的遍历操作，我们才可以找到链表的下一个节点的位置，清空对应的内存
首先，我们先定义两个指针，其中一个用来指向链表的头节点
node* p = _head,* t;其次，我们就需要依次遍历释放元素了
while(p!=NULL)
{
t = p->next;
free(p);
p = t;
}我们在释放内存前，需要先用一个指针记录下来p的next指针的指向，不然的话，我们在释放掉当前的p的内存后，我们就没有办法找到p的next指针的指向了，所以，我们要一个t指针来保存，把p释放掉后，再让p = t
链表遍历完了，内存也就释放完了
总的代码如下：
//链表清除
void clear()
{
node* p = _head, *t;
while (p != NULL) {
t = p->next;
free(p);
p = t;
}
}第九步 反转链表
我们清空了原来那个臭链表后，又写了一个新的链表，但是，这次我们想玩些不一样的，怎么个不一样呢，就是，我们把我们的链表给反过来，让头节点变到尾，让尾节点变到头
假设，我们写了一个新的链表
_head ---> 3 ---> 1 ---> 2 ---> 4 ---> NULL我们现在想让链表反转
_head ---> 4 ---> 2 ---> 1 ---> 3 ---> NULL欸，这该怎么办呢？
其实，这个就跟我们的链表排序大同小异，只是这次我们不按id的大小来排罢了
我们还是先创建两个节点
node* p = _head,* t = _head;现在，我们来想，我们想让链表反转，其实就是已知原来的链表的元素，对原来的链表自身重新进行了一次头插法，一开始，我们的链表已经告诉我们我们要按照什么顺序进行头插法了
一开始，我们看看我们的链表需不需要反转，如果它本身是空链表或者说只有一个元素在里面，那就没有必要进行反转了，怎么转都是一样的，因此，我们一开始要来判断一下，我们的链表是否需要反转
//链表不需要反转
if (_head == NULL || _head->next == NULL) return;如果，我们的链表需要反转，那么，就要这么做
首先，我们要我们的3指向NULL，那么就要p的next指针先指向3,
再让p指向NULL,但是这里不是真的让p指向NULL，而是让_head的next指针指向NULL，至于为什么，等一下就知道了
p = _head->next;
_head->next = NULL;现在，我们来对链表进行遍历，欸，现在我们用p来遍历链表是有效的，但是如果刚才我们直接让p去指向NULL的话，我们就不能让p来遍历链表了，而t是我们后面用来进行保留数据的操作的，所以用t来遍历不妥
while (p != NULL) {
t = p->next;
p->next = _head;
_head = p;
p = t;
}上述代码的四行思路如下：
一开始，我们的链表长这样
_head ---> 3 ---> 1 ---> 2 ---> 4 ---> NULL在循环中的第一步结束后，我们的t现在在1的位置上，p在3的位置上，我们让p的next指针指向_head，也就是让我们的p的next指针指向了NULL，这时候，我们就把3和1转换过去了，第三步结束后，我们的_head到了现在3的位置，而p到了现在1的位置，在进入下一步循环后，第一步结束，我们的t的位置更新到原来的2的位置上了，这样一来，我们就做到了，遍历之前的链表上的每一个元素
总的代码如下：
//链表反转
void turn()
{
node* p = _head, * t = _head;
if (_head == NULL || _head->next == NULL) return;
p = _head->next;
_head->next = NULL;
while (p != NULL) {
t = p->next;
p->next = _head;
_head = p;
p = t;
}
}写在最后
好了，到目前为止，我们就掌握了单链表的基本操作了，其它的困难操作都是由这九种的基础来扩展的，同时再加上了一些算法的范畴，所以牢记掌握这九种基本操作，对于之后的链表学习有很大的帮助哦，Ciallo～(∠・ω< )⌒☆
当然，由于作者能力有限，如果读者找到了文章中的不够妥当或者生涩难懂的地方，还请告知我，我将会第一时间查询并修改我的错误之处，谢谢！(qq1594463152)
