数组、链表、栈、队列和哈希表：按操作选择结构

问题与目标

同一批数据换一种组织方式，查找、插入和删除成本可能完全不同。本篇不追求手写完整容器，而是从操作需求选择 Python 中合适的结构。

完成标准：能比较五类结构的访问特点，并用栈、队列和哈希表实现一个任务处理案例。

数据结构的选择起点不是名称，而是最频繁的操作：按位置访问、两端进出、后进先出，还是按键查找。先确定操作模式，通常比先选容器再迁就需求更稳妥。

核心概念

Python list 是动态数组，不是链表。从头部 pop(0) 会移动后续元素，队列应使用 deque.popleft()。哈希键必须可哈希；列表和字典不能直接作为键。

操作成本对照

数据结构常组合使用，而不是只能选一个。任务队列负责顺序，字典负责按 ID 查找，集合负责去重，列表保存展示顺序。组合的代价是修改时必须维护一致性。

栈和队列的边界

栈适合“最近发生的先处理”，例如撤销和括号匹配；队列适合“先到先处理”，例如批任务调度。优先队列则按优先级而非到达时间取出，Python 可用 heapq。

import heapq

priority_tasks = [(2, "normal"), (1, "urgent"), (3, "later")]
heapq.heapify(priority_tasks)
while priority_tasks:
    print(heapq.heappop(priority_tasks))

元组先比较优先级，再比较后续字段。若后续对象不可比较，可加入唯一递增序号避免同优先级时报错。

可运行实现

案例同时维护待处理队列、按 ID 索引和撤销栈：

from collections import deque


tasks = [
    {"id": 1, "title": "load data"},
    {"id": 2, "title": "clean data"},
    {"id": 3, "title": "draw chart"},
]

task_by_id = {task["id"]: task for task in tasks}
pending = deque(task["id"] for task in tasks)
completed: list[int] = []


def complete_next() -> dict[str, object]:
    if not pending:
        raise LookupError("没有待处理任务")
    task_id = pending.popleft()
    completed.append(task_id)
    return task_by_id[task_id]


def undo() -> dict[str, object]:
    if not completed:
        raise LookupError("没有可撤销任务")
    task_id = completed.pop()
    pending.appendleft(task_id)
    return task_by_id[task_id]


print(complete_next())
print(complete_next())
print("undo:", undo())
print("pending:", list(pending))

输入是三条任务，输出显示处理顺序、撤销对象和剩余队列。字典按 ID 平均快速定位，队列从左侧取任务，列表末尾承担撤销栈。

链表适合理解节点关系，最小节点可写为：

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: "Node | None" = None

但 Python 业务代码很少仅为头部插删而自建链表；对象开销和遍历成本往往抵消理论优势。

哈希表为什么快

字典先对键计算哈希值，再定位存储位置；哈希冲突由内部机制处理。相等对象必须具有相同哈希值，因此可变内容不适合作为键。tuple 只有在内部元素都可哈希时才能作为键。

进一步检查可以从一个实际需求出发，列出最频繁的三种操作，再说明为何选 list、deque、dict 或组合结构，而不是只写结构定义。

进一步验证

• 将队列中的任务扩展到一万条，对比 pop(0) 与 popleft() 的增长趋势。
• 增加“按 ID 取消未处理任务”需求，说明队列与字典的状态如何保持一致。
• 为撤销栈补上空栈测试，并明确返回 None 还是抛出异常。

最终产出一张“主要操作—候选结构—选择理由”对照表，而不是孤立记忆容器名称。

常见问题与排查

• 用 list.pop(0) 实现大队列：改用 deque。
• 用列表反复查找 ID：建立字典索引，但修改原数据时同步维护索引。
• 认为字典天然有序排序：它保留插入顺序，但不会按键大小自动排序。
• 自定义哈希对象后内容还会改变：可变键会破坏定位，应使用不可变值。
• 只看单次操作：结构选择要看完整工作负载，包括遍历频率和内存。

小结

数据结构选择来自主要操作：按位置访问用列表，排队用 deque，撤销用栈，按键定位和去重用字典或集合。理解链表有助于认识引用关系，但不必为了“学过”而替代标准容器。