1110 字
6 分钟
python算法学习之数组与链表
一、基本概念
数组（Array） python
数组：连续内存中相同类型元素的集合
arr = [10, 20, 30, 40, 50] # Python中用list模拟数组内存布局：[10][20][30][40][50]核心定义：
在连续的内存空间存储相同数据类型的元素
通过索引（下标） 访问元素：arr[i]
知道首地址后，可通过公式计算任意元素地址：地址 = 首地址 + i × 元素大小
链表（Linked List）
链表节点
class ListNode: def __init__(self, val): self.val = val # 数据 self.next = None # 指向下一个节点的指针链表：1→3→5→7→None node1 = ListNode(1) node2 = ListNode(3) node3 = ListNode(5) node4 = ListNode(7) node1.next = node2 node2.next = node3 node3.next = node4
核心定义：
由节点（Node） 组成的线性集合
每个节点包含：
数据域（存储数据）
指针域（指向下一个节点的地址）
节点在内存中非连续，通过指针连接
二、共同点
线性结构：元素按顺序排列，有前驱后继关系
存储数据：都用于存储一组相关数据
基础操作：都支持插入、删除、查找、遍历
数组的优点
随机访问高效：O(1)时间复杂度访问任意元素
arr = [10, 20, 30, 40, 50] print(arr[2]) # 直接访问第三个元素：30，一步到位
内存连续，缓存友好：CPU预加载相邻元素，提高访问速度
内存开销小：只存储数据，无额外指针开销
实现简单：几乎所有编程语言原生支持数组的缺点
大小固定（静态数组）：声明后无法改变大小 int arr[100]; // 固定100个元素，不能增加
插入/删除低效：需要移动大量元素
# 在数组中间插入元素需要移动后面所有元素 arr = [1, 2, 4, 5] # 想在2后面插入3 # 需要：把4、5向后移动 → [1, 2, _, 4, 5] → 插入3内存浪费或不足：提前分配可能浪费，不够时需要重新分配
链表的优点
动态大小：运行时自由增加/删除节点
# 轻松添加新节点 new_node = ListNode(10) current.next = new_node # 只需修改指针
高效插入/删除：O(1)时间（如果知道位置） python
# 删除节点只需修改指针 # A → B → C → D，删除C B.next = D # 将B指向D，C自动被"跳过"
无内存预分配：按需分配，无内存浪费链表的缺点
顺序访问：访问第n个元素需要从头遍历，O(n)时间
# 访问链表第5个节点 current = head for i in range(4): # 必须走4步 current = current.next
内存开销大：每个节点都需要额外存储指针
缓存不友好：内存分散，无法利用CPU缓存
实现复杂：需要手动管理节点和指针三、实际应用场景
数组的典型应用
数值计算与矩阵运算
# 图像处理中的像素矩阵 image = [ [[255, 0, 0], [0, 255, 0], [0, 0, 255]], [[128, 128, 128], [64, 64, 64], [32, 32, 32]] ]
数据库记录存储 python
# 固定字段的记录集 employees = [ {"id": 1, "name": "Alice", "salary": 50000}, {"id": 2, "name": "Bob", "salary": 60000} ]
缓存实现 python
# 实现简单缓存（LRU的变种） cache = [None] * 100 # 固定大小的缓存数组
查找表 python
# 字符到ASCII码的查找表 char_table = [0] * 256 # 直接下标访问链表的典型应用
实现栈和队列
# 用链表实现栈（头部插入删除O(1)） class Stack: def __init__(self): self.head = None # 链表头作为栈顶
LRU缓存淘汰算法
# 最近最少使用，链表快速移动节点 # 最近使用的移到头部，淘汰尾部
文件系统
# 文件的块分配表（FAT文件系统） # 每个文件块包含数据和下一块地址
撤销功能（Undo）
# 编辑器中的撤销操作 # 每个操作作为节点，形成操作链
多项式表示
# 稀疏多项式：5x^100 + 2x^50 + 3 # 只存储非零项，节省空间四、实战代码示例{哈希表中的链地址法（数组+链表）}
class HashMap: def __init__(self, capacity=100): self.table = [None] * capacity # 数组：哈希桶
def put(self, key, value): index = hash(key) % len(self.table)
# 桶为空，创建链表 if not self.table[index]: self.table[index] = ListNode((key, value)) else: # 添加到链表头部 new_node = ListNode((key, value)) new_node.next = self.table[index] self.table[index] = new_node
# 结合了数组的快速定位和链表的动态扩展部分信息可能已经过时