Linked lists · 链表
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
用指针连起来的节点
- 链表是一串叫做节点的小结构体,散落在堆的各处。
- 每个节点存一个值,以及一个指向下一个节点的指针。顺着指针就能遍历链表。
- 和数组不同,链表可以一次加一个节点,而不用移动其他节点。
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
自引用的结构体
- 节点是一个包含指向自己类型指针的结构体:
struct Node { int data; struct Node *next; };——data是值,next指向后面那个节点。- 这个
Node在每个起始代码里都替你写好了。最后一个节点的next是NULL。
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
head 与 NULL 结尾
- 一个单独的指针 head 指向第一个节点。从它出发就能到达其余的节点。
- 最后一个节点指向
NULL,它标记链表的结尾。 - 空链表就是
head == NULL—— 一个节点都没有。
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
在头部加一个节点
- 要在头部添加,新建一个节点,把它的
next指向旧的 head,再把这个新节点作为新的 head 返回。 - 这很快 —— 它不碰任何其他节点。
- 因为 head 变了,函数要返回新的 head,调用者把它存起来。
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
常见错误
- 绝不能弄丢
head指针,否则整条链表都找不到。 - 释放每个节点;最后一个节点指向
NULL。
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
现在轮到你了
- 用一个
cur指针和cur = cur->next遍历链表,在NULL处停止。 - 新节点来自
malloc(sizeof(Node));检查器会释放整个链表。不要自己写main。
Nodes and pointers · 节点与指针
Each node points to the next; insert/delete by re-linking. · 每个节点指向下一个;通过重新连接来插入/删除。
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not · 不 write a main. · 完成 int length(const Node *head),让它数出链表里有多少个节点(空链表为 0)。用 ->next 遍历直到 NULL。Node 类型已给出。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not · 不 write a main. · 完成 int sum_list(const Node *head),让它返回每个节点 data 的总和(空链表为 0)。Node 类型已给出。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not · 不 write a main. · 完成 Node *push_front(Node *head, int value),让它用 malloc 新建一个节点,把它的 next 指向旧的 head,并把它作为新的 head 返回。检查器会释放链表。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。