单链表模板(数组模拟链表)

为什么要用数组模拟链表而不是动态分配内存？
因为new分配速度慢,算法题中一般都使用数组模拟链表

注意:如果用%c读入操作,必须把换行符读入了再读入操作!

例题:https://www.acwing.com/problem/content/828/

#include 
#include 

using namespace std;

const int N = 100010;

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

// 初始化
void init()
{
    Head = -1;
    idx = 0;
}

// 将x插到头结点
void add_head(int x)
{
    e[idx] = x;
    ne[idx] = Head;
    Head = idx;
    idx++;
}

// 将x插到下标是k的点的后面
void add_k(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 将下标是k的点后面的点删除
void remove(int k)
{
    ne[k] = ne[ne[k]];
}


int main()
{
    scanf("%d",&m);
    init();
    while(m--)
    {
        char op = '-1';
        int k,x;
        while(op != 'H' && op != 'D' && op != 'I')
        {
            scanf("%c",&op);
        }
        if(op == 'H')
        {
            scanf("%d",&x);
            add_head(x);
            
        }
        else if(op == 'D')
        {
            scanf("%d",&k);
            if(k == 0) Head = ne[Head];
            else remove(k-1);
        }
        else
        {
            scanf("%d%d",&k,&x);
            add_k(k-1,x);
        }
    }
    for(int i = Head; i != -1; i = ne[i])
    {
        printf("%d ",e[i]);
    }
    printf("n");
    return 0;
}