链表

数组要求元素连续存储，容量固定或扩容时需要搬迁；链表由节点链接而成，节点含数据域和指针域，不要求连续存放。它以 O(1) 的已知位置插删能力，交换 O(1) 随机访问能力。

静态链表

竞赛中常用数组模拟指针：val[i] 保存数据，nxt[i] 保存后继下标，head=-1 表示空表，idx 指向下一个可用节点。已知节点下标时，头插、后插、删除后继均为 O(1)。

const int N = 100005;
int head = -1, idx = 0, val[N], nxt[N];
void addHead(int x) {
    val[idx] = x; nxt[idx] = head; head = idx++;
}
void insertAfter(int k, int x) {
    val[idx] = x; nxt[idx] = nxt[k]; nxt[k] = idx++;
}
void eraseAfter(int k) {
    if (nxt[k] != -1) nxt[k] = nxt[nxt[k]];
}
for (int p = head; p != -1; p = nxt[p]) cout << val[p] << ' ';

按位置访问和查找仍需遍历 O(n)，且应检查数组容量和后继是否存在。

动态链表

struct Node {
    int val;
    Node* next;
    Node(int v, Node* n = nullptr) : val(v), next(n) {}
};
Node* head = nullptr;
head = new Node(5, head);  // 头插
// 删除节点后应 delete 被删除的节点

动态链表按需通过 new 创建节点；工程代码必须在删除节点后 delete，或使用智能指针管理所有权。带哨兵头节点可统一首节点和中间节点的插删逻辑。

变体与选择

双向链表增加 prev，可在已知节点时 O(1) 删除自身并支持双向遍历；循环链表让尾节点指向头节点，遍历应以回到起点为终止条件。数组适合随机访问和缓存友好的遍历，链表适合已知位置的频繁局部修改。