Linked lists · 链表
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
中文
由链接串起的节点
- 链表(linked list)是一串节点(node)。
- 每个节点存放一份数据和指向下一个节点的链接。
- 最后一个节点链接到
None,表示结束。
English
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
中文
节点就是一条小记录
- 我们可以用一个字典存放一个节点:
{"data": ..., "next": ...}。 "data"存放值;"next"存放下一个节点(或None)。- 第一个节点叫作链表的头(head)。
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
English
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
中文
遍历链表
- 从头节点开始,沿着每个
"next"链接走。 - 当走到
None时停下。 - 这种访问每个节点的过程叫作遍历(traversal)。
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
English
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
中文
为什么用链表?
- 你可以通过改变链接来插入或删除节点 —— 不用移动其他元素。
- 而数组在改动后必须把后面的每个元素都挪动一遍。
- 但链表没有索引:要找到第 5 个元素,必须从头一个个走过去。
English
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
中文
用剑桥伪代码表示
- 考试把节点存在一个数组里;
Next是下一个节点的索引,NULL表示结束。
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
English
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
中文
常见错误
- 绝不能弄丢
head指针,否则整条链表都找不到。 - 最后一个节点指向
None。
English
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
中文
现在轮到你
- 一个节点就是字典
{"data": ..., "next": ...}。沿着"next"遍历这条链。 - 按检查答案来测试你的代码。
Explore · 探索
Nodes linked by pointers · 用指针连起来的节点
Each node points to the next; you insert/delete by re-linking. · 每个节点指向下一个;通过重新连接来插入/删除。
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · 用字典构建一个链表 1 → 2 → 3。创建三个节点,把每个节点链接到下一个,并让 head 指向第一个节点。最后一个节点的 "next" 必须是 None。
Click Run to see the output here. · 点击“运行”查看此处输出。
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · 从 head 开始遍历链表,把每个节点的 "data" 加起来。把总和存进 total(答案是 60)。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write length(head) that returns · 返回值 how many nodes are in the linked list. An empty list (head is None) has length 0. · 编写 length(head),返回链表中有多少个节点。空链表(head 是 None)的长度为 0。
Click Run to see the output here. · 点击“运行”查看此处输出。