数组，链表，栈，队列，哈希表等数据结构¶
面试有可能会被问道，简单记录一下。
数组（Array）¶
定义: 一段连续内存空间，存储相同类型的元素，通过索引（下标）直接访问。
特点：
- 内存连续，支持随机访问。
- 大小通常固定（静态数组），部分语言支持动态数组（如C++ vector、Python list），其大小可动态增长但需重新分配内存。
操作复杂度：
- 访问：O(1)（按索引）
- 插入/删除：
- 在末尾：平均O(1)（动态数组分摊成本）
- 在中间或开头：O(n)（需移动后续元素）
- 搜索（无序）：O(n)
- 搜索（有序）：O(log n)（二分查找）
内存存储方式：
- 连续内存分配：数组在内存中占据一段连续的内存空间
- 固定大小：声明时确定大小（静态数组）或动态分配时确定大小
- 顺序存储：元素在内存中按顺序依次排列
内存布局示例：
内存地址: 0x1000 0x1004 0x1008 0x100C ...
数组元素: arr[0] arr[1] arr[2] arr[3] ...
数据类型: int(4字节) int(4字节) int(4字节) int(4字节) ...
- 元素地址 = 基地址 + 索引 × 元素大小
- 例如：arr[3]地址 = arr基地址 + 3 × 4字节（假设int为4字节）
优点：
- 随机访问高效。
- 内存局部性好，缓存友好。
- 实现简单。
缺点：
- 固定大小（静态数组）或动态扩容时有成本。
- 插入/删除非末尾元素效率低。
应用场景：
- 需要频繁随机访问的场景。
- 数据量已知或变化不大的情况。
- 实现其他数据结构的基础（如栈、队列、堆、哈希表冲突解决等）。
系统级应用：
- CPU缓存：利用数组的局部性原理优化缓存命中
- 文件系统：文件分配表（FAT）使用数组存储簇链
- GPU并行计算：数组结构适合SIMD（单指令多数据）并行处理
链表（Linked List）¶
定义： 由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针（单链表），或指向前后节点的指针（双向链表）。
特点：
- 内存不连续，通过指针链接。
- 大小可动态增长，无需预先分配。
操作复杂度：
- 访问：O(n)（必须从头遍历）
- 插入/删除：
- 在已知位置（如头/尾指针）：O(1)
- 在未知位置（需先查找）：O(n)（查找时间）+ O(1)（插入/删除）
- 搜索：O(n)
存储方式：
- 非连续内存分配：节点可分散在内存的任何位置
- 动态分配：每个节点在需要时动态分配内存
- 指针连接：通过指针（地址）将节点连接起来
内存布局示例：
优点：- 动态大小，无需预分配。
- 插入/删除节点（在已知位置）效率高，只需调整指针。
缺点：
- 随机访问效率低。
- 额外内存开销（存储指针）。
- 缓存不友好，内存访问分散。
应用场景：
- 需要频繁插入/删除的场景，尤其是数据量不可预知时。
- 实现栈、队列、图邻接表等。
- 内存分配管理（如操作系统中的空闲内存块链表）。
系统级应用：
- 进程控制块(PCB)管理：操作系统用链表管理就绪、阻塞进程队列
- 哈希表冲突解决：链地址法使用链表存储冲突元素
- 符号表管理：编译器用链表管理变量符号
- 图表示：邻接表用链表存储每个顶点的邻接点
栈 (Stack)¶
定义： 后进先出（LIFO）的线性数据结构，只允许在一端（栈顶）进行插入（入栈）和删除（出栈）操作。
实现方式：
- 基于数组：需预先指定大小，栈顶指针移动。
- 基于链表：动态大小，栈顶为头节点。
操作复杂度（假设实现合理）：
- 入栈 (push)：O(1)
- 出栈 (pop)：O(1)
- 查看栈顶 (peek)：O(1)
- 搜索：O(n)（需遍历）
优点：
- 简单高效，LIFO操作常数时间。
- 函数调用、表达式求值等场景直观。
缺点：
- 访问限制，只能操作栈顶。
- 数组实现有容量限制；链表实现有额外指针开销。
应用场景：
- 函数调用栈（递归、调用历史）。
- 表达式求值（括号匹配、后缀表达式）。
- 浏览器前进后退、撤销操作。
- 深度优先搜索。
队列 (Queue)¶
定义： 先进先出（FIFO）的线性数据结构，允许在一端（队尾）插入，在另一端（队头）删除。
变种：
- 双端队列 (Deque)：两端均可插入删除。
- 循环队列：基于数组，解决假溢出。
- 优先队列：按优先级出队，通常用堆实现。
操作复杂度（假设实现合理）：
- 入队 (enqueue)：O(1)
- 出队 (dequeue)：O(1)
- 查看队头 (front)：O(1)
- 搜索：O(n)
优点：
- FIFO操作常数时间。
- 任务调度、缓冲等场景自然。
缺点：
- 访问限制，只能操作两端。
- 数组实现有空间限制或需循环使用；链表实现有指针开销。
应用场景：
- 任务调度（CPU调度、打印队列）。
- 消息队列（生产者-消费者）。
- 广度优先搜索。
- 缓存（如最近使用缓存）。
哈希表 (Hash Table)¶
定义： 通过键（key）直接访问值（value）的数据结构，利用哈希函数将键映射到存储位置（桶）。
关键组成部分：
- 哈希函数：将键转换为数组索引。
- 冲突解决：开放寻址（线性探测、二次探测）、链地址法（每个桶为一个链表/树）。
操作复杂度（平均情况，假设哈希函数均匀、负载因子适当）：
- 插入：O(1)
- 删除：O(1)
- 查找：O(1)
- 最坏情况（所有键冲突）：O(n)（退化为链表/线性搜索）
优点：
- 平均常数时间的插入、删除、查找。
- 灵活，键值对存储。
缺点：
- 最坏情况性能差（依赖哈希函数和冲突处理）。
- 无序（除非使用有序哈希表）。
- 内存使用较高（需预留空间以减少冲突）。
应用场景：
- 字典/关联数组（数据库索引、缓存）。
- 对象属性映射（JavaScript对象、Python字典）。
- 去重（集合实现）。
- 快速查找表（符号表、编译器）。
树¶
树是一种层次结构，每个节点有零个或多个子节点。二叉树是树的一种特殊形式，每个节点最多有两个子节点。树结构在处理大批量动态数据方面非常有用。
# 示例代码：创建一个二叉树并遍历其元素
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
def inorder_traversal(node):
if node:
inorder_traversal(node.left)
print(node.data)
inorder_traversal(node.right)
inorder_traversal(root)
堆¶
堆是一种特殊的树形结构，用于实现优先队列。堆分为最大堆和最小堆，根节点分别是最大值和最小值。
# 示例代码：使用heapq模块实现最小堆
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 输出：1
图¶
图由顶点和边组成，可以表示复杂的关系。图分为有向图和无向图，常用于网络结构的表示。