Linked lists
Python for A-Level CS Lesson 6 2:05 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A linked list is a chain of nodes, and each node holds two things: a piece of data, and a link to the next node.
链表是一串节点，而每个节点装着两样东西： 一份数据，和一个指向下一个节点的链接。
Here a node is just a dictionary with those two keys.
这里，一个节点就是一个带这两个键的字典。
Notice the order in which the chain is built from the back: the last node first, because you cannot point at a node that does not exist yet.
注意这条链是从后往前建起来的： 先建最后一个节点，因为你没法指向一个还不存在的节点。
Then head names the first one.
最后，head 指出第一个是谁。
You cannot index a linked list.
链表不能用下标访问。
There is no node number two; there is only follow the link, again.
没有"第 2 号节点"这回事；只有"再顺着链接走一步"。
So every operation has the same shape: a cursor starting at the head, doing its job, then stepping to whatever the link points at.
所以每一个操作都是同一个形状： 一个游标从 head 出发，做完它该做的事， 然后走到链接指向的地方。
When the last node hands over its link, cur becomes None and the loop ends.
当最后一个节点交出它的链接时，cur 变成 None，循环结束。
Here is the A-Level question: why would you ever use this instead of a list?
这就是 A-Level 要问的问题：你为什么会用它，而不用普通的列表？
Insert something in the middle of an array and every item after the gap has to shift along one place.
在数组中间插入一个元素，缺口后面的每一个元素都要往后挪一格。
Insert it into a linked list and you change two links — the new node points at what follows, and the node before points at the new one.
而在链表里插入，你只改两条链接—— 新节点指向后面那个，前面那个指向新节点。
Nothing else moves at all, however long the chain is.
不管这条链有多长，其它任何东西都不用动。
But nothing is free.
但天下没有免费的午餐。
An array can jump straight to item five hundred, because the position is arithmetic.
数组可以直接跳到第 500 个元素，因为位置是算出来的。
A linked list has to follow every link on the way there, one at a time.
链表必须一步一步地顺着每一条链接走过去。
Fast to insert, slow to reach — that is the trade the exam wants you to state, and it is why the answer to "which data structure" is always "it depends what you do most".
插入快，访问慢——这正是考试要你说出来的那个取舍， 也是为什么"该用哪种数据结构"的答案永远是"看你做得最多的是什么"。
Four things to take with you.
带走四点。
One: a node holds a value and a link to the next node.
第一：一个节点装着一个值，和一个指向下一个节点的链接。
Two: walk it from the head until the link is None.
第二：从 head 出发遍历，直到链接为 None。
Three: inserting changes two links and moves nothing.
第三：插入只改两条链接，什么都不用搬。
Four: but reaching item n means following n links.
第四：但要到达第 n 个元素，就得跟着走 n 条链接。
Now do the three tasks.
现在去做那三道题。