AcWing 826. 数组实现单链表【带含义解释】
原题链接
简单
作者:
ACSaber
,
2020-11-27 09:20:43
,
所有人可见
,
阅读 264
import java.util.*;
import java.io.*;
class Main {
private static int N = 100010;
private static int head; // head 节点下标
private static int[] e; // 存储每个节点的值
private static int[] ne; // 存储每个节点的 next 指针下标是都是;可以初始化时将全部值设为 -1
private static int idx; // 当前可以用来存储的下标
// 链表:10 -> 20 -> 30 -> 40
// 那么对应就是:
// head = 1(当前 head 的下标为 1)、idx = 5(下一个存储的下标位置为)
// 可以从 idx = 1 开始存储:e[1] = 10、e[2] = 20、e[3] = 30、e[4] = 40
// ne[1] = 2、ne[2] = 3、ne[3] = 4、
// 实际链表和数组下标不一定是对应的,因为中间可能经历了一下删除,所以也可能是:
// 那么对应就是:
// head = 10(当前 head 的下标为 10)、idx = 29(下一个存储的下标位置为)
// 可以从 idx = 1 开始存储:e[10] = 10、e[11] = 20、e[27] = 30、e[28] = 40
// ne[10] = 11、ne[11] = 27、ne[27] = 28、
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
init();
int m = Integer.parseInt(reader.readLine());
for (int i = 0; i < m; i++) {
String[] s = reader.readLine().split(" ");
if (s[0].equals("H")) {
add(Integer.parseInt(s[1]));
} else if (s[0].equals("D")) {
delete(Integer.parseInt(s[1]));
} else if (s[0].equals("I")) {
insert(Integer.parseInt(s[1]), Integer.parseInt(s[2]));
}
}
int tmp = head;
while (tmp != -1) {
writer.write(e[tmp] + " ");
tmp = ne[tmp];
}
writer.flush();
writer.close();
reader.close();
}
private static void init() {
head = -1;
e = new int[N];
ne = new int[N];
idx = 1;
Arrays.fill(ne, -1);
}
private static void add(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
private static void delete(int k) {
if (k == 0) {
head = ne[head];
} else {
ne[k] = ne[ne[k]];
}
}
private static void insert(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
}