17370845950

Python数据结构学习关键不在讲数而在实操：list的in操作为O(n)全扫描，10万元素最坏比较10万次；set查重O(1)但需构建开销，小列表偶尔查询未必划算。

这标题不是学习路线，是营销包装出来的数字幻觉。Python 数据结构的学习根本不存在“第515讲”这种线性序列，真正卡住人的从来不是讲数，而是list和dict在什么场景下会意外变慢、set查重为什么有时不生效、deque真比list快在哪——这些得靠实操暴露问题。

为什么in操作在list里慢得反直觉？

因为它是 O(n) 全扫描，哪怕只查一个元素，也要从头比到尾。你写if x in my_list:时，如果my_list有 10 万个元素，最坏情况要比较 10 万次。

• 换成set：查重是 O(1)，但得先构建set(my_list)，有额外开销
• 如果只是偶尔查一次，且列表很小（list反而更轻量
• 别对list反复做in——比如在循环里写for item in big_list: if item in blacklist:，这时务必把blacklist转成set

dict的键必须不可变，但tuple能当键，list不能——为什么？

因为dict内部用哈希表实现，键的哈希值必须稳定。一旦list被修改，它的哈希值可能变化（实际会直接报错），导致字典内部索引失效。

my_dict = {}
my_dict[(1, 2)] = "valid"   # OK
my_dict[[1, 2]] = "invalid" # TypeError: unhashable type: 'list'

• tuple内容不变 → 哈希值不变 → 可安全当键
• tuple里嵌了list也不行：(1, [2, 3])仍报错
• 想用可变结构当“逻辑键”？改用frozenset或自定义__hash__（慎用）

用collections.deque代替list做队列，真能提速吗？

只在频繁.appendleft()或.popleft()时才明显快。因为deque是双向链表+块内存混合实现，两端操作 O(1)；而list在头部插入/删除是 O(n)，要整体搬移后面所有元素。

• 普通遍历、按索引取值（my_list[100]）：list更快，deque是 O(n) 随机访问
• 只用.append()和.pop()（尾部操作）：两者性能几乎没差别，list更常用也更省内存
• 典型适用场景：BFS 层序遍历、滑动窗口、任务队列

__slots__真能省内存？什么情况下反而坏事？

能，尤其当你创建大量实例（比如百万级Point(x, y)对象）时，__slots__禁用__dict__，每个实例少存一个字典指针（约 24–48 字节），积少成多。

• 加了__slots__后，实例不能动态加属性：p.z = 10会报AttributeError
• 继承时子类也得显式定义__slots__，否则父类的__slots__失效
• 用了__slots__就别指望用vars(p)或json.dumps(p)直接序列化，得手动处理

数据结构选型没有银弹，关键看你的数据规模、访问模式、是否需要动态扩展。跑个timeit比空想“该用哪个”有用十倍，而调试时打印sys.getsizeof()往往比文档更能说明问题。