3.1 数据结构分类：逻辑关系、存储方式与 Python 容器

1 · 先分清三个问题：关系、存储、操作

逻辑结构回答“元素之间是什么关系”，物理结构回答“这些关系如何存到内存”，操作接口回答“允许怎样使用它”。三者不是三个互斥的箱子。同一个队列，可以用数组或链式结构实现；同一棵树，也可以保存成带引用的节点或数组下标。

本篇对应《Hello 算法》3.1，不提前代替数组、链表、树和哈希表的后续专章。目标是建立分类坐标系：看到一个 Python 容器或自己的测试系统，能说清关系、表示及代价，而不只背名称。

你可以接着 2.6 复杂度分析练习阅读：上一章数“做多少工作、同时保留多少状态”，这一节解释为何表示方式会改变这些成本。本文是按课程自动编写的讲解，不代表你已讨论、掌握或完成复盘。

2 · 逻辑结构：看的是关系，不是屏幕上的排列

线性序列有明确前后：在普通非循环链中，除首尾边界外，每个元素各有一个直接前驱和直接后继。例如测试任务按既定顺序运行：连接设备、创建卷、执行 I/O。树刻画层级：一个父节点可连接多个子节点，非根节点有唯一父节点。图描述更一般的连接，允许共享依赖、多路径以及环。

“一对一、一对多、多对多”描述的是关系形态，不是每个节点必须刚好连接几个元素。单节点树也是树；树也可退化成一条链。应看结构整体的约束，不能只看某一个样本长什么样。

3 · 为什么原书的哈希表会出现在不止一类？

原书的分类列表把哈希表同时放进线性、非线性以及树形相关分类。这提醒我们：它在这里结合了抽象关系和具体实现形态，不能直接当成互斥、严格的类型划分。

更稳妥的表述是：字典/映射定义按键访问的语义；哈希表是一类实现；哈希冲突可以通过不同策略处理。有的实现把桶中元素连成链，有的采用开放寻址，有的在特定条件下采用树。不能由“用了哈希表”推出“它是一棵树”，也不能推出“Python dict 的冲突处理一定是链表”。Python 官方 FAQ 将 CPython dict 说明为可调整大小的哈希表。

后续遇到分类冲突，先问：此处讨论接口、元素关系，还是某个版本的底层布局？这比争论一个名称只能属于哪一格更有用。

4 · 物理结构：连续的是哪一层？

教材以数组和链表作为两种基本表示：数组把等宽槽位排成一段连续空间，链式表示把节点通过引用连接起来。连续存储可由起点与偏移计算槽位；链式访问下一项要先取得当前节点中的 next。

这里的连续通常指进程可见的虚拟地址空间，并非保证底层物理 RAM 页相邻。教材用内存表格帮助入门，不应把类比扩大成“所有进程共享一套可直接读写的地址”。常见操作系统通过虚拟内存和权限隔离进程；共享内存又是另外一种显式机制。数据结构课程里的“物理结构”这个术语，不等同于操作系统里的“物理地址”。

数组与链接是本章的基础模型，不是声称一切实现都必须是纯数组或逐个节点分配的链表。分块队列等混合结构正体现两者组合。

5 · 同一个线性序列：列表访问与链式访问

下面用三个节点表示同一顺序。Node 对象只保留 value 和 next；逻辑关系由 next 决定，不由创建时间或 id 的大小决定。chain_at 为教学返回“结果、走过多少条链接”，不测耗时。索引契约是非负整数；示例对越界和负数显式抛 IndexError，不模仿 list 的负索引语义。

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def build_chain(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head

def chain_values(head):
    values = []
    while head is not None:
        values.append(head.value)
        head = head.next
    return values

def chain_at(head, index):
    if index < 0:
        raise IndexError("negative index is not supported")
    hops = 0
    while head is not None and hops < index:
        head = head.next
        hops += 1
    if head is None:
        raise IndexError("index out of range")
    return head.value, hops

cases = ["connect", "create_volume", "run_io"]
head = build_chain(cases)
print(chain_values(head))
for i in range(len(cases)):
    print(i, cases[i], chain_at(head, i))
for i in (-1, 3):
    try:
        chain_at(head, i)
    except IndexError:
        print(i, "IndexError")

6 · 顺着执行轨迹解释访问成本

在固定大小索引和槽位模型下，数组按索引访问 Θ(1)；单链表从头定位第 i 项要 Θ(i+1) 时间，最坏 Θ(n)。这里“0 次跳转”也有判定和返回工作，不能说时间为零。空链表 head=None，访问任何索引均越界；只做一次从头到尾遍历时，两种表示都可为 Θ(n)。

chain_values 额外建立输出列表，输出空间 Θ(n)，辅助游标空间 Θ(1)；build_chain 创建 n 个节点，结果本身也占 Θ(n) 空间。示例是无环链，若自行让尾节点指回前面，chain_values 会无限循环；生产接口要明确无环契约，或另加环检测。这里不把普通链遍历误称为通用图遍历。

7 · “链表插入 O(1)”必须先说明定位成本

假设已持有前驱 a 的引用，在 a 后插入 x：先让 x.next 指向旧后继，再令 a.next 指向 x。仅改固定数量引用。下面定义一个独立可运行的小链表，拒绝空前驱；不是“在整个链表按下标插入”的完整 API。

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def chain_values(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

def insert_after(previous, value):
    if previous is None:
        raise ValueError("a predecessor node is required")
    new_node = Node(value, previous.next)
    previous.next = new_node
    return new_node

tail = Node("run_io")
head = Node("connect", tail)
inserted = insert_after(head, "create_volume")
print(chain_values(head))
print(inserted.next is tail)
last = insert_after(tail, "cleanup")
print(chain_values(head))
print(last.next is None)

8 · 插入的状态表与反例

若先覆盖 a.next，之后再写 x.next=a.next，就会让 x 指向自己并丢失原后缀入口。验证不能只检查头两个值，还应检查旧后缀对象身份与可达性。

已知前驱后的链接变更为 Θ(1)，但从 head 按下标找前驱仍为 Θ(n)，所以整次插入最坏仍为 Θ(n)。删除也类似：单链表仅有待删节点引用，并不自动拥有前驱；不能笼统承诺删除任何节点都 O(1)。链表还需额外节点和引用，缓存局部性常不如连续槽位；这些是工程权衡，本文没有用一次微基准证明谁总是更快。

9 · 栈与队列：约束操作，不唯一决定底层表示

栈是 LIFO，队列是 FIFO。将相同任务放进去，取出顺序不同。这是操作语义，不是“栈必须连续、队列必须分散”。Python 官方教程展示 list 末端 append/pop 用作栈，并推荐 deque 用作两端操作的队列。

from collections import deque

def drain_stack(values):
    stack = list(values)
    result = []
    while stack:
        result.append(stack.pop())
    return result

def drain_queue(values):
    queue = deque(values)
    result = []
    while queue:
        result.append(queue.popleft())
    return result

tasks = ["connect", "create_volume", "run_io"]
print("stack:", drain_stack(tasks))
print("queue:", drain_queue(tasks))
print("empty:", drain_stack([]), drain_queue([]))
empty_errors = []
for operation in (lambda: [].pop(), lambda: deque().popleft()):
    try:
        operation()
    except IndexError as error:
        empty_errors.append(type(error).__name__)
print(empty_errors)

10 · 同样 FIFO，为什么 list.pop(0) 要谨慎？

list.pop(0) 也能实现 FIFO，语义未必错；问题是移除头部后，后续引用槽位要前移。连续出队 n 项需要移动 (n−1)+(n−2)+…+1=Θ(n²) 个槽位。deque 的两端添加/移除在官方文档中为近似 O(1)，因此适合这个操作模式。本文 drain_queue 还会构造队列与结果，整体时间 Θ(n)，辅助队列和输出均为 Θ(n)。

反过来，不能因为 deque 两端高效就推断其中间随机访问也与 list 一样。数组队列还可以采用头下标或环形缓冲区避免每次移动，这也是“接口相同、实现不同”。并发生产者/消费者、阻塞、任务完成通知又是额外需求；普通 deque 示例不是完整的并发任务调度系统。

11 · 用数值缓冲区理解等宽槽位与偏移

下面使用 array('i') 保存 C 有符号整数，以 memoryview 查看元素宽度和连续性；不依赖某台机器的整数恰好为 4 字节。输出中的偏移是用 itemsize 推导的相对字节偏移，不是通过 id() 测出的元素地址。

from array import array

values = array("i", [10, 20, 30])
view = memoryview(values)
offsets = [i * view.itemsize for i in range(len(view))]
print("values:", list(view))
print("one-dimensional contiguous:", view.ndim == 1 and view.c_contiguous)
print("offsets in item widths:", [x // view.itemsize for x in offsets])
print("buffer size matches:", view.nbytes == len(values) * view.itemsize)
try:
    values.append(1.5)
except TypeError:
    print("float:", "TypeError")

12 · CPython list：连续的是引用槽位，不一定是对象本体

CPython 官方 FAQ 明确说明 list 使用可变长的连续对象引用数组，而不是 Lisp 式链表。因此 nums=[10,20,30] 不能直接画成三个内联 C 整数。列表对象、内部引用数组、元素对象是不同层；一个对象还可被多个槽位引用。

shared = {"status": "pending"}
items = [shared, shared, {"status": "pending"}]
alias = items
print("same outer:", alias is items)
print("shared targets:", items[0] is items[1], items[0] is items[2])
items[0]["status"] = "passed"
print([item["status"] for item in items])
items[2] = {"status": "failed"}
print([item["status"] for item in alias])

13 · 长度能变化，不等于链表；id 也不是布局证据

上例先修改共享字典，因此前两个位置都读到 passed；再替换第 2 号槽位的绑定，alias 因为仍指向同一外层列表，也看见 failed。这可关联 对象修改与重新绑定：名字、槽位、对象之间不是“一个变量拥有一块独占值”的关系。

教材把固定长度数组称为静态结构，把可增长链表称为动态结构，这是基础模型；CPython list 是动态数组，array.array 也支持增删，因此长度可变 ≠ 必须链式存储。扩容可能换内部缓冲区，不等于必须换外层 list 对象；具体增长比例是实现细节，不在本文保证范围内。

id(x) 的语言语义是对象生命周期内的身份，CPython 才以对象地址实现。id(items) 不是内部引用数组的起始地址；id(items[i]) 不是第 i 个槽位地址。打印它们的差值不能证明或否定槽位连续。本文只用 is 核对共享关系，布局结论依据官方实现说明；没有进行原始指针读写或伪造内存实测。

14 · 非线性的树，也可以存进线性数组

用层序数组表示一棵完整的三节点二叉树，索引 i 的左、右孩子为 2i+1、2i+2。下面只是演示表示规则；不是所有稀疏树都适合这种表示，也不是堆必须把节点真的摆成树枝。

tree = ["suite", "smoke", "regression"]
relations = []
for parent in range(len(tree)):
    for child in (2 * parent + 1, 2 * parent + 2):
        if child < len(tree):
            relations.append((tree[parent], tree[child]))
print(relations)
print("leaf children:", [
    child for child in (3, 4) if child < len(tree)
])

15 · 有序字典与邻接表：容器顺序不是业务关系

Python dict 保留插入顺序，但顺序与排序、链式后继、图中的边都不是一回事。更新已有键不会把它移到末尾；新增键才加入末尾。下面还用“字典 → 邻接列表”保存依赖图，图的边来自列表内容，而非字典键的排列。

results = {"case_b": "failed", "case_a": "pending"}
results["case_a"] = "passed"
results["case_c"] = "skipped"
missing = results.get("missing", "unknown")
print("iteration:", list(results))
print("lookup:", results["case_a"], missing)
dependencies = {
    "run_io": ["connect", "create_volume"],
    "create_volume": ["connect"],
    "connect": [],
}
edge_count = sum(len(neighbors) for neighbors in dependencies.values())
print("nodes / edges:", len(dependencies), edge_count)
print("shared dependency:", "connect" in dependencies["run_io"]
      and "connect" in dependencies["create_volume"])

16 · 面向工程选结构：先写操作负载，再谈效率

常说哈希查找平均 O(1)，依赖合理分布、负载管理，以及把键的 hash/比较视为固定成本；不是无条件最坏 O(1)。连续槽位通常有利于缓存，但真实延迟还受对象间接访问、分配、规模和操作比例影响。选型需要有代表性的工作负载与内存观测，不由一次小样本耗时决定。

本节仅验证表示与行为。涉及设备拓扑或服务依赖时，建议先明确：节点身份如何去重，边是否有方向，是否允许环，遍历结果要顺序还是集合，再选容器。

17 · 可自行核验的验证策略

七段程序各在独立 Python 子进程运行，逐字比对展示输出。额外测试从文章代码读取真正的函数，而不另写一份“被测实现”：链长 0…20 的遍历、全部合法索引和负数/越界；链长 1…11 的每个前驱插入，核对后缀对象身份；栈/队列 0…20 长度与空操作；缓冲区连续性、元素宽度和字节数关系；共享对象与外层别名；字典更新顺序及缺失键默认值。

这些是确定性行为检查。用更广输入与独立预期增加覆盖比重复同一输入更有意义；没有把它们说成时延测量、物理 RAM 检测或跨解释器实现证明。链式示例要求无环，索引示例要求整数；浮点索引、可变序列的并发改动等不属于它们的输入契约。

18 · 十道复盘题与参考答案

以下为建议自测，不会自动记作用户已复盘。先给出推理，再展开答案。

19 · 回到目录：下一节按同一选择器推进

这一节建立“逻辑关系—存储表示—操作接口”的坐标系。接下来按目录进入 3.2 基本数据类型，再理解整数、浮点数、字符等值的表示。具体发布进度以 全书覆盖表为准；学习地图中的文章关联表示内容已提供，不代表学习者已掌握。

20 · 来源、改动说明与许可

主题与分类框架依据 krahets《Hello 算法》3.1 数据结构分类（2026-10-20 阅读核对）。本文重新组织讲解、自行编写七段 Python 程序、状态表与测试；补充操作接口层、Python 引用槽位、虚拟地址边界、定位成本、哈希分类限制与误区反例，并未逐字复制原书正文或插图。与原书相关的改编文字采用 CC BY-NC-SA 4.0，保留作者署名、来源、非商业与相同方式共享要求；不改变站点其他内容与源码的许可。

Python 官方依据：CPython list 与 dict 实现说明、列表栈和队列、deque 两端操作、array 元素宽度、memoryview 缓冲区视图、dict 插入顺序和 id 语义与实现边界。正文将实现事实、教材简化模型与工程建议分别说明；运行证据只支持所测试的行为。