数组，链表，栈，队列，哈希表等数据结构¶

面试有可能会被问道，简单记录一下。

数组（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字节) ...

优点： * 随机访问高效。 * 内存局部性好，缓存友好。 * 实现简单。

缺点： * 固定大小（静态数组）或动态扩容时有成本。 * 插入/删除非末尾元素效率低。

应用场景： * 需要频繁随机访问的场景。 * 数据量已知或变化不大的情况。 * 实现其他数据结构的基础（如栈、队列、堆、哈希表冲突解决等）。

系统级应用： * CPU缓存：利用数组的局部性原理优化缓存命中 * 文件系统：文件分配表（FAT）使用数组存储簇链 * GPU并行计算：数组结构适合SIMD（单指令多数据）并行处理

链表（Linked List）¶

定义： 由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针（单链表），或指向前后节点的指针（双向链表）。

特点： * 内存不连续，通过指针链接。 * 大小可动态增长，无需预先分配。

操作复杂度： * 访问：O(n)（必须从头遍历） * 插入/删除： * 在已知位置（如头/尾指针）：O(1) * 在未知位置（需先查找）：O(n)（查找时间）+ O(1)（插入/删除） * 搜索：O(n)

存储方式： * 非连续内存分配：节点可分散在内存的任何位置 * 动态分配：每个节点在需要时动态分配内存 * 指针连接：通过指针（地址）将节点连接起来

内存布局示例：

节点1: 0x2000 [数据|指针] → 指向0x3000
节点2: 0x3000 [数据|指针] → 指向0x1500
节点3: 0x1500 [数据|指针] → NULL

缺点： * 随机访问效率低。 * 额外内存开销（存储指针）。 * 缓存不友好，内存访问分散。

应用场景： * 需要频繁插入/删除的场景，尤其是数据量不可预知时。 * 实现栈、队列、图邻接表等。 * 内存分配管理（如操作系统中的空闲内存块链表）。

系统级应用：
* 进程控制块(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

图¶

图由顶点和边组成，可以表示复杂的关系。图分为有向图和无向图，常用于网络结构的表示。

# 示例代码：使用邻接表表示图
graph = {
   "A": ["B", "C"],
   "B": ["A", "D"],
   "C": ["A", "D"],
   "D": ["B", "C"]
}
print(graph["A"]) # 输出：['B', 'C']