数组模拟单链表-acwing

题目：

代码

new（），申请结点空间时间性能慢。

数组模拟链表，时间性能快，通过下标索引代替指针域。

head = -1, 头结点指针置空，也就是初始化位置为-1

idx 当前所需要用到的位置，向后不断申请空间的移动指针（下标）

e[i]  表示i指向的值域，值

ne[i] 表示i指向的指针域，指针，指向下一个结点的位置

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;// head 指向头结点
//e[i] 结点i的值域
//ne[i] 结点i的指针域，索引下一个点的位置
//idx 当前需要使用的位置，相当于指针向后移动，申请结点空间
int head, e[N], ne[N], idx;void init() {head = -1; idx = 0;
}
// 头插法
//刚开始创建的是一个，idx = 0，nex[idx] 指向空，头结点为-1的结点。
void add_to_head(int x) {//指向头结点，自身成为头结点。idx 向后移动e[idx] = x,ne[idx] = head, head = idx++;
}
//将x 插入到下标是k的点的后面
void add(int k, int x) {e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
// 将下标是k的点后面的点删掉
void remove(int k) {ne[k] = ne[ne[k]];
}int main() {int m;cin >> m;init();while(m --) {int k, x;char op;cin >> op;if(op == 'H') {cin >> x;add_to_head(x);}else if(op == 'D') {cin >> k;if(!k) head = ne[head];else remove(k - 1); // 因为下标从0开始，第k个要-1偏移得到下标}else {cin >> k >> x;add(k-1, x);}}for(int i = head; i!=-1; i = ne[i]) cout << e[i] << " ";cout << endl;return 0;
}

图文直观分析