2.1 链表
2.1.1 单链表
概念：
- 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
- 链表由一系列结点组成，每个结点中分为存储数据元素的数据域和存储下一个结点的指针域
操作思想
- 插入：新建一个结点，改变前一个结点的指针指向新建的结点
- 删除：将删除结点的前一个结点的指针指向该节点的后一个结点的指针
模板
/* 可使用数组、结构体等模拟链表，malloc和new模拟动态链表较慢，而结构体模拟代码繁琐，故采用静态数组模拟链表 */
const int N=1e6+10; //根据需要开辟链表大小
int e[N],ne[N],head=-1,idx=0; //e[N]存储值，ne[N]存储下一个结点，初始化head头结点，idx用于计数
void head_add(int x){ //在头部插入x
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void add(int k,int x){ //在下标k后面插入x
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k){ //删除下标k后面的结点
ne[k]=ne[ne[k]];
}
例题 826.单链表
描述
实现一个单链表，链表初始为空，支持三种操作：
1.向链表头插入一个数；
2.删除第 k 个插入的数后面的数；
3.在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
输出样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N],ne[N],head=-1,idx=0;
void head——add(int x){ //在头部插入x
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void add(int k,int x){ //在第k个数后面插入x
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k){ //删除第k个数后面的结点
ne[k]=ne[ne[k]];
}
int main(){
int m;
cin>>m; //读入操作次数
while(m--){
string s;
cin>>s; //读入操作
if(s=="H"){ //头部插入
int x;
cin>>x;
head_add(x);
}
else if(s=="D"){ //删除操作
int k;
cin>>k;
if(k==0){
head=ne[head];
}
else{
remove(k-1); //idx从0开始，下标为k-1
}
}
else if(s=="I"){ //插入操作
int k,x;
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i]){ //遍历输出
cout<<e[i]<<" ";
}
return 0;
}
2.1.2 双链表
概念：
- 在单链表的基础上，取消头结点，换为左端点和右端点，每个结点的指针域存储其左边结点的指针和右边结点的指针
操作思想
- 插入：思想同单链表，新建结点后，依次更改左右结点的左右指针的指向
- 删除：思想同单链表，将删除结点的左右结点的左右指针改向，跳过该节点
模板
const int N=1e6+10; //根据需要开辟链表大小
int e[N],r[N],l[N],idx; //e[N]存储值，r[N]存储右结点，l[N]存储左结点，idx用于计数
void init(){ //初始化链表
r[0]=1; //初始化左端点右边为右端点
l[1]=0; //初始化右端点左边为左端点
idx=2; //已经用掉了左端点和右端点，下标从2开始
}
void add(int k,int x){ //在下标k右边插入x
e[idx]=x; //存储新结点的值
l[idx]=k; //新结点的左边指针为k
r[idx]=r[k]; //新结点的右边指针为左结点的右指针r[k]
l[r[k]]=idx; //修改新结点右边结点的左指针为新结点下标idx
r[k]=idx++; //修改新结点左边结点的右指针为新结点下标idx
}
//调用时，若在第k个数的右边插入x则为 add(k+1,x) idx从2开始，故为k+1
//调用时，若在第k个数的左边插入x则为 add(l[k+1],x) 相当于在k左边的点的右边插入x
void remove(int k){ //删除下标为k的点
r[l[k]]=r[k];
l[r[k]]=l[k];
}
例题 827. 双链表
描述
实现一个双链表，双链表初始为空，支持 5 种操作：
1.在最左侧插入一个数；
2.在最右侧插入一个数；
3.将第 k 个插入的数删除；
4.在第 k 个插入的数左侧插入一个数；
5.在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
1.L x，表示在链表的最左端插入数 x。
2.R x，表示在链表的最右端插入数 x。
3.D k，表示将第 k 个插入的数删除。
4.IL k x，表示在第 k 个插入的数左侧插入一个数。
5.IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
输出样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N],r[N],l[N],idx=2;
void add(int k,int x){
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx++;
}
void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
r[0]=1,l[1]=0; //初始化链表
int m;
cin>>m; //读入操作次数
while(m--){
string s;
cin>>s; //读入操作
if(s=="L"){ //最左端插入x
int x;
cin>>x;
add(0,x); //最左端的端点下标为0
}
else if(s=="R"){ //最右端插入x
int x;
cin>>x;
add(l[1],x); //最右端的端点下标为下标为1的左边，即l[1]
}
else if(s=="D"){ //删除操作
int k;
cin>>k;
remove(k+1); //idx从2开始，下标为k+1
}
else if(s=="IL"){ //在第k个数左边插入x
int k,x;
cin>>k>>x;
add(l[k+1],x); //即在第k个数左边的数的右边插入x
}
else if(s=="IR"){ //在第k个数右边插入x
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){ //遍历输出
cout<<e[i]<<" ";
}
return 0;
}
