707. 设计链表

目的

用数组模拟单链表

问题描述

AcWing 826. 单链表
实现一个单链表，链表初始为空，支持三种操作：

  1. 向链表头插入一个数；
  2. 删除第 k 个插入的数后面的数；
  3. 在第 k 个插入的数后插入一个数。

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

  1. H x，表示向链表头插入一个数 x。
  2. D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
  3. I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

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

  1. 10
  2. H 9
  3. I 1 1
  4. D 1
  5. D 0
  6. H 6
  7. I 3 6
  8. I 4 5
  9. I 4 5
  10. I 3 4
  11. D 6

输出样例：

  1. 6 4 6 5

方法

  1. 开辟合适大小的值数组 e[n] 和指针数组 ne[n]
  2. 将下标为0的数组元素作为链表的头节点
  3. -1 表示空指针，ne[0] = -1 ， e[0]不用。
  4. 第一个可用节点的下标为idx，初始化 idx = 1

代码

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static int N = 100010;
  6.     public static void main(String[] sss) throws IOException{
  7.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  10.         int m = Integer.parseInt(br.readLine());
  11.         int[] e = new int[N];
  12.         int[] ne = new int[N];
  13.         int idx = 1;
  14.         ne[0] = -1;
  16.         while (m-- > 0) {
  17.             String[] str = br.readLine().split(" ");
  18.             int x = 0, k = 0;
  20.             switch (str[0]) {
  21.                 case "H":
  22.                     x = Integer.parseInt(str[1]);
  23.                     e[idx] = x;
  24.                     ne[idx] = ne[0];
  25.                     ne[0] = idx++;
  26.                     break;
  27.                 case "I":
  28.                     k = Integer.parseInt(str[1]);
  29.                     x = Integer.parseInt(str[2]);
  30.                     e[idx] = x;
  31.                     ne[idx] = ne[k];
  32.                     ne[k] = idx++;
  33.                     break;
  34.                 case "D":
  35.                     k = Integer.parseInt(str[1]);
  36.                     if (ne[k] == -1) break;
  37.                     ne[k] = ne[ne[k]];
  38.                     break;
  39.                 default:
  40.             }
  41.         }
  43.         for (int i = ne[0]; i != -1; i = ne[i]) {
  44.             bw.write(e[i] + " ");
  45.         }
  47.         br.close();
  48.         bw.close();
  50.     }
  51. }

注意

因为是用数组实现的链表，当链表中的某个节点被删除时相当于数组的某个位置被闲置，这不要紧，算法题因为时间有限，不会考虑闲置空间的回收问题。
但是工程上来说是一定得回收的。如果考虑的话也很好实现，在释放节点时将该节点加入备用链表即可。
具体做法可以是这样：

  1. //删除k节点
  2. delete(k);
  3. //加入k到备用链表
  4. ne[idx] = k;
  5. ne[k] = ne[idx] == 0 ? idx + 1 : ne[idx]

[

](https://www.acwing.com/activity/content/problem/content/863/1/)