单联表题目用数组模拟单链表

题目：acwing 单链表

答案：思路：

此题需要知道每个节点的插入时间，用普通的链表肯定行不通，因此我们用数组模拟链表，e数组只是用来记录每个节点的数值，ne数组是记录每个节点的下一个节点，所以本质上ne数组是记录链表条链的。

#include 
#include 

using namespace std; 

const int N=1000010;
//存头结点所指向的数组下标
int head;
//每个节点存的值
int e[N];
//每个节点的next指针
//ne数组实际上是存的e数组的下标
int ne[N];
//代表每个在操纵的节点
int idx;
int a;
//初始化链表，这时的head头结点没有指向的e数组下标，所以为-1
void init(){
    //一个节点对应的ne[i]如果存的是-1代表它之后没有节点了，它就是最后一个
	 head=-1;
	 idx=0;
}
void add_head(int n){
	e[idx]=n;
	ne[idx]=head;
	head=idx;
	idx++;

}

void remove(int k){
	ne[k]=ne[ne[k]];
	
}
void add(int k,int n){
	e[idx]=n;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}
int main(){

    head=-1;idx=0;
    cin>>a;
    while(a--){
        string op;
        int k,x;
        cin>>op;
        if(op=="D")
        {

            cin>>k;
            if(!k)head=ne[head];
            remove(k-1);
        }
        else if(op=="H")
        {
            cin>>x;
            add_head(x);
        }
        else if(op=="I"){
            int k,x;
            cin>>k>>x;
            add(k-1,x);
        }
    }
    //从head开始遍历链表直到遍历到最后一个节点
    for(int i=head;i!=-1;i=ne[i])
      cout<