线性数据结构：数组与链表的深度解析

摘要

线性数据结构是计算程序中最为基础且应用最广泛的数据组织形式。本文将全面剖析数组和链表两大核心线性结构，包括它们的存储原理、操作实现、性能比较以及典型应用场景，帮助开发者根据实际需求选择最合适的数据结构。

1. 数组(Array)：连续存储的基石

1.1 基本特性

数组是将相同类型的元素存储在连续内存空间的数据结构。

# Python列表(动态数组)示例
arr = [10, 20, 30, 40, 50]

关键特点：

随机访问：通过索引直接访问，时间复杂度O(1)
固定类型：通常要求元素类型相同
连续内存：物理存储位置连续

1.2 操作复杂度分析

操作	时间复杂度	说明
访问	O(1)	通过索引直接计算内存地址
搜索	O(n)	需要遍历查找特定值
插入	O(n)	需要移动后续元素
删除	O(n)	需要移动后续元素

1.3 多维数组应用

# 二维数组表示矩阵
matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]# 访问元素matrix[1][2] -> 6

2. 链表(Linked List)：动态连接的灵活结构

2.1 基本实现

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 创建链表 1 -> 2 -> 3
head = ListNode(1, ListNode(2, ListNode(3)))

链表类型对比：

类型	特点	图示
单链表	每个节点只存储下一节点地址	1→2→3→None
双链表	节点存储前后节点地址	None⇄1⇄2⇄3⇄None
循环链表	尾节点指向头节点	1→2→3→1→...

2.2 操作复杂度

操作	时间复杂度	说明
访问	O(n)	需要从头遍历
搜索	O(n)	需要遍历查找
插入	O(1)*	已知位置时只需修改指针
删除	O(1)*	已知位置时只需修改指针

*注：查找插入/删除位置需要O(n)时间

3. 数组 vs 链表：终极对决

3.1 性能比较表

特性	数组	链表
内存分配	静态/动态连续	动态非连续
访问方式	随机访问	顺序访问
内存开销	较小(仅数据)	较大(含指针)
缓存友好	是(空间局部性)	否
扩展性	调整大小成本高	动态扩展灵活

3.2 选择指南

使用数组当：

需要频繁随机访问元素
已知或可预测数据量大小
需要内存效率最大化

使用链表当：

需要频繁插入/删除操作
数据量变化大或不可预测
不需要频繁随机访问

4. 实战应用案例

4.1 数组典型应用

图像处理中的像素矩阵
数值计算中的向量/矩阵
哈希表的桶实现
数据库表行存储

4.2 链表典型应用

实现栈、队列等抽象数据类型
文件系统的目录结构
内存管理中的空闲块链表
区块链的区块链接

# 用链表实现栈
class LinkedStack:def __init__(self):self.head = Nonedef push(self, val):self.head = ListNode(val, self.head)def pop(self):if not self.head:raise Exception("Empty Stack")val = self.head.valself.head = self.head.nextreturn val