Python数据结构选择需匹配操作类型与规模：list适合随机访问但中间增删为O(n)，deque更适合两端操作；dict/set平均O(1)但有哈希开销；tuple/str不可变利于缓存；heapq和bisect可实现O(log n)堆操作与二分查找。
Python 数据结构的选择直接决定算法的时间和空间复杂度，不是所有结构在所有场景下都高效——关键看操作类型和数据规模。
列表（list）的“看似简单”陷阱
列表底层是动态数组，随机访问是 O(1)，但插入/删除末尾以外的位置（如 list.insert(0, x) 或 del list[5]）需移动后续元素，平均时间 O(n)。频繁在头部增删时，用 list 会让原本 O(n) 的算法退化成 O(n²)。
- 用 collections.deque 替代 list 做队列或栈操作（append/pop 左右两端都是 O(1)）
- 若只需遍历或按索引查值，list 完全合适；若需频繁中间修改，先评估是否可改用其他结构
字典（dict）与集合（set）：平均 O(1)，但别忽略哈希开销
Python 3.7+ 的 dict 是有序且平均查找/插入/删除为 O(1)，这得益于哈希表实现。但要注意：最坏情况（大量哈希冲突）会退化到 O(n)；键对象必须可哈希；且空间开销比 list 大约 2–3 倍。
- 用 set 判断存在性（x in my_set）比用 list（x in my_list）快得多——后者是 O(n)，前者平均 O(1)
- 避免用可变类型（如 list、dict）作 dict 键；字符串、数字、tuple（不含可变项）才是安全选择
元组（tuple）和字符串（str）：不可变≠低效，而是“预计算友好”
不可变性让 tuple 和 str 可被缓存哈希值，因此作为 dict 键或 set 成员时，首次哈希后无需重复计算。同时，小字符串和短元组创建和比较往往比等价的 list 更快。
立即学习“Python免费学习笔记（深入）”；
- 函数返回多个值时用 tuple（return a, b），解包自然且无额外开销
- 若数据不需修改，优先用 tuple 替代 list —— 内存更紧凑，且能作字典键，有助于设计更清晰的接口
堆（heapq）与排序列表：手动维护结构才能控复杂度
Python 没有内置的“有序列表”类型。用 list + sorted() 每次排序是 O(n log n)，而用 heapq 维护最小堆，每次 push/pop 是 O(log n)。同样，bisect 模块能在已排序 list 中二分插入/查找（O(log n)），但前提是 list 必须始终有序——你得自己保证这点。
- 需要动态获取最小/最大元素？选 heapq（注意它只提供最小堆，最大堆可用负值技巧）
- 需要按序遍历 + 频繁查找某值位置？考虑 sorted list + bisect，但插入代价是 O(n)，不如直接用 dict/set + sorted(keys()) 临时排序
