Linked lists
C Programming Lesson 17 2:21 English narration · English + 中文 subtitles burned in
Chapters
Transcript
An array is one solid block.
数组是一整块连续的内存。
A linked list is the opposite: small structs called nodes, scattered anywhere in the heap, each one holding a value and a pointer to the next.
链表恰好相反： 一个个叫做“节点”的小结构体，散落在堆的任何地方， 每个节点里装着一个值，和一个指向下一个节点的指针。
Follow the pointers and you have the sequence.
顺着这些指针走，你就得到了这个序列。
The declaration looks strange the first time — a struct that contains a pointer to its own type — but that is exactly what a chain needs, and it is the entire trick.
第一次看到那个声明会觉得很奇怪—— 一个结构体里包含指向它自己这个类型的指针—— 但链条需要的正是这个，而这就是全部的诀窍。
A list is reached through a single pointer called the head.
访问一个链表，靠的是一个叫 head 的指针。
It is the only way in, so if you overwrite it before you are done, every node behind it becomes unreachable — the memory is still allocated, but nothing in your program can find it again.
它是唯一的入口， 所以如果你在用完之前就把它覆盖掉， 它后面的每一个节点都变得无法到达—— 内存还占着，但你的程序再也找不到它们了。
At the other end, the last node's next is null, and that marks the end.
在另一头，最后一个节点的 next 是 NULL，这就标出了结尾。
Which gives you the empty list for free: head is null, and there are no nodes at all.
空链表也就顺带有了定义：head 是 NULL，一个节点也没有。
You cannot index a list.
链表不能用下标访问。
There is no node number five; there is only "follow next, again".
没有“第 5 号节点”这回事；只有“再跟着 next 走一步”。
So every list function has the same shape: a cursor that starts at the head, does its job, and then takes one step to the next node.
所以每一个链表函数都是同一个形状： 一个游标从 head 出发，做完它该做的事， 然后往下一个节点走一步。
When the last node hands over its next, cur becomes null and the loop ends.
当最后一个节点交出它的 next 时，cur 变成 NULL，循环结束。
That is counting, summing, printing and searching — all four are this loop with a different line in the middle.
计数、求和、打印、查找—— 这四件事都是同一个循环，只是中间那一行不同。
The third task adds a node at the front, and this is where a list beats an array outright: nothing else has to move.
第三道题是在链表最前面加一个节点， 而这正是链表完胜数组的地方：其它任何节点都不必移动。
Make a new node with malloc and fill in its data.
用 malloc 造一个新节点，把它的 data 填好。
Point it at the old head, so the rest of the chain hangs off it unbroken.
把它的 next 指向原来的 head， 这样整条链就完好地挂在它后面。
Then return the new head, and the caller stores it.
然后返回这个新的头，由调用者把它存下来。
Note what did not happen — no other node was touched, however long the list is.
注意没有发生的事—— 不管这个链表有多长，其它节点一个都没被碰过。
Four things to take with you.
带走四点。
One: a node holds a value and a pointer to the next.
第一：一个节点装着一个值和一个指向下一个节点的指针。
Two: head is the way in, and null is the way out.
第二：head 是入口，NULL 是出口。
Three: walk it with a cursor, stepping until it reaches null.
第三：用一个游标遍历，一步步走到它变成 NULL 为止。
Four: adding at the front returns the new head.
第四：在最前面插入，要返回新的头。
Now do the three tasks — the first two are the same walk, counting and then totalling.
现在去做那三道题—— 前两题是同一个遍历，一个数个数，一个求总和。