数据结构之手写单链表(数组)(Java)
import java.util.*;
import java.io.*;
class Main {
static int[] e = new int[100010];// 存储值
static int[] ne = new int[100010];// 存储下一个节点的地址,充当指针
static int head = -1;// head:表示头节点的下标,NULL表示为-1(head不是节点,只是指向某个节点的指针)
static int idx = 0;// 表示当前已经用到了哪个节点
static Scanner in = new Scanner(new BufferedInputStream(System.in));// 优化输入速度
// 向链表投插入
static void insertToHead(int x) {
e[idx] = x;// 先赋值
ne[idx] = head;// 指向头节点指向的节点
head = idx ++ ;// 节点数加一
}
static void insert(int k, int x) {
e[idx] = x;// 先赋值
ne[idx] = ne[k];// 指向k指向的节点
ne[k] = idx ++ ;// 节点数加一
}
// 删除节点
static void delete(int k) {
ne[k] = ne[ne[k]];// ne[ne[k]]:表示下下个节点的地址
}
public static void main(String[] args) {
int m = in.nextInt();
while (m -- > 0) {
char c = in.next().charAt(0);
int k;
int x;
if (c == 'H') {
x = in.nextInt();
insertToHead(x);
} else if (c == 'I') {
k = in.nextInt();
x = in.nextInt();
insert(k - 1, x);// k - 1:是因为题目说的是第k个插入的数,你想第一个插入的元素,下表是0
} else {
k = in.nextInt();
if (k == 0) {
head = ne[head];
} else {
delete(k - 1);
}
}
}
// 从头节点开始循坏遍历,输出数值,直到i变为NULL(即为-1),i = ne[i]:i后移一个节点
for (int i = head; i != -1; i = ne[i]) {
System.out.print(e[i] + " ");
}
}
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码