在 Python 中，数据结构是组织、管理和存储数据的核心。我们可以将其分为两类：内置数据结构（最常用）和高级/扩展数据结构（来自标准库 collections 或 heapq）。
考虑到你正在准备面试并有 LeetCode 刷题经验，理解这些结构的时间复杂度和底层实现至关重要。
1. 四大内置数据结构
列表 (List) —— 动态数组
-
特点：有序、可变、元素可重复。
-
底层：本质是一个连续内存的数组。当空间不足时，会进行“扩容”（通常是申请更大的内存并拷贝旧数据）。
-
复杂度：
-
访问/修改：O(1)
-
尾部添加/删除：O(1)
-
中间/头部插入/删除：O(n)（因为需要移动后面的元素）
元组 (Tuple) —— 只读数组
-
特点：有序、不可变、元素可重复。
-
用途：作为字典的 Key（因为不可变且可哈希）；用于函数返回多个值。
-
优势：比 List 更轻量，性能略高，且线程安全。
字典 (Dictionary) —— 哈希表
-
特点：无序（Python 3.7+ 保持插入顺序）、键值对存储、Key 必须是可哈希的。
-
底层：使用哈希表 (Hash Table) 实现。通过对 Key 进行 Hash 运算决定存储位置。
-
复杂度：
-
插入/查询/删除：平均 O(1)，最坏 O(n)（发生严重哈希冲突时）。
集合 (Set) —— 只有 Key 的字典
-
特点：无序、元素唯一。
-
用途：去重、集合运算（交集
&、并集|、差集-）。 -
复杂度：查询和增加都是 O(1)。
2. 算法面试常备结构 (collections 模块)
在 LeetCode 中，内置的 List 有时无法满足性能要求，这时需要使用专门的工具：
双端队列 (collections.deque)
- 场景：实现队列 (FIFO) 或 栈 (LIFO)。
- 优势：在头部和尾部添加/删除元素的时间复杂度均为 $O(1)$。
- 注意：普通 List 在头部
pop(0)的复杂度是 $O(n)$，面试中实现 BFS（广度优先搜索）必须用deque。
计数器 (collections.Counter)
- 场景：统计频率。
- 例子：
Counter("abracadabra")会直接返回每个字符出现的次数，在处理“有效字母异位词”等问题时非常快。
堆 (heapq)
- 场景：优先队列、求 Top K 问题。
- 特性：Python 默认实现的是小顶堆（堆顶是最小元素）。
- 复杂度：插入 O(\log n)，弹出最小元素 O(\log n)。
3. 深层考点：可变性与哈希 (Mutability & Hashing)
面试官经常会问：“为什么 List 不能作为 Dict 的 Key，而 Tuple 可以？”
-
原因：Dict 的底层是哈希表。为了快速定位，Key 必须是不可变 (Immutable) 且 可哈希 (Hashable) 的。
-
Hashable 判定：一个对象如果在其生命周期内
hash()值不变，它就是可哈希的。 -
list、set、dict是不可哈希的。 -
int、str、tuple是可哈希的。
4. 总结对比表
| 数据结构 | 查找复杂度 | 是否可变 | 底层实现 | 典型场景 |
|---|---|---|---|---|
| List | O(n) | 是 | 动态数组 | 存储一组有序数据 |
| Tuple | O(n) | 否 | 静态数组 | 记录、函数多返回值 |
| Dict | O(1) | 是 | 哈希表 | 快速查找、映射关系 |
| Set | O(1) | 是 | 哈希表 | 去重、关系运算 |
| Deque | O(n) | 是 | 双向链表 | 队列、BFS 搜索 |
| Heap | O(1)(查) | 是 | 完全二叉树 | Top K、优先级排序 |
💡 实战建议
你在做 Distributed Log Analysis (分布式日志分析) 项目时，如果需要对大量 IP 进行实时计数，建议使用 dict 或 Counter；如果你需要处理带有优先级的预警任务，heapq 则是首选。
你想看一个关于如何用 deque 和 heapq 解决具体算法问题的代码对比吗？