python内置数据结构包括列表、字典、集合，树和图需手动实现或借助库。1. 列表是动态数组，适合顺序和随机访问，但频繁在头部插入元素建议用collections.deque；2. 字典基于哈希表，平均时间复杂度为o(1)，支持键值对存储，可保持插入顺序；3. 集合用于去重和集合运算，判断元素是否存在效率高；4. 树和图需自定义类或使用第三方库如networkx实现，常见遍历方式有深度优先和广度优先。掌握这些结构的实现有助于提升代码效率。
Python 作为一门高级编程语言，内置了很多常用的数据结构，并且支持灵活的自定义实现。掌握这些数据结构的实现方式，对理解算法、提升代码效率很有帮助。
列表（List）：动态数组的实现
Python 的列表是动态数组的一种实现，可以自动扩容。它在内存中是连续存储的，所以访问元素很快，时间复杂度为 O(1)。但插入和删除操作可能需要移动大量元素，最坏情况下时间复杂度为 O(n)。
- 如果你在频繁地往列表头部插入元素，建议考虑使用 collections.deque。
- 使用列表模拟栈（stack）时，用 append() 和 pop() 效率很高。
- 模拟队列（queue）时，用 pop(0) 性能较差，推荐用双端队列 deque.popleft()。
列表非常适合顺序访问和随机访问，但在频繁修改中间或开头位置时性能一般。
立即学习“Python免费学习笔记（深入）”；
字典（Dict）：哈希表的实现
字典是基于哈希表实现的，键值对存储，查找、插入和删除的时间复杂度平均为 O(1)，非常高效。每个键必须是可哈希的类型，比如整数、字符串、元组等。
- 字典底层通过哈希函数计算键的位置，如果发生冲突（不同键算出同一个索引），会采用开放寻址法或链式存储来解决。
- 如果你希望保持插入顺序，在 Python 3.7 及以上版本中，字典默认就是有序的。
- 自定义对象作为键时，要确保其实现了 __hash__() 和 __eq__() 方法。
如果你需要一个默认值返回机制，可以用 dict.get(key, default) 或者 collections.defaultdict。
集合（Set）：无序不重复集合
集合是基于哈希表实现的，内部只保存键，没有值。它适合用来去重或者进行集合运算（交集、并集、差集等）。
- 判断某个元素是否在集合中，比列表快得多，平均时间复杂度是 O(1)。
- 集合本身是不可哈希的，但有不可变版本 frozenset。
- 常见操作包括：add(), remove(), union(), intersection() 等。
举个例子：你想快速判断两个列表是否有共同元素，可以把它们转成集合后求交集。
树和图：需要手动实现或借助库
Python 标准库并没有直接提供树（Tree）或图（Graph）这类结构，通常需要自己构建类或者使用第三方库如 networkx。
- 实现二叉树时，通常定义节点类，包含值、左子节点和右子节点。
- 图可以用邻接表（字典+列表）或邻接矩阵（二维数组）表示。
- 常见遍历方式：深度优先（DFS）、广度优先（BFS）。
例如，用字典表示图：
graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E'], 'D': ['B'], 'E': ['C'] }
这种结构清晰又容易操作，适合处理图相关的搜索和路径问题。
基本上就这些。Python 提供了很丰富的基础数据结构，同时也很灵活，可以根据需要扩展实现更复杂的结构。了解它们的底层实现方式，有助于写出更高效的代码。
评论（已关闭）
评论已关闭