双链表

双链表和单链表的区别：双链表是左右都有的

l[N], r[N]

再双链表中，我们用0表示头节点，1，表示尾点

双链表的几个基本操作：

插入一个点，左插入，有插入

模板

int e[N], l[N], r[N], idx;
void init(){
    //0 表示左端点， 1表示右端点
    r[0] = 1;
    l[1] = 0;
}

//一样，下边k  右边插入
void add(int k, int val){
    e[idx] = val;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    
    idx++;
}

//左边插入
add(l[k],x);

//删除
//删除第k个点
void remove(int k) {
    //就是要跳过k这个点
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

题目

AcWing

827 双链表

827

描述

实现一个双链表，双链表初始为空，支持5种操作：

(1) 在最左侧插入一个数；

(2) 在最右侧插入一个数；

(3) 将第k个插入的数删除；

(4) 在第k个插入的数左侧插入一个数；

(5) 在第k个插入的数右侧插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

解答

import java.util.*;
import java.io.*;

public class Main {
		private static int N = 100010;//数据十万
		
		private static int[] e = new int[N];
		private static int[] l = new int[N];
		private static int[] r = new int[N];
		static int idx;
		//初始化
		private static void init(){
		    //0表示左端点，1表示右端点
		    r[0] = 1;
		    l[1] = 0;
			idx = 2;
		}
		
		private static void add(int k, int x) {
			e[idx] = x;
			r[idx] = r[k];
			l[idx] = k;
			l[r[k]] = idx;
			r[k] = idx;
			idx++;
		}
		
		//将下标是k的点后面的那个节点删除
		private static void remove(int k){
			r[l[k]] = r[k];
			l[r[k]] = l[k];
		}
    
    	public static void main(String[] args) throws IOException {
 			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			//m操作数
			int m = Integer.parseInt(br.readLine());
			init();       
            while(m-- > 0){
                String[] line = br.readLine().split(" ");
				String op = line[0];
                
                if(op.equals("L")) {
                	//最左端插入  左端点的下标就是0
					int x = Integer.parseInt(line[1]);
					add(0,x);
                }else if(op.equals("R")) {
					int x = Integer.parseInt(line[1]);
					//R x”，表示在链表的最右端插入数x。
					add(l[1],x);
                }else if(op.equals("D")) {
					//表示将第k个插入的数删除。
					//第一个插入的是下标是2 第二个插入的是3
					int k=Integer.parseInt(line[1]);
	                remove(k+1);
                }else if(op.equals("IL")) {
					//表示在第k个插入的数左侧插入一个数
					int k = Integer.parseInt(line[1]);
					int x = Integer.parseInt(line[2]);
					add(l[k+1], x);
                }else{
					int k = Integer.parseInt(line[1]);
					int x = Integer.parseInt(line[2]);
					add(k+1, x);
                }
            }
            
            for(int i=r[0];i!=1;i=r[i]) {
				System.out.print(e[i]+" ");
			}
      
        }
}