目录
链表概念
上一次我们用顺序存储实现了线性表，这次我们用链式存储结构实现的线性表就叫链表
链表每个节点包含数据本身和下一个节点和上一个节点的地址
链表的分类
单链表 双链表
带头链表 不带头链表
循环链表等等
我们竞赛一般都用的是带头链表
双向链表的特点是比较任意的找到前驱节点
循环链表的特点是从任意节点的位置开始都能遍历完整个链表
我们的动态实现链表是用new申请节点，delete释放节点
但是这种动态形式对时间消耗很大，所以我们竞赛中实现的是静态的链表
静态单链表的实现
我们用两个足够大的数组来实现静态链表
一个是elem数组用来存储每个节点的数据域
一个是next数组用来存储每个节点的指针域
一个变量h表示头节点的位置
一个变量id表示新加入节点的位置
静态单链表的头插
我们应该先把2连上，再进行1的连接，如果我们先进行1的连接，那么第一个节点就找不到了，2无法进行
所以我们要头插的时候，先让id++ 为新节点腾位置，再把数据的值给e[id]
然后我们实现2号连接，我们把ne[id]=ne[h]
最后我们实现1号连接，ne[h]=id;
我们的时间复杂度就是O（1）
代码：
void push_front(int x)
{
e[++id] = x;
ne[id] = ne[h];
ne[h] = id;
}遍历链表：
用for循环，int i先初始化为ne[h]，i只要不等于0就继续进入循环，每次循环i都变成ne[i] 就完成了我们的遍历链表操作
代码
void Print()
{
for (int i = ne[h]; i; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl;
}测试结果
查询节点 第一种方法就是遍历链表查询，返回节点的下标
int find(int x)
{
//解法1遍历链表
for (int i = ne[h]; i; i = ne[i])
{
if (e[i] == x)
return i;
}
return 0;
}
查询节点的第二种方法，用空间替代时间，开一个mp数组，mp数组的下标就是我们链表的值，数组的值就是我们的链表节点的存储位置
相比于遍历的查询，我们mp数组的时间复杂度只是O（1），但是有两点局限性，1是数据的值不能太大，2是数据的值不能重复，不然就不知道存哪个下标了
int find(int x)
{
return mp[x];
}每次头插的时候 把新节点的存储位置更新到mp里
void push_front(int x)
{
e[++id] = x;
mp[x] = id;
ne[id] = ne[h];
ne[h] = id;
}在任意位置之后 插入节点
如果我们先连接1号路线，那我们就找不到三这个节点了，所以我们应该先连接2号路线，也就是说，我们先让id++给新节点腾出位置，然后我们连接2号路线也就是让ne[id]=ne[p]，再连接1号路线，也就是让ne[p]=id
void insert(int p, int x)
{
//在存储位置为p的节点后面插入一个新节点
id++;
e[id] = x;
mp[x] = id;
ne[id] = ne[p];
ne[p] = id;
}删除在任意位置之后的元素
如图，这种情况我们只要让1直接连接3 跳过2就行了，这时候虽然2还在我们的数组里面，但是遍历的时候不会遍历到他，也就相当于删除了这个节点了
也就是我们要删除2，就让ne[1]=ne[ne[1]]就行了，如果我们传p的话，就让ne[p]=ne[ne[p]]
当然，如果我们删除的节点是最后一个的下一个的话，就需要特殊判断一下，不然会存在bug
比如下图
我们要删除6节点的下一个节点的时候，ne[6]=ne[ne[6]]，也就是ne[6]=ne[0]，就会让我们的6节点和4节点再形成一个连接，破坏原有的结构
所以我们需要特判一下
void erase(int p)
{
if (ne[p])//当p不是最后一个元素的时候
{
mp[e[ne[p]]] = 0;//清空标记
ne[p] = ne[ne[p]];
}
}测试
我们单链表会了头插，查询存储位置，任意位置之后插入，任意位置之后删除这几个操作就够用了，其他的操作时间复杂度太高了我们基本用不到
静态单链表总代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], h, id;
int mp[N];
void Print()
{
for (int i = ne[h]; i; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl;
}
void push_front(int x)
{
e[++id] = x;
mp[x] = id;
ne[id] = ne[h];
ne[h] = id;
}
int find(int x)
{
解法1遍历链表
//for (int i = ne[h]; i; i = ne[i])
//{
// if (e[i] == x)
// return i;
//}
//return 0;
return mp[x];
}
void insert(int p, int x)
{
//在存储位置为p的节点后面插入一个新节点
id++;
e[id] = x;
mp[x] = id;
ne[id] = ne[p];
ne[p] = id;
}
void erase(int p)
{
if (ne[p])//当p不是最后一个元素的时候
{
mp[e[ne[p]]] = 0;//清空标记
ne[p] = ne[ne[p]];
}
}
int main()
{
for (int i = 1; i <= 5; i++)
{
push_front(i);
Print();
}
erase(2);
Print();
erase(3);
Print();
/*cout << find(1) << endl;
cout << find(5) << endl;
cout << find(6) << endl;*/
/*insert(3, 10);
insert(5, 100);
Print();*/
}静态双链表的实现
下面我们来介绍一下双链表的实现,双链表无非就是在单链表的基础上增加了前驱指针，我们只需要多开一个足够大的数组来存储前面的元素的存储位置就行了
静态双链表的创建
#include <iostream>
using namespace std;
const int N = 1e5+10;
int e[N], ne[N], pre[N];
int id, h;静态双链表的头插
a是哨兵位
和单链表一样，我们1号路线应该最后实现不然的话我们就找不到b这个节点了，自然也就连不上我们的链表了，我们先让id++为新节点腾出位置，然后e[id]=x 为了规范一下操作
我们首先先把新节点的pre指针和ne指针与相邻的两个节点连接
也就是ne[id]=ne[h] , pre[id] = h
接下来我们把b节点的前指针连接新节点，也就是3号路线
pre[ne[h]]=id
最后，我们修改哨兵位的ne指针，
ne[h]=id;
我们来实现一下代码
void push_front(int x)
{
id++;
e[id] = x;
//先修改新来节点的左右指针
ne[id] = ne[h];
pre[id] = h;
//再修改哨兵位下一个节点的左指针
pre[ne[h]] = id;
//最后修改哨兵位的右指针
ne[h] = id;
}测试头插
实现按值查找，我们还是用mp[N]空间代替时间
int find(int x)
{
return mp[x];
}
在插入的时候更新mp数组
在任意位置之后插入元素
如图，我们想要在p这个存储位置后面插入一个元素，和头插差不多，id++,e[id]=x我们应该先更改新节点的左右指针，也就是pre[id] = p ne[id] = ne[p]
然后更改p右边的节点的左指针
pre[ne[p]]=id
最后更改p位置的右指针
ne[p]=id
代码实现
void insert_back(int p, int x)
{
id++;
e[id] = x;
//修改新节点左右指针
ne[id] = ne[p];
pre[id] = p;
//修改p后面节点的左指针
pre[ne[p]] = id;
//修改p的右指针
ne[p] = id;
}测试
在任意位置之前插入元素
比如如图，我们要插入y这个节点，首先给节点腾出位置，然后先把新节点的左右指针连接上，然后连插入节点之前的节点的右指针，最后修改p的左指针。
代码
void insert_front(int p, int x)
{
id++;
e[id] = x;
//修改新节点的左右指针
ne[id] = p;
pre[id] = pre[p];
//修改p前节点的右指针
ne[pre[p]] = id;
//修改p存储位置的左指针
pre[p] = id;
mp[x] = id;
}测试代码
删除任意位置的元素
如图我们要删除p存储位置的节点，首先我们要让ne[pre[p]] = ne[p]
然后让 pre[ne[p]] = pre[p]
也就是让该节点的上一个节点的右指针指向该节点下一个节点，让该节点下一个节点的左指针指向该节点的上一个指针，然后mp[e[p]] = 0清空标记
循环链表
我们之前写的单链表其实就是循环链表，因为我们把最后一个节点的右指针写为0，其实就是头节点的下标
算法题练习：
1.排队顺序
第一行n是小朋友个数
第二行分别是第i个小朋友的下一个小朋友的编号，相当于我们链表的ne[N]的数组，而我们的数据域就是下标，我们只需要写一个遍历链表的代码就行了
第三行表示第一个小朋友的编号，我们遍历的起点
#include <iostream>
using namespace std;
const int N = 1e6+10;
int ne[N];
int n;
int main()
{
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> ne[i];
}
int h;
cin >> h;
for(int i = h;i;i=ne[i])
{
cout << i << " ";
}
}2.单向链表
#include <iostream>
using namespace std;
const int N = 1e5+10;
const int M = 1e6+10;
int id,h,ne[N],e[N];
int mp[M];
int main()
{
id++;
e[id] = 1;
mp[1] = id;
int q;
cin >> q;
int op,x,p;
while(q--)
{
cin >> op >> x;
p = mp[x];
if(op == 1)//插入到x后面
{
int y;
cin >> y;
id++;
e[id] = y;
ne[id] = ne[p];
ne[p] = id;
mp[y] = id;
}
else if(op == 2)
{
if(ne[p])
{
cout << e[ne[p]] << endl;
}
else cout << "0" << endl;
}
else
{
mp[e[ne[p]]] = 0;
ne[p] = ne[ne[p]];
}
}
}3.队列安排
由于这里还要求删除某个结点之前的元素，我们就按双链表来实现它，下面是我们的代码
#include <iostream>
using namespace std;
const int N = 1e5+10;
int ne[N],h,pre[N];
int st[N];
int main()
{
int n;
cin >> n;
ne[h] = 1;
pre[1] = h;
int p,op;
for(int i = 2;i<=n;i++)
{
cin >> p >> op;
if(op == 0)
{
pre[i] = pre[p];
ne[i] = p;
ne[pre[p]] = i;
pre[p] = i;
}
else
{
pre[i] = p;
ne[i] = ne[p];
pre[ne[p]] = i;
ne[p] = i;
}
}
int m;
cin >> m;
while(m--)
{
int x;
cin >> x;
if(st[x])
continue;
ne[pre[x]] = ne[x];
pre[ne[x]] = pre[x];
st[x] = true;
}
for(int i = ne[h];i;i=ne[i])
{
cout << i << " ";
}
return 0;
}4.约瑟夫问题
约瑟夫问题我们可以创建一个循环链表，然后我们写个循环一直循环到链表是空表，链表没到空表的话每次循环都找到要删除的元素并在删除前打印它
#include <iostream>
using namespace std;
const int N = 110;
int ne[N],h;
int main()
{
h= 1;
int n,m;
cin >> n >> m;
for(int i = h;i<n;i++)
{
ne[i] = i+1;
}
ne[n] = h;
int t = n;
for(int i = 1;i<=n;i++)//执行n次出圈操作
{
for(int j = 0;j<m-1;j++)//找到每次出圈的人
{
t = ne[t];
}
cout << ne[t] << " ";
ne[t] = ne[ne[t]];
}
}