目的

用数组模拟双向链表

问题描述

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

  1. 在最左侧插入一个数；
  2. 在最右侧插入一个数；
  3. 将第 k 个插入的数删除；
  4. 在第 k 个插入的数左侧插入一个数；
  5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

  1. L x，表示在链表的最左端插入数 x。
  2. R x，表示在链表的最右端插入数 x。
  3. D k，表示将第 k个插入的数删除。
  4. IL k x，表示在第 k个插入的数左侧插入一个数。
  5. IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：

  1. 10
  2. R 7
  3. D 1
  4. L 3
  5. IL 2 10
  6. D 3
  7. IL 2 7
  8. L 8
  9. R 9
  10. IL 4 7
  11. IR 2 2

输出样例：

  1. 8 7 7 3 2 9

思路：

  • 开辟合适大小的值数组 e[n] ，左指针数组 l[n] ，右指针数组 r[n]
  • 将下标为0的数组元素作为链表的头节点，将下标为 1 的数组元素作为链表的尾结点

  • -1 表示空指针, e[0], e[1]不用。

    1. static int N = 100010; //视具体问题而定N
    2. //初始化
    3. int[] e = new int[N];
    4. int[] l = new int[N], r = new int[N];    // 头尾相互指一下
    5. l[0] = -1;
    6. r[0] = 1;
    7. l[1] = 0;
    8. r[1] = -1;

  • 第一个可用节点的下标为idx，初始化 idx = 2

  1. import java.util.*;
  3. public class Main {
  4.     static int[] e, l, r;
  5.     static int idx;
  6.     static {
  7.         e = new int[100010];
  8.         l = new int[100010];
  9.         r = new int[100010];
  10.         //idx = 2,因为0和1被分别用于头尾节点
  11.         idx = 2;
  12.         r[0] = 1;
  13.         l[0] = -1;
  14.         r[1] = -1;
  15.         l[1] = 0;
  16.     }
  18.     //在指针为k的节点后插入值为x的新节点
  19.     static void add(int k, int x) {
  20.         e[idx] = x;
  21.         r[idx] = r[k];
  22.         l[idx] = k;
  23.         l[r[k]] = idx;
  24.         r[k] = idx;
  25.         idx++;
  26.     }
  27.     //删除指针为k的节点
  28.     static void delete(int k) {
  29.         r[l[k]] = r[k];
  30.         l[r[k]] = l[k];
  31.     }
  34.     public static void main(String[] sss) {
  35.         Scanner sc = new Scanner(System.in);
  37.         int m = sc.nextInt();
  38.         while (m-- > 0) {
  39.             String op = sc.next();
  40.             int k, x;
  42.             switch (op) {
  43.                 case "L":
  44.                     x = sc.nextInt();
  45.                     add(0, x);
  46.                     break;
  47.                 case "R":
  48.                     x = sc.nextInt();
  49.                     add(l[1], x);
  50.                     break;
  51.                 case "D":
  52.                     k = sc.nextInt();
  53.                     delete(k + 1);
  54.                     break;
  55.                 case "IL":
  56.                     k = sc.nextInt();
  57.                     x = sc.nextInt();
  58.                     add(l[k+1], x);
  59.                     break;
  60.                 case "IR":
  61.                     k = sc.nextInt();
  62.                     x = sc.nextInt();
  63.                     add(k + 1, x);
  64.                     break;
  65.             }
  66.         }
  68.         for (int i = r[0]; i != 1; i = r[i]) {
  69.             System.out.print(e[i] + " ");
  70.         }
  72.     }
  73. }