作用:
单链表实现和操作
e[n]存value,ne[n]存next指针,-1表示尾结点
1 import java.util.*; 2 public class Main{ 3 static int head; 4 static int idx; 5 static int[] value=new int[100010]; 6 static int[] next=new int[100010]; 7 //初始化 8 public static void init(){ 9 head=-1; 10 idx=0; 11 } 12 //向头结点后面加一个树 13 public static void add_head(int x){ 14 value[idx]=x; 15 next[idx]=head; 16 head=idx; 17 idx++; 18 } 19 //在下标为k的结点后面加一个数 20 public static void add(int k,int x){ 21 value[idx]=x; 22 next[idx]=next[k]; 23 next[k]=idx; 24 idx++; 25 } 26 //删除下标为k的结点的后面的结点 27 public static void delete(int k){ 28 next[k]=next[next[k]]; 29 } 30 public static void main(String[] args){ 31 Scanner scan=new Scanner(System.in); 32 int n=scan.nextInt();init(); 33 while(n-->0){ 34 String s=scan.next(); 35 if(s.equals("H")){ 36 int x=scan.nextInt(); 37 add_head(x); 38 } 39 else if(s.equals("D")){ 40 int k=scan.nextInt(); 41 if(k==0){ 42 head=next[head]; 43 } 44 else{ 45 delete(k-1); 46 } 47 } 48 else{ 49 int k=scan.nextInt(); 50 int x=scan.nextInt(); 51 add(k-1,x); 52 } 53 } 54 for(int i=head;i!=-1;i=next[i]){ 55 System.out.print(value[i]+" "); 56 } 57 } 58 }
1 import java.util.*; 2 public class Main{ 3 static int[] value=new int[100010]; 4 static int[] l=new int[100010]; 5 static int[] r=new int[100010]; 6 static int idx; 7 //初始化 8 public static void init(){ 9 r[0]=1; 10 l[1]=0; 11 idx=2; 12 } 13 //在第k个数右边插入一个数 14 public static void add(int k,int x){ 15 value[idx]=x; 16 r[idx]=r[k]; 17 l[idx]=k; 18 l[r[k]]=idx; 19 r[k]=idx; 20 idx++; 21 } 22 //在第k个数左边插入一个数就是在第k个数左边的数的右边插入一个数 23 //删除下标为k的数 24 public static void delete(int k){ 25 r[l[k]]=r[k]; 26 l[r[k]]=l[k]; 27 } 28 public static void main(String[] args){ 29 Scanner scan=new Scanner(System.in); 30 int m=scan.nextInt(); 31 init(); 32 while(m-->0){ 33 String s=scan.next(); 34 if(s.equals("L")){ 35 int x=scan.nextInt(); 36 add(0,x); 37 } 38 else if(s.equals("R")){ 39 int x=scan.nextInt(); 40 add(l[1],x); 41 } 42 else if(s.equals("D")){ 43 int k=scan.nextInt(); 44 delete(k+1); 45 } 46 else if(s.equals("IL")){ 47 int k=scan.nextInt(); 48 int x=scan.nextInt(); 49 add(l[k+1],x); 50 } 51 else { 52 int k=scan.nextInt(); 53 int x=scan.nextInt(); 54 add(k+1,x); 55 } 56 } 57 for(int i=r[0];i!=1;i=r[i]){ 58 System.out.print(value[i]+" "); 59 } 60 } 61 }