列表随机访问O(1)但首部插入删除O(n)，元组不可变且更轻量；字典和集合平均O(1)依赖哈希表，查存在性优先用set；deque两端操作O(1)，适合队列场景。
列表 vs 元组：随机访问快，但插入删除慢
Python 的 list 是动态数组，底层连续分配内存，所以 list[i] 是 O(1) 时间；但 list.insert(0, x) 或 list.pop(0) 是 O(n)，因为要移动后续所有元素。tuple 不可变，创建后内存固定，访问同样 O(1)，但无法增删——这不是限制，而是提示你：如果数据只读、且长度已知，用 tuple 更轻量，还能作为字典键。
- 频繁在头部/中部插入？别硬扛
list，改用collections.deque - 循环中反复调用
list.append()是安全的，Python 已做倍增扩容优化 - 把大
list传给函数时，注意是引用传递；若不希望被意外修改，传my_list.copy()或list(my_list)
字典和集合的平均 O(1) 不是白来的
dict 和 set 底层靠哈希表实现，理想情况下查找、插入、删除都是平均 O(1)。但实际性能受哈希冲突和负载因子影响：
- 键类型必须可哈希（
list、dict不行，tuple可以） - 如果自定义类作键，必须正确定义
<strong>hash</strong>和<strong>eq</strong> - 大量插入后，Python 会自动扩容重哈希，这时单次操作可能卡到 O(n)——但均摊仍是 O(1)
- 用
in判断存在性：对list是 O(n)，对set是 O(1)，差距在十万级数据上就明显
当你要频繁查“有没有”，别用 list in
写 if x in my_list: 看似自然，但每次都是线性扫描。换成 my_set = set(my_list) 后再查，初始化多花 O(n)，但后续每次 in 都省下大量时间。
- 初始化成本可接受？比如数据只建一次、查几百次 → 换
set - 数据实时变动？用
set同步增删，比每次重建划算 - 内存敏感？
set比list占更多内存（哈希表有空槽），但通常值得 - 注意：
set不保序，如果顺序重要，Python 3.7+ 的dict可模拟有序集合：{x: None for x in items}
deque 在队列场景下比 list 稳定得多
list 做队列（append() + pop(0)）看似简单，但 pop(0) 每次都 O(n)。而 collections.deque 是双向链表+块状缓冲，两端操作都是 O(1)。
立即学习“Python免费学习笔记（深入）”；
- BFS、滑动窗口、任务队列等场景，直接上
deque -
deque支持appendleft()、popleft()、extendleft()，语义清晰 - 不要用
deque[i]随机访问——虽然支持，但退化为 O(n)，不如转成list再取 - 创建空
deque开销略大于list，但微乎其微；真正影响性能的是操作模式，不是构造本身
实际选型时，别只看「哪个更快」，要看「哪次操作最常发生」。一个算法里查 10 万次存在性，哪怕初始化多花 5ms，也远小于累计 2 秒的线性扫描。而很多人卡在“习惯写 list”，没意识到自己正在用 O(n) 解决本该 O(1) 的问题。
