数组模拟单链表 附带详细注释(见代码)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10;
int idx,head,a[N],ne[N],n;

void add(int x){
  // 存值
  a[idx] =x;
  // 将头节点 存位第一个节点的下一个。
  ne[idx] =head;
  // 指针移动到下一个值的位置。
  head = idx++;
}

void del(int x){
  //删除第x位的后一位 所以直接跳过下一位 即可
  ne[x] = ne[ne[x]];
}

void insert(int k,int x)
{
  //先将x的值存下来
  a[idx] =x;
  //再将添加的下一位指针指向 k的下一位
  ne[idx] = ne[k];
  // 将k的指针向后移一位
  ne[k] = idx++;
}

int main()
{
  idx =0,head =-1;
  cin>>n;
  int k,b;
  while(n--)
  {

    string s;
    cin>>s;
    if(s=="H"){
      cin>>k;
      add(k);
    }else if(s=="D"){
      cin>>k;
      // 为零则删除头节点
      if(!k) head = ne[head];
      // 删除第k个因为从0开始 第k个下标为k-1
      del(k-1);
    }else{
      cin>>b>>k;
      //第b个 即为 b-1 因为下标是从0开始的。
      insert(b-1,k);
    }
  }

  for(int i=head;i!=-1;i=ne[i]){
    printf("%d ",a[i]);
  }
  puts("");


  return 0;
}