# Python 数据结构速查手册

> 涵盖线性表、堆、数组操作等常用数据结构的 Python 实现

---

## 一、线性表（List）

### 1. 基本概念
线性表是最基础的数据结构，Python 中用 `list` 实现。

### 2. 常用操作

| 操作 | 代码 | 时间复杂度 | 说明 |
|------|------|-----------|------|
| 创建 | `lst = []` 或 `lst = [1, 2, 3]` | O(1) | 初始化 |
| 访问 | `lst[i]` | O(1) | 随机访问 |
| 修改 | `lst[i] = x` | O(1) | 按索引修改 |
| 尾部添加 | `lst.append(x)` | O(1) 均摊 | 动态数组扩容 |
| 尾部删除 | `lst.pop()` | O(1) | 删除最后一个 |
| 插入 | `lst.insert(i, x)` | O(n) | 在位置 i 插入 |
| 删除 | `lst.pop(i)` | O(n) | 删除位置 i 的元素 |
| 删除指定值 | `lst.remove(x)` | O(n) | 删除第一个值为 x 的元素 |
| 查找 | `lst.index(x)` | O(n) | 查找 x 的位置 |
| 切片 | `lst[a:b]` | O(b-a) | 获取子列表 |
| 排序 | `lst.sort()` / `sorted(lst)` | O(n log n) | 原地排序 / 返回新列表 |
| 反转 | `lst.reverse()` | O(n) | 原地反转 |
| 长度 | `len(lst)` | O(1) | 获取长度 |

### 3. 代码示例

```python
# 创建
lst = [1, 2, 3, 4, 5]

# 访问和修改
print(lst[0])      # 1
lst[0] = 10        # [10, 2, 3, 4, 5]

# 添加删除
lst.append(6)      # 尾部添加: [10, 2, 3, 4, 5, 6]
lst.pop()          # 尾部删除: 返回 6
lst.insert(1, 20)  # 插入: [10, 20, 2, 3, 4, 5]
lst.pop(1)         # 删除索引1: 返回 20

# 查找
idx = lst.index(3) # 返回 3 的索引: 2

# 切片
sub = lst[1:4]     # [2, 3, 4]

# 排序
lst.sort()         # 原地排序
new_lst = sorted(lst, reverse=True)  # 降序，返回新列表
```

### 4. 应用场景
- ✅ 需要频繁随机访问（O(1)）
- ✅ 主要在尾部添加/删除
- ❌ 频繁在头部/中间插入删除（O(n)）

---

## 二、堆（Heap）

### 1. 基本概念
堆是一种特殊的完全二叉树，分为最大堆和最小堆。
- **最小堆**：父节点 <= 子节点
- **最大堆**：父节点 >= 子节点

Python 的 `heapq` 模块实现的是**最小堆**。

### 2. 常用操作

| 操作 | 代码 | 时间复杂度 | 说明 |
|------|------|-----------|------|
| 创建堆 | `heapq.heapify(lst)` | O(n) | 将列表转为堆 |
| 插入 | `heapq.heappush(heap, x)` | O(log n) | 添加元素 |
| 弹出最小 | `heapq.heappop(heap)` | O(log n) | 删除并返回最小值 |
| 查看最小 | `heap[0]` | O(1) | 不删除 |
| 替换最小 | `heapq.heapreplace(heap, x)` | O(log n) | 弹出最小，插入 x |
| 合并堆 | `heapq.merge(*iterables)` | O(n) | 合并多个有序序列 |
| 获取最大 n 个 | `heapq.nlargest(n, heap)` | O(n log k) | 返回最大的 n 个 |
| 获取最小 n 个 | `heapq.nsmallest(n, heap)` | O(n log k) | 返回最小的 n 个 |

### 3. 代码示例

```python
import heapq

# 创建最小堆
heap = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(heap)  # [1, 1, 2, 3, 5, 9, 4, 6]

# 插入
heapq.heappush(heap, 0)  # [0, 1, 2, 3, 5, 9, 4, 6, 1]

# 弹出最小
min_val = heapq.heappop(heap)  # 返回 0

# 查看最小
print(heap[0])  # 1

# 最大堆（用负数实现）
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
max_val = -heapq.heappop(max_heap)  # 返回 4

# 获取最大 3 个
lst = [3, 1, 4, 1, 5, 9, 2, 6]
largest = heapq.nlargest(3, lst)  # [9, 6, 5]
smallest = heapq.nsmallest(3, lst)  # [1, 1, 2]
```

### 4. 应用场景
- ✅ Top K 问题（最大/最小 K 个元素）
- ✅ 优先队列（任务调度）
- ✅ 合并 K 个有序数组
- ✅ Dijkstra 最短路径算法
- ✅ 数据流的中位数

---

## 三、数组删除元素

### 1. 删除指定值的元素

#### 方法 1：遍历删除（原地修改）
```python
# 删除所有值为 x 的元素
def remove_all(lst, x):
    i = 0
    for j in range(len(lst)):
        if lst[j] != x:
            lst[i] = lst[j]
            i += 1
    del lst[i:]  # 删除尾部多余元素
    return lst

# 示例
lst = [1, 2, 3, 2, 4, 2, 5]
remove_all(lst, 2)  # [1, 3, 4, 5]
```
**时间复杂度：** O(n)  
**空间复杂度：** O(1)

#### 方法 2：列表推导式（创建新列表）
```python
lst = [1, 2, 3, 2, 4, 2, 5]
new_lst = [x for x in lst if x != 2]  # [1, 3, 4, 5]
```
**时间复杂度：** O(n)  
**空间复杂度：** O(n)

#### 方法 3：filter 函数
```python
lst = [1, 2, 3, 2, 4, 2, 5]
new_lst = list(filter(lambda x: x != 2, lst))  # [1, 3, 4, 5]
```

### 2. 删除指定索引的元素

```python
lst = [1, 2, 3, 4, 5]

# 删除索引 i
i = 2
del lst[i]        # [1, 2, 4, 5]
# 或
lst.pop(i)        # 返回 3, lst = [1, 2, 4, 5]
```
**时间复杂度：** O(n-i)，即 O(n)

### 3. 删除多个索引的元素

```python
# 删除索引 1, 3
def remove_indices(lst, indices):
    indices = set(indices)  # 去重
    return [x for i, x in enumerate(lst) if i not in indices]

lst = [1, 2, 3, 4, 5]
new_lst = remove_indices(lst, [1, 3])  # [1, 3, 5]
```

### 4. 删除满足条件的元素

```python
# 删除所有偶数
lst = [1, 2, 3, 4, 5, 6]
new_lst = [x for x in lst if x % 2 != 0]  # [1, 3, 5]

# 删除所有大于 3 的元素
new_lst = [x for x in lst if x <= 3]  # [1, 2, 3]
```

---

## 四、双端队列（Deque）

### 1. 基本概念
双端队列，两端都可以 O(1) 添加删除。

### 2. 常用操作

| 操作 | 代码 | 时间复杂度 | 说明 |
|------|------|-----------|------|
| 创建 | `deque()` | O(1) | 初始化 |
| 右端添加 | `append(x)` | O(1) | 尾部添加 |
| 左端添加 | `appendleft(x)` | O(1) | 头部添加 |
| 右端删除 | `pop()` | O(1) | 尾部删除 |
| 左端删除 | `popleft()` | O(1) | 头部删除 |
| 访问 | `deque[i]` | O(1) | 随机访问 |

### 3. 代码示例

```python
from collections import deque

dq = deque([1, 2, 3])

dq.append(4)        # 右端添加: deque([1, 2, 3, 4])
dq.appendleft(0)    # 左端添加: deque([0, 1, 2, 3, 4])
dq.pop()            # 右端删除: 返回 4
dq.popleft()        # 左端删除: 返回 0
```

### 4. 应用场景
- ✅ 滑动窗口问题
- ✅ BFS 队列
- ✅ 需要两端操作的场景

---

## 五、集合（Set）

### 1. 基本概念
无序不重复元素集合。

### 2. 常用操作

| 操作 | 代码 | 时间复杂度 | 说明 |
|------|------|-----------|------|
| 创建 | `s = set()` | O(1) | 初始化 |
| 添加 | `s.add(x)` | O(1) | 添加元素 |
| 删除 | `s.remove(x)` | O(1) | 删除元素（不存在报错）|
| 删除 | `s.discard(x)` | O(1) | 删除元素（不存在不报错）|
| 查找 | `x in s` | O(1) | 判断是否存在 |
| 交集 | `s1 & s2` | O(min(len1, len2)) | 交集 |
| 并集 | `s1 \| s2` | O(len1 + len2) | 并集 |
| 差集 | `s1 - s2` | O(len1) | 差集 |

### 3. 代码示例

```python
s = {1, 2, 3}
s.add(4)        # {1, 2, 3, 4}
s.remove(2)     # {1, 3, 4}
print(3 in s)   # True

# 去重
lst = [1, 2, 2, 3, 3, 3]
unique = list(set(lst))  # [1, 2, 3]（无序）
```

### 4. 应用场景
- ✅ 去重
- ✅ 快速查找（O(1)）
- ✅ 集合运算

---

## 六、字典（Dict）

### 1. 基本概念
键值对存储，哈希表实现。

### 2. 常用操作

| 操作 | 代码 | 时间复杂度 | 说明 |
|------|------|-----------|------|
| 创建 | `d = {}` | O(1) | 初始化 |
| 添加/修改 | `d[key] = value` | O(1) | 插入或更新 |
| 查找 | `d[key]` / `d.get(key)` | O(1) | 获取值 |
| 删除 | `del d[key]` | O(1) | 删除键值对 |
| 判断存在 | `key in d` | O(1) | 判断 key 是否存在 |

### 3. 代码示例

```python
d = {'a': 1, 'b': 2}
d['c'] = 3          # 添加
print(d['a'])       # 1
del d['b']          # 删除
print('a' in d)     # True

# 遍历
for key, value in d.items():
    print(key, value)
```

### 4. 应用场景
- ✅ 快速查找（O(1)）
- ✅ 计数（Counter）
- ✅ 缓存（Memoization）

---

## 七、复杂度对比总结

| 数据结构 | 访问 | 搜索 | 插入 | 删除 | 特点 |
|---------|------|------|------|------|------|
| 数组/列表 | O(1) | O(n) | O(n) | O(n) | 随机访问快 |
| 链表 | O(n) | O(n) | O(1) | O(1) | 插入删除快 |
| 哈希表/字典 | O(1) | O(1) | O(1) | O(1) | 查找快 |
| 堆 | O(1)最小 | - | O(log n) | O(log n) | 取极值快 |
| 集合 | - | O(1) | O(1) | O(1) | 去重、判断存在 |

---

## 八、选择指南

| 场景 | 推荐数据结构 | 原因 |
|------|-------------|------|
| 频繁随机访问 | 列表 | O(1) 访问 |
| 频繁两端操作 | 双端队列 | O(1) 两端操作 |
| 频繁查找 | 字典/集合 | O(1) 查找 |
| 取最大/最小 | 堆 | O(1) 取极值 |
| 去重 | 集合 | 自动去重 |
| 保持插入顺序 | 列表/双端队列 | 有序 |
| 需要排序 | 列表 + sort | 灵活 |

---

*文档整理时间：2026-04-09*