链表模板

单链表与双链表的数组模拟——竞赛中最高效的实现

链表单链表双链表数组模拟 GESP5

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

// ====== 单链表（数组模拟）======
int head, e[N], ne[N], idx;

void init() { head = -1; idx = 0; }

void insertHead(int x) {
    e[idx] = x; ne[idx] = head; head = idx++;
}

void insertAfter(int k, int x) {  // 在下标k后插入
    e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++;
}

void remove(int k) {  // 删除下标k后的节点
    if (k == -1) head = ne[head];
    else ne[k] = ne[ne[k]];
}

// ====== 双链表（数组模拟）======
int l[N], r[N], val[N], idx2;

void init2() {
    r[0] = 1; l[1] = 0; idx2 = 2;  // 0=左端点, 1=右端点
}

void insertR(int k, int x) {  // 在k右边插入
    val[idx2] = x;
    l[idx2] = k; r[idx2] = r[k];
    l[r[k]] = idx2; r[k] = idx2++;
}

int main() {
    init();
    insertHead(3);
    insertHead(5);
    insertHead(7);

    for (int i = head; i != -1; i = ne[i])
        cout << e[i] << " ";
    // 输出: 7 5 3
    return 0;
}

📖 要点说明

数组模拟链表比指针快，竞赛首选
e[i] 存值，ne[i] 存下一个节点下标
双链表用两个哨兵节点 0 和 1

⚠️ 常见错误

插入顺序搞错导致链断裂
删除忘处理头节点特殊情况
双链表插入时操作顺序错误