单链表，双链表¶
单链表¶
单链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m;
int hh, e[N], ne[N], idx;
void add_to_head(int x){
e[idx] = x, ne[idx] = hh, hh = idx++;
}
void add_to_node(int k, int x){
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
hh = -1;
cin >> m;
while (m--){
string op;
cin >> op;
if (op[0] == 'H'){
int x;
cin >> x;
add_to_head(x);
}
else if (op[0] == 'D'){
int k;
cin >> k;
if (k == 0) hh = ne[hh]; //如何删除的是头结点
else remove(k - 1);
}
else{
int k, x;
cin >> k >> x;
add_to_node(k - 1, x);
}
}
for (int i = hh; i != -1; i = ne[i]) printf("%d ", e[i]);
puts("");
return 0;
}
双链表¶
双链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N], L[N], R[N], idx;
// k -> idx -> R[k]
void insert(int k, int x){
e[idx] = x;
R[idx] = R[k]; // 先把idx挂好
L[idx] = k;
L[R[k]] = idx; // 然后弄原来的结点
R[k] = idx++;
}
void remove(int k){
L[R[k]] = L[k];
R[L[k]] = R[k];
}
int main(){
// r[0] 指向第一个点，0 1两个点作为两端，r[0] = 1, l[1] = 0 模拟成环
// 用0, 1表示左端点、右端点，第一个数从idx = 2开始
R[0] = 1, L[1] = 0, idx = 2;
cin >> m;
while (m--){
string op;
cin >> op;
if (op == "L"){
int x;
cin >> x;
insert(0, x);
}
if (op == "R"){
int x;
cin >> x;
insert(L[1], x);
}
if (op == "D"){
int k;
cin >> k;
remove(k+1);
}
if (op == "IL"){
int k, x;
cin >> k >> x;
insert(L[k+1], x); // 2-index
}
if (op == "IR"){
int k, x;
cin >> k >> x;
insert(k+1, x);
}
}
for (int i = R[0]; i != 1; i = R[i]) printf("%d ", e[i]);
puts("");
return 0;
}