Python3 数据结构

在 Python 3 中，数据结构是组织和存储数据的方式，直接决定了程序的运行效率和代码的优雅程度。Python 提供了丰富且高度优化的内置数据结构，以及强大的标准库支持。

下面我将从四大基础内置结构、高级标准库结构到性能与选择指南，为你系统梳理 Python 3 的数据结构。

一、 四大基础内置数据结构

1. 列表 (List) []

• 特性：可变、有序、允许重复元素。
• 时间复杂度：尾部追加/弹出 O(1)，头部插入/删除 O(n)，按索引查找 O(1)。
• 常用操作： nums = [1, 2, 3] nums.append(4) # 尾部追加: [1, 2, 3, 4] nums.insert(0, 0) # 指定位置插入: [0, 1, 2, 3, 4] nums.pop() # 尾部弹出并返回: 4 nums[1:3] # 切片: [1, 2] # 现代 Python 3 推荐：列表推导式 (List Comprehension) squares = [x**2 for x in range(5) if x % 2 == 0] # [0, 4, 16]

2. 元组 (Tuple) ()

• 特性：不可变、有序、允许重复元素。
• 用途：保护数据不被修改；作为字典的键 (Key)；函数返回多个值。
• 常用操作： point = (10, 20) # point[0] = 15 # ❌ TypeError: 'tuple' object does not support item assignment # 解包 (Unpacking) x, y = point print(x, y) # 10 20 # 具名元组 (见下文 collections 模块，更推荐)

3. 集合 (Set) {}

• 特性：可变、无序、元素唯一（基于哈希表实现）。
• 时间复杂度：添加、删除、查找均为 O(1)。
• 常用操作： set_a = {1, 2, 3, 4} set_b = {3, 4, 5, 6} set_a.add(5) # 添加元素 set_a.remove(1) # 删除元素 (不存在会报错) set_a.discard(99) # 删除元素 (不存在不报错，推荐) # 集合运算 (非常高效) print(set_a & set_b) # 交集: {3, 4, 5} print(set_a | set_b) # 并集: {2, 3, 4, 5, 6} print(set_a - set_b) # 差集: {2}

4. 字典 (Dictionary) {k: v}

• 特性：可变、键唯一、Python 3.7+ 保证插入顺序。基于哈希表实现。
• 时间复杂度：查找、插入、删除平均均为 O(1)。
• 常用操作： user = {"name": "Alice", "age": 25} user["city"] = "Beijing" # 添加/修改 age = user.get("age", 18) # 安全获取，找不到返回默认值 18 # 遍历 for key, value in user.items(): print(f"{key}: {value}") # 字典推导式 squared_dict = {x: x**2 for x in range(3)} # {0: 0, 1: 1, 2: 4}

二、 进阶：collections 模块 (Python 数据结构的神器)

当内置结构不够用时，collections 模块提供了针对性优化的高级数据结构。

1. deque (双端队列)

• 痛点：List 在头部插入/删除 (insert(0, x) 或 pop(0)) 是 O(n) 的，性能极差。
• 解法：deque 基于双向链表，两端操作均为 O(1)。非常适合实现队列 (Queue) 或滑动窗口。 from collections import deque q = deque([1, 2, 3]) q.append(4) # 右端添加: O(1) q.appendleft(0) # 左端添加: O(1) q.pop() # 右端弹出: O(1) q.popleft() # 左端弹出: O(1)

2. defaultdict (带默认值的字典)

• 痛点：普通字典访问不存在的键会抛出 KeyError。
• 解法：自动为不存在的键提供一个默认值（由传入的工厂函数决定）。 from collections import defaultdict # 统计词频 words = ["apple", "banana", "apple", "orange"] freq = defaultdict(int) # int() 默认返回 0 for word in words: freq[word] += 1 # 无需检查键是否存在 print(dict(freq)) # {'apple': 2, 'banana': 1, 'orange': 1} # 分组 groups = defaultdict(list) groups["even"].append(2) groups["odd"].append(3)

3. Counter (计数器)

• 用途：专门用于统计可哈希对象的出现次数，是 defaultdict(int) 的增强版。 from collections import Counter text = "abracadabra" counts = Counter(text) print(counts) # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}) print(counts.most_common(2)) # 获取出现次数最多的 2 个: [('a', 5), ('b', 2)]

4. namedtuple (具名元组) / 现代替代：dataclasses

• 用途：创建轻量级、不可变的数据对象，比字典更省内存，比元组可读性更强。 from collections import namedtuple # 定义 Point = namedtuple('Point', ['x', 'y']) p = Point(10, 20) print(p.x, p.y) # 10 20 (支持属性访问) # p.x = 15 # ❌ 不可变 💡 Python 3.7+ 现代推荐：对于需要可变或更复杂逻辑的数据对象，优先使用 @dataclass (见下文最佳实践)。

三、 特殊结构：heapq (堆 / 优先队列)

Python 没有内置的 PriorityQueue 类，但提供了 heapq 模块，它基于普通的 List 实现最小堆。

• 用途：动态获取最大值/最小值、Top-K 问题、Dijkstra 算法。
• 时间复杂度：插入 O(log n)，弹出最小值 O(log n)，获取最小值 O(1)。

import heapq

nums = [5, 1, 9, 3]
heapq.heapify(nums)       # 原地将列表转换为堆: [1, 3, 9, 5]

heapq.heappush(nums, 2)   # 插入新元素并保持堆性质
smallest = heapq.heappop(nums) # 弹出并返回最小值: 1

# 实用技巧：获取最大的 N 个元素
top_2 = heapq.nlargest(2, [5, 1, 9, 3]) # [9, 5]

四、 数据结构选择指南 (决策树)

在实际开发中，如何选择合适的数据结构？请参考以下逻辑：

五、 Python 3 数据结构最佳实践

1. 优先使用推导式 (Comprehensions)：
   比传统的 for 循环 + append 更快、更 Pythonic。

   # ❌ 慢且啰嗦
   res = []
   for i in range(10):
       if i % 2 == 0:
           res.append(i)

   # ✅ 快且优雅
   res = [i for i in range(10) if i % 2 == 0]

2. 善用生成器表达式 (Generator Expressions)：
   如果数据量极大，使用 () 代替 [] 创建推导式，可以按需生成，节省大量内存。

   # 列表推导式：立即计算并占用内存
   big_list = [x**2 for x in range(1000000)] 

   # 生成器表达式：惰性求值，内存占用极小
   big_gen = (x**2 for x in range(1000000))
   print(next(big_gen)) # 0

3. 使用 Type Hints (类型提示)：
   Python 3.9+ 内置了泛型类型，让数据结构的使用更加清晰，配合 IDE 能大幅减少 Bug。

   from typing import List, Dict, Set, Tuple

   def process_data(items: List[int], config: Dict[str, float]) -> Set[str]:
       # ...
       pass

   # Python 3.9+ 可以直接使用内置类型
   def process_data_modern(items: list[int], config: dict[str, float]) -> set[str]:
       pass

4. 复杂数据模型使用 @dataclass：
   替代传统的字典或 namedtuple，提供默认值、类型检查和自动生成的 __init__、__repr__。

   from dataclasses import dataclass

   @dataclass
   class User:
       name: str
       age: int
       is_active: bool = True  # 默认值

   u = User("Alice", 25)
   print(u)  # User(name='Alice', age=25, is_active=True)

如果你想深入了解某个特定场景（例如：如何用数据结构优化一个具体的算法题，或者 dataclass 的高级用法），可以随时告诉我！