一、单链表：
1.算法模板：
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } // 在链表头插入一个数a void insert(int a) { e[idx] = a; ne[idx] = head; head = idx ++ ; } // 将头结点删除，需要保证头结点存在 void remove() { head = ne[head]; }
2.思路：
A.初始化
int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; }
B.*在链表头插入一个数a
void insert(int a) { e[idx] = a; ne[idx] = head; head = idx ++ ; }
C.就先把值赋到数据域，然后让head的地址值存入指针域，让idx向下移一位；
向表中k位置插图x
void add(int k,int x) { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; }
D.将k删除，需要保证头结点存在
void remove(int k) { ne[k]=ne[ne[k]]; }
3.例题:
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的数；
- 在第 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<iostream> using namespace std; const int N=100010; //对链表进行初始化 int head,e[N],ne[N],idx; void init() { head=-1;//最开始的时候，链表的头节点要指向-1， //为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束 //当它在初始化的时候指向-1，来表示链表里没有内容。 idx=0; //idx在我看来扮演两个角色，第一个是在一开始的时候，作为链表的下标，让我们好找 //第二在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下 //标来帮助操作。并且是在每一次插入操作的时候，给插入元素一个下标，给他一个窝，感动！ /* 虽然我们在进行各种操作的时候，元素所在的下标看上去很乱，但是当我们访问的 时候，是靠着指针，也就是靠ne[]来访问的，这样下标乱，也就我们要做的事不相关了。 另外，我们遍历链表的时候也是这样，靠的是ne[] */ } //将x插入到头节点上 void insert(int a)//和链表中间插入的区别就在于它有head头节点 { e[idx]=a;//第一步，先将值放进去 ne[idx]=head;//head作为一个指针指向空节点，现在ne[idx] = head;坐这把交椅的人换了 //现在只是做到了第一步，将元素x的指针指向了head原本指向的 head=idx++;//head现在表示指向第一个元素了，它不在是空指针了。 //指针向下移一位，为下一次插入元素做准备。 } //将x插入到下标为k的点的后面 void add(int k,int x) { e[idx]=x;//先将元素插进去 ne[idx]=ne[k];//让元素x配套的指针，指向它要占位的元素的下一个位置 ne[k]=idx++;//让原来元素的指针指向自己，//将idx向后挪 } //将下标是k的点后面的点个删掉 void remove(int k) { ne[k]=ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。 } int main() { init();//初始化 int n; cin>>n; while(n--) { char op; cin>>op; int k,x; if(op=='H') { cin>>x; insert(x); } else if(op=='D') { cin>>k; if(k==0) head=ne[head];//删除头节点 else remove(k-1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1 } else { cin>>k>>x; add(k-1,x);//同样的，第k个数，和下标不同，所以要减1 } } for(int i=head;i!=-1;i=ne[i])cout<<e[i]<<" "; return 0; }
二、双链表：
- 算法模板：
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点 int e[N], l[N], r[N], idx; // 初始化 void init() { //0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; } // 在节点a的右边插入一个数x void insert(int k, int x) { e[idx] = x; r[idx] = r[k],l[idx] = k; l[r[k]] = idx, r[k] = idx ++ ; } // 删除节点a void remove(int k) { l[r[k]] = l[k]; r[l[k]] = r[k]; }
2.思路：
A.初始化：
void init() { //0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; }
B.在k节点右面插入一个数
void insert(int k, int x) { e[idx] = x; r[idx] = r[k],l[idx] = k; l[r[k]] = idx, r[k] = idx ++ ; }
C.删除第k个点
void remove(int k) { l[r[k]] = l[k]; r[l[k]] = r[k]; }
3.例题：
实现一个双链表，双链表初始为空，支持 5 种操作：
- 在最左侧插入一个数；
- 在最右侧插入一个数；
- 将第 k个插入的数删除；
- 在第 k 个插入的数左侧插入一个数；
- 在第 k个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
- L x，表示在链表的最左端插入数 x。
- R x，表示在链表的最右端插入数 x。
- D k，表示将第 k 个插入的数删除。
- IL k x，表示在第 k 个插入的数左侧插入一个数。
- 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<iostream> using namespace std; const int N=100010; int e[N],l[N],r[N],idx; //! 初始化 void init() { r[0]=1,l[1]=0;//* 初始化 第一个点的右边是 1 第二个点的左边是 0 idx=2;//! idx 此时已经用掉两个点了 } //* 在第 K 个点右边插入一个 X void add(int k,int x) { e[idx]=x; r[idx]=r[k];//这边的 k 不加 1 ， 输入的时候 k+1 就好 l[idx]=k; l[r[k]]=idx; r[k]=idx++; }//!当然在K的左边插入一个数 可以再写一个,也可以直接调用我们这个函数， //在 k 的左边插入一个数等价于在l[k] 的右边插入一个数 add(l[k],x) //*删除第 k个 点 void remove(int k) { l[r[k]]=l[k]; r[l[k]]=r[k]; } int main() { init(); int n; cin>>n; while(n--) { int k,x; string op; cin>>op; if(op=="R") { cin>>x; add(l[1],x); //0和1只是代表头和尾所以最右边插入只要在指向1的那个点的右边插入就可以了 } else if(op=="L") { cin>>x; add(0,x); //最左边插入就是在指向0的数的左边插入就可以也就是可以直接在0的有右边插入 } else if(op=="D") { cin>>k; remove(k+1); } else if(op=="IL") { cin>>k>>x; add(l[k+1],x); } else { cin>>k>>x; add(k+1,x); } } for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<" "; return 0; }
