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

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

一、链表的基本概念

链表是一种线性的、动态的数据结构，由一系列节点（Node）通过指针（或引用）连接而成。与数组不同，链表中的元素在内存中不是连续存储的，而是通过每个节点中的指针域来维护逻辑上的连续性。

链表的主要特点包括：

• 动态大小：可以随时增加或删除节点，无需预先分配固定空间
• 高效插入/删除：在已知位置插入或删除节点的时间复杂度为 O(1)
• 顺序访问：只能从头节点开始顺序访问，不支持随机访问

二、结构体实现链表

2.1 节点结构定义

在 C/C++ 中，我们通常使用结构体来定义链表节点：

struct Node {
    int data; // 数据域，存储节点值
    Node* next; // 指针域，指向下一个节点
};

类比说明：这个结构体定义类似于 JavaScript 中的类或 Java 中的对象。Node* next 相当于 Java 中的引用，指向下一个节点对象。

2.2 链表构建与遍历

让我们构建一个包含四个节点（数据分别为 1、2、3、4）的链表：

头节点 -> 1 -> 2 -> 3 -> 4 -> NULL

// 创建节点函数
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// 构建链表
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);

// 遍历链表
void traverseList(Node* head) {
    Node* p = head;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
}

遍历过程说明：

1. 初始化指针 p 指向头节点
2. 当 p 不为空时，输出当前节点数据
3. 将 p 移动到下一个节点（p = p->next）
4. 重复步骤 2-3 直到链表末尾

2.3 结构体实现的优缺点

优点	缺点
直观易懂，符合链表逻辑模型	内存分配不连续，可能导致缓存不命中
动态内存分配，灵活性强	频繁的内存分配/释放可能产生内存碎片
插入/删除操作高效	每个节点需要额外空间存储指针

三、数组实现链表

3.1 实现原理

数组实现链表的核心思想是用数组下标代替内存地址，将链表拆分为两个数组：

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

示例映射：

• data: 0, next: 1
• data: 1, next: 2
• data: 2, next: 4
• data: 100, next: 0
• data: 3, next: 3

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;          // 前驱指向新节点
}

3.3 构建与访问示例

构建一个链表，数据为 0、1、2、3、100：

// 构建链表
init();
insertAfter(head, 0);           // 在头节点后插入 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. 竞赛编程：数组实现更常见，因为通常有明确的数据规模限制

结语

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