current position:Home>Double linked list of data structure (array simulation) (Java)

Double linked list of data structure (array simulation) (Java)

2022-01-26 22:21:51 Everything goes with fate ~~~

	import java.util.*;

class Main {
    
    static int[] e = new int[100010];
    static int[] l = new int[100010];
    static int[] r = new int[100010];
    static int idx;
    
    static Scanner in = new Scanner(System.in);
    
    // 0: Left end point  1: Right endpoint 
    static void init(){
    
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }
    
    //  As long as the implementation , In the k The function inserted to the right of the number of inserts , Other inserts can borrow this function .
    static void insert(int k, int x) {
    
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        //  The order of the following two sentences cannot be reversed , In the revision r[k] Before , Use r[k]
        l[r[k]] = idx;
        r[k] = idx ++ ;
    }
    
    //  Delete the first k The number of inserts 
    static void delete(int k) {
    
        //  The first k The left pointer of the node to the right of the number of inserts  ->  The first k The node to the left of the number of inserts 
        l[r[k]] = l[k];
        //  The first k The right pointer of the node to the left of the number of inserts  ->  The first k The node to the right of the number of inserts 
        r[l[k]] = r[k];
    }
    
    public static void main(String[] args) {
    
        init();
        int m  = in.nextInt();

        while (m -- > 0) {
    
            String str = in.next();
            int k;
            int x;
            if (str.equals("IL")) {
    
                k = in.nextInt();
                x = in.nextInt();
                insert(l[k + 1], x);//  Different from single linked list  k + 1( because idx For the initial 2)
            } else if (str.equals("IR")) {
    
                k = in.nextInt();
                x = in.nextInt();
                insert(k + 1, x);
            } else if (str.equals("L")) {
    
                x = in.nextInt();
                insert(0, x);
            } else if (str.equals("R")) {
    
                x = in.nextInt();
                insert(l[1], x);
            } else {
    
                k = in.nextInt();
                delete(k + 1);
            }
        }
        //  Loop traversal , Output value 
        for (int i = r[0]; i != 1; i = r[i]) {
    
            System.out.print(e[i] + " ");
        }
    }
}

copyright notice
author[Everything goes with fate ~~~],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262221502116.html

Random recommended