java模板
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点的索引
//head = 0,tail = 1;l[]相当于向左走一步,r[]相当于向右走一步
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点k的右边插入一个数x
void insert(int k, int x)
{
e[idx] = x; //赋值
l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx ++ ;
}
//在节点k的左边插入一个数x
insert(l[k],x)
// 删除节点k
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
//在链表的最左端插入值x
insert(0,x);
//在链表的最右端插入值x
insert(l[1],x);
java代码
import java.util.Scanner;
public class Main{
private static int N = 100010;
private static int idx;
private static int[] e = new int[N];
private static int[] l = new int[N];
private static int[] r = new int[N];
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int m = in.nextInt();
init();
while(m-- > 0){
String a = in.next();
if(a.equals("L")){
int x = in.nextInt();
insert_k(0,x);
}else if(a.equals("R")){
int x = in.nextInt();
insert_k(l[1],x);
}else if(a.equals("D")){
int k = in.nextInt();
remove_k(k+1); //因为初始化了两个值,所以第k个数的下标是 k+2-1 = k+1
}else if(a.equals("IL")){
int k = in.nextInt();
int x = in.nextInt();
insert_k(l[k+1],x);
}else if(a.equals("IR")){
int k = in.nextInt();
int x = in.nextInt();
insert_k(k+1,x);
}
}
for(int i = 0; r[i] != 1; i = r[i]) System.out.print(e[r[i]] + " ");
}
private static void init(){ //初始化
int head = 0,tail = 1;
r[0] = 1; //1
l[1] = 0; //00
idx = 2;
}
private static void insert_k(int k, int x){ //移除第k个数右边的数
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx; //这步要最后做
idx++;
}
private static void remove_k(int k){ //删除k右边的数
r[l[k]] = r[k];
l[r[k]] = l[k];
}
}