单链表

一、数组实现

基本结构

int e[N], ne[N], idx;

• e[i]：节点值
• ne[i]：下一个节点编号
• idx：当前节点编号

插入头节点

void add_to_head(int x){
    e[idx] = x;
    ne[idx] = hh;
    hh = idx++;
}

删除节点

void remove(int k){
    ne[k] = ne[ne[k]];
}

完整模板

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int e[N], ne[N], idx;
int hh;

void add_to_head(int x){
    e[idx] = x;
    ne[idx] = hh;
    hh = idx++;
}

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

void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    hh = -1;
    add_to_head(1);
    add_to_head(2);

    for(int i = hh; i != -1; i = ne[i])
        cout << e[i] << " ";

    return 0;
}

二、指针实现

struct Node{
    int val;
    Node *next;
};

Node *head;

void add_to_head(int x){
    Node *p = new Node;
    p->val = x;
    p->next = head;
    head = p;
}