链表算法实战：排队顺序与单向链表实现

链表是数据结构中的基础组件，掌握其基本操作对算法竞赛至关重要。本节通过两道经典题目，演示如何使用静态数组模拟链表以及标准单链表的实现细节。

一、排队顺序

1.1 题目

题目链接：排队顺序

1.2 算法原理

这道题的核心在于理解'静态链表'的概念。题目给出了每个节点的后继节点编号，我们可以直接用数组来存储这种关系。数组的下标代表节点编号（数据域），数组的值代表下一个节点的编号（指针域）。这样就能在不使用动态内存分配的情况下，高效地还原整个队列结构。

1.3 代码

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int ne[N]; // 存储后继节点

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> ne[i];
    }
    int head;
    cin >> head; // 读取头节点
    for (int i = head; i; i = ne[i]) {
        cout << i << " ";
    }
    return 0;
}

注意这里用 ne 数组模拟 next 指针，输入的头节点决定了遍历的起点。

二、单向链表

2.1 题目

题目链接：单向链表

2.2 算法原理

这是一道标准的单链表模板题。我们需要支持三种操作：在指定位置插入节点、查询指定位置的后继节点、删除指定节点的后继。关键在于维护好 head 指针以及 next 数组的指向关系，确保在插入或删除时不会丢失链表连接。

2.3 代码

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int e[N], ne[N]; // e 存值，ne 存后继

int main() {
    int q;
    cin >> q;
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            int y;
            cin >> y;
            ne[y] = ne[x];
            ne[x] = y;
        } else if (op == 2) {
            cout << ne[x] << endl;
        } else if (op == 3) {
            ne[x] = ne[ne[x]];
        }
    }
    return 0;
}

这里 op=1 表示在 x 后面插入 y，op=3 表示删除 x 的后继。实际编写时要注意操作的先后顺序，避免覆盖未保存的指针。

总结

这两道题分别展示了静态链表和动态链表的典型用法。在实际开发或竞赛中，如果数据范围固定且已知，静态数组往往比 new 或 malloc 更快且更安全。理解指针域的传递逻辑是解决链表问题的关键，多动手调试代码能帮你更好地建立空间模型。