双链表

关于双链表的增和删

模拟删除

//删除第k位的数据
void remove(int k){
    l[r[k]] = l[k]; //把黑的指针都给替换即可
	r[l[k]] = r[k];
}

模拟双链表增加

//向第k位的右边插入数据
void insert(int k,int x){
	e[idx] = x;
	r[idx] = r[k];//把当前数据的右指针指向右边
	l[idx] = k;//当前数据的左指针指向左边
	l[r[k]] = idx; //最后一个的左指针指向当前数据
	r[k] = idx++;//k位的右指针指向当前数据即可
}

---

总结

了解其指针替换即可，并不难，慢慢把代码记住就行。

记住模板即可

代码题目如下：实现一个双链表，双链表初始为空，支持 55 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 kk 个插入的数删除；
4. 在第 kk 个插入的数左侧插入一个数；
5. 在第 kk 个插入的数右侧插入一个数

现在要对该链表进行 MM 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 kk 个插入的数并不是指当前链表的第 kk 个数。例如操作过程中一共插入了 nn 个数，则按照插入的时间顺序，这 nn 个数依次为：第 11 个插入的数，第 22 个插入的数，…第 nn 个插入的数。

输入格式

第一行包含整数 MM，表示操作次数。

接下来 MM 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 xx。
2. R x，表示在链表的最右端插入数 xx。
3. D k，表示将第 kk 个插入的数删除。
4. IL k x，表示在第 kk 个插入的数左侧插入一个数。
5. IR k x，表示在第 kk 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

1≤M≤1000001≤M≤100000
所有操作保证合法。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int r[N],l[N],e[N],idx;
int head;

//向第k位的右边插入数据
void insert(int k,int x){
	e[idx] = x;
	r[idx] = r[k];
	l[idx] = k;
	l[r[k]] = idx;
	r[k] = idx++;
}
//删除第k位的数据
void remove(int k){
    l[r[k]] = l[k];
	r[l[k]] = r[k];
}
int main(){
	int m;
	cin>>m;
	l[1] = 0 ,r[0] =1;
	idx = 2;
	while(m--){
		string ch;
		cin>>ch;
		int k,x;
		if(ch == "L"){
			cin>>x;
			insert(0,x);
		} else if(ch == "R"){
			cin>>x;
			insert(l[1],x);
		}
		else if(ch == "D"){
			cin>>k;
			remove(k+1);
		}
		else if(ch == "IL"){
			cin>>k>>x;
			insert(l[k+1],x);
		}
		else  {
			cin>>k>>x;
			insert(k+1, x);
		}
	}
	for(int i = r[0]; i != 1; i = r[i])cout<<e[i]<<" ";
	return 0;
}