C++ 数组模拟链表例题详解

例题： (原题链接：Acwing 826)

实现一个单链表，链表初始为空，支持三种 *** 作：

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

   
   

现在要对该链表进行 M 次 *** 作，进行完所有 *** 作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。

例如 *** 作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 MM，表示 *** 作次数。

接下来 MM 行，每行包含一个 *** 作命令， *** 作命令可能为以下几种：

1. H x，表示向链表头插入一个数 x。
   

   
   

2. D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
   

   
   

3. I k x，表示在第 k 个插入的数后面插入一个数 x（此 *** 作中 k 均大于 0）。
   

   
   

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000
所有 *** 作保证合法。

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例：

6 4 6 5

代码如下：

#include
using namespace std;
#define int long long
const int N = 111111;

//head表示头结点的下标 
//e[i]表示结点i的值
//ne[i]表示结点i的next指针值是多少
//idx表示当前已经用到了哪个点 
int head, e[N], ne[N], idx = 0;

//初始化链表 
void init(){
	head = -1; //此时链表为空，head指向-1 
	idx = 0; //表示起点从0号点开始
} 

//把一个x结点插入到头结点的后面 
void add_to_head(int x){
	e[idx] = x;
	ne[idx] = head; //待插入的结点的next指针指向head指向的结点
/*补充说明： 
head的作用一：链表初始化的时候等于-1，表示链表为空
二：指向下一个结点，即 head = 下标, "下标"指的是下一个结点的下标 
next的作用：指向下一个结点的下标，也就是idx值(head第二作用相当于next) 
*/
	head = idx;  //head指向插入的这个点的下标，也就是指向idx 
	idx++; //当前下标为idx的结点被占用，idx++ 
}

//在两个点之间插入新的结点(将x插入到下标是k个结点的后面) 
void add(int k, int x){
	e[idx] = x; //idx指的是新的结点占用的下标是idx 
	ne[idx] = ne[k]; //新结点的next指针,指向下标k结点的next指针所指向的结点 
	ne[k] = idx;  //下标k结点的next指针指向新插入的结点 
	idx++;   //新插入的结点占用了原来的idx，idx++ 
}

//将第k个点后面的一个结点删掉 
void remove(int k){
	ne[k] = ne[ne[k]]; //原来k结点next指针指向下一个结点，现在想把下一个结点删掉
	//那么直接让k结点next指针指向下一个结点的下一个结点
	//即直接将k结点的next指针指向下一个结点next指针指向的结点 
}	//这样就完成了删除 *** 作 

signed main(){
	int M;
	char ch;
	cin >> M;
	init();
	while(M--){
		cin >> ch;
		switch(ch)
		{
			case 'H':
				int x;
				cin >> x;
				add_to_head(x);
				break; 
			case 'D':
				int k;
				cin >> k;
				if (!k) head = ne[head]; //删除头结点 
				else remove(k - 1);
				break; 
			case 'I':
				cin >> k >> x;
				add(k - 1, x);
				break; 
		}
	}
	for(int i = head; i != -1; i = ne[i])
		cout << e[i] << " "; 
	
	return 0;
}