链表实现解析：结构体与数组两种方式对比

这里有个细节：遍历时初始化指针 p 指向头节点，只要 p 不为空就输出并后移，直到遇到 nullptr 结束。这种写法最符合直觉。

2.3 结构体实现的优缺点

三、数组实现链表

3.1 实现原理

数组实现的核心思路是用下标代替地址。我们把链表拆成两个数组：

• data[]：存节点的值
• next[]：存下一个节点的下标（相当于指针）

比如：下标 0 存值 1，next[0] 是 1；下标 1 存值 2，next[1] 是 2……这样就能模拟出链式关系。

3.2 代码实现

这种方式需要手动管理空闲节点，适合对性能要求高的场景。

const int MAX_SIZE = 100;
int data[MAX_SIZE];      // 数据域
int next[MAX_SIZE];      // 指针域（存下标）
int head = 3;            // 头节点下标
int freeIdx = 0;         // 当前空闲位置

// 初始化
void init() {
    for (int i = 0; i < MAX_SIZE - 1; i++) {
        next[i] = i + 1; // 连成空闲链表
    }
    next[MAX_SIZE - 1] = 0; // 0 表示 NULL
}

// 在 index 节点后插入值为 value 的节点
void insertAfter(int index, int value) {
    if (freeIdx == 0) return; // 空间已满
    int p = freeIdx;
    freeIdx = next[freeIdx];  // 更新空闲链表头
    data[p] = value;
    next[p] = next[index];    // 新节点指向原后继
    next[index] = p;          // 前驱指向新节点
}

注意看 insertAfter 的逻辑：先拿空闲位置，再调整前后节点的 next 指针，最后更新空闲链表头。这一步要是搞反了顺序，链表就断了。

3.3 构建与访问示例

// 构建链表
init();
insertAfter(head, 0);
insertAfter(next[head], 1);
insertAfter(next[next[head]], 2);
insertAfter(next[next[next[head]]], 3);
insertAfter(next[next[head]], 100); // 在 2 后面插入 100

// 遍历链表
void traverse() {
    int p = head;
    while (p != 0) {
        cout << data[p] << " ";
        p = next[p];
    }
}

3.4 数组实现的性能特点

四、两种实现方式对比

五、实际应用建议

1. 常规开发：优先选结构体实现，代码直观，维护方便。
2. 嵌入式/高性能：考虑数组实现，减少碎片，提高缓存命中率。
3. 竞赛编程：数组实现更常见，因为通常有明确的数据规模限制。

结语

链表作为基础数据结构，实现方式的选择往往取决于具体场景。理解这两种方式的原理和差异，能帮我们在实际开发中做出更合理的选择。无论是结构体的优雅直观，还是数组的高效紧凑，都体现了'同一个问题，多种解法'的精妙之处。