此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
由链接串起的节点
- 链表(linked list)是一串节点(node)。
- 每个节点存放一份数据和指向下一个节点的链接。
- 最后一个节点链接到
None,表示结束。
节点就是一条小记录
- 我们可以用一个字典存放一个节点:
{"data": ..., "next": ...}。 "data"存放值;"next"存放下一个节点(或None)。- 第一个节点叫作链表的头(head)。
English
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
遍历链表
- 从头节点开始,沿着每个
"next"链接走。 - 当走到
None时停下。 - 这种访问每个节点的过程叫作遍历(traversal)。
English
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
为什么用链表?
- 你可以通过改变链接来插入或删除节点 —— 不用移动其他元素。
- 而数组在改动后必须把后面的每个元素都挪动一遍。
- 但链表没有索引:要找到第 5 个元素,必须从头一个个走过去。
用剑桥伪代码表示
- 考试把节点存在一个数组里;
NextIndex是下一个节点的索引,NULL表示结束。
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
常见错误
- 绝不能弄丢
head指针,否则整条链表都找不到。 - 最后一个节点指向
None。
现在轮到你
- 一个节点就是字典
{"data": ..., "next": ...}。沿着"next"遍历这条链。 - 按检查答案来测试你的代码。
探索
用指针连起来的节点
每个节点指向下一个;通过重新连接来插入/删除。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
用字典构建一个链表 1 → 2 → 3。创建三个节点,把每个节点链接到下一个,并让 head 指向第一个节点。最后一个节点的 "next" 必须是 None。
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
从 head 开始遍历链表,把每个节点的 "data" 加起来。把总和存进 total(答案是 60)。
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
编写 length(head),返回链表中有多少个节点。空链表(head 是 None)的长度为 0。
点击“运行”查看此处输出。