不好意思，好久没更新了
链表
目录：
链表介绍
STL中的链表
单向链表
双向链表
链表介绍
链表是一种线性数据结构（一对一），他的内存是随机分布的，所以不能像数组一样，直接用下标访问。需要用指针访问。
使用链表时注意：在操作时千万不要丢失数据！！！
链表中的每个节点（元素）分为，数据域和指针域，大概图片：
大概就是说，头不存东西，只是指向p节点，p节点存了一个小东西，同时指向tail节点，tail节点可以存东西，但是指向一个空节点。
优点：占用空间随机，节省空间。（刚刚说了）
优点：删除元素和插入元素较快，解释：
删除（p节点）：只要让头节点的指针指向尾节点，就完成了。但是数组就要先删掉，然后让后面每个元素向前挪一个，才能实现真正意义上的删除（有些可以在输出时不输出，直接跳过，作为假删除）。明显链表更优
插入（s节点）在p节点和head节点中间：先让s的next*指向原来head的next*，再把head的next*指向s也就好了。但是数组要让后面的所有元素每一个都向后移一位，才能把s插进来。链表更优
缺点：想要快速找一个元素就不能像数组一样，直接用下标。（但是如果告诉你一个元素，你要告诉他在哪，那就是一样的）如果告诉你找第i个元素，就要从头开始，沿着指针慢慢找。
STL中的链表
为什么说这是STL容器总结的后续呢？
因为链表在STL容器中有一个独立的结构，也就是
list<typename> ls
其函数与众多STL容器相似，如加入元素用 ls.push(),删除元素用ls.pop()但是具体也不知道怎么用，到时候再出一篇，专门讲c++中内置STL中的链表。本篇主要用手写来解释
单向链表
平常用的较多的链表主要分为单向链表和双向链表，还有循环链表……
先讲单向链表。
上面的图就是单向链表。
意思是，只能向后指，不能向前指。自然就无法从后往前遍历链表了。
实现基本的很简单。拓展一个知识点，结构体类型指针
正常来说，我们定义一个变量是这么写的
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a=3; //定义变量
int *a1;//一个指针，但是他不指向任何变量
int *a2=&a; //指针类型要和变量一样，且要是一个实质性的变量
//现在访问变量a有两种方法，直接访问和用指针。
cout<<a<<' '<<*a2;//直接输出变量，或者用刚刚的指针。
return 0;
}
但是一个单向链表中，每个结点的定义应该是这样的：
struct node
{
int data; //数据
node *next; //指针，指向下一个节点
};
所以要开一个新的节点怎么办？
直接新建一个node类型的节点p
struct node
{
int data;
node *next;
};
int main()
{
node *p=new node; //一个新的没有名字的节点，我们用指针p指向它
}
学会这个就可以完成第一个操作：在末尾加入链表
流程：先让原来的末尾指向他，再把它变成尾巴。
大概代码：
struct node
{
int data;
node *next;
};
int main()
{
node *p;
p=new node; //一个新的没有名字的节点，我们用指针p指向它
cin>>p->data; //由于是个链表要用->访问链表里的每个元素，而不是和普通结构体一样用.
p->next=NULL; //把他的下一个指向空，初始化指针域
tail->next=p; //原来尾巴的下一个指向它，由于是末尾加入。
tail=p; //尾巴变成现在这个节点
}
插入：
从末尾加入可以说是新的节点。但是我想在中间插入一个怎么办？
假设新节点是s，要插在p的后面。
只要让s的指针指向p的下一个，p的下一个再指向s。过程不能反过来！
代码实现（定义同上）：
s->next=p->next; //让s的指针指向p的下一个
p->next=s; //p的下一个再指向s。
删除，链表中最简单的东西。
假设删除s节点，只要让原来s前面的节点指向s的一个。这是把s舍弃了，并不是说s在内存中消失了，但是也无法挽回s。
代码实现：
p->next=p->next->next;//p的下一个变成p的下一个（s）的下一个，等价于p->next=s->next
输出与查找
输出只需要当前节点不是NULL就可以输出数据域，然后再去访问当前节点所指向的节点
代码实现：
while(p!=NULL)
{
cout<<p->data<<' ';//用空格隔开，输出p的数据
p=p->next;//p节点向下寻找
}
查找就是说如果当前元素与目标不符，且指针指向的位置不为空，搜索下一个节点。
代码实现：
while(p->data!=num and p->next != NULL) //p的数据与目标不符，且下一个节点不为空
{
p=p->next; //搜索下一个
}
cout<<p->data; //或cout<<p->id; id是一个新建的数据域，用于记录下标，其实变成了数组，在增或删是不方便
单项指针就没了，建议去把luogu链表模板题AC后，再阅读接下来的双向链表。提前预告：下一篇会单独出一个循环队列，预计暑假内出完树，图