深入浅出链表：从结构体到数组的两种实现方式

深入浅出链表：从结构体到数组的两种实现方式

• 一、链表的基本概念
• 二、结构体实现链表
  • 2.1 节点结构定义
  • 2.2 链表构建与遍历
  • 2.3 结构体实现的优缺点
• 三、数组实现链表
  • 3.1 实现原理
  • 3.2 代码实现
  • 3.3 构建与访问示例
  • 3.4 数组实现的性能特点
• 四、两种实现方式对比
• 五、实际应用建议
• 结语

本文 Bilibili 视频地址

链表作为计算机科学中最基础也最重要的数据结构之一，其灵活性和动态性使其在各种场景下都有广泛应用。本文将带你深入探索链表的两种实现方式：经典的结构体实现和高效的数组实现。

一、链表的基本概念

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

链表的主要特点包括：

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

二、结构体实现链表

2.1 节点结构定义

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

structNode{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);// 遍历链表voidtraverseList(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 代码实现

constint MAX_SIZE =100;int data[MAX_SIZE];// 数据域int next[MAX_SIZE];// 指针域（存储下一个节点的下标）int head =3;// 头节点下标int freeIdx =0;// 当前空闲位置// 初始化voidinit(){for(int i =0; i < MAX_SIZE -1; i++){ next[i]= i +1;// 初始化空闲链表} next[MAX_SIZE -1]=0;// 0表示NULL}// 在index节点后插入值为value的节点voidinsertAfter(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);// 在头节点后插入0insertAfter(next[head],1);insertAfter(next[next[head]],2);insertAfter(next[next[next[head]]],3);insertAfter(next[next[head]],100);// 在2后面插入100// 遍历链表voidtraverse(){int p = head;while(p !=0){ cout << data[p]<<" "; p = next[p];}}

3.4 数组实现的性能特点

四、两种实现方式对比

五、实际应用建议

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

结语

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

希望本文能帮助你更深入地理解链表的本质，在未来的编程实践中灵活运用这两种实现方式！