双链表和单链表原理是一样的,只不过双链表有俩个指针,一个指向前,一个指向后。(具体单链表可以看这里单链表)
int l[N]
存放每个点左边的点
是谁,r[N]
存放每个点右边的点
是谁head = 0
, tail = 1
。c此时头和尾都被占用了,idx从2
开始题目
实现一个双链表,双链表初始为空,支持 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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
输出样例:
8 7 7 3 2 9
- 1
代码
#include<iostream> #include<string> using namespace std; const int N = 100010; int l[N], r[N], idx, e[N]; /*用结构体也可以只不过非常的长 struct Node { int e, l , r; }nodes[N]; */ void init() //初始化 { r[0] = 1; //0的右端点指向1; 0代表头 l[1] = 0; //1的左端点指向0; 1代表尾 idx = 2; } void insert_right(int k, int x) //在下标是K的点的右侧插入 { e[idx] = x; r[idx] = r[k]; l[idx] = k; l[r[k]] = idx; r[k] = idx; idx ++; } void insert_left(int k, int x) //在下标是K的点的左侧插入 { e[idx] = x; r[idx] = k; l[idx] = l[k]; r[l[k]] = idx; l[k] = idx; idx ++; //还有 一种简便写法,直接调用insert_right(l[k], x); 在k的左边插入一个点,实际上就是在l[k]的右边插入一个点 } void remove(int k) //删除 { r[l[k]]= r[k]; l[r[k]] = l[k]; //nodes[nodes[k].l].r = nodes[k].r; } int main() { init(); int m; cin >> m; while (m --) { int x, k; string op; cin >> op; if (op == "L") { cin >> x; insert_right(0, x); } else if (op == "R") { cin >> x; insert_left(1, x); } else if (op == "D") { cin >> k; remove(k + 1); } else if(op =="IL") { cin >> k >> x; insert_left(k + 1, x); } else { cin >> k >> x; insert_right(k + 1 , x); } } for(int i = r[0]; i != 1; i = r[i] ) cout << e[i] <<" "; cout << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92