📚 GCSE Edexcel Computer Science: Linked Lists | GCSE Edexcel 计算机：链表 考点精讲
A linked list is a dynamic data structure used to store a collection of items. Unlike arrays, the elements are not stored in contiguous memory locations. Instead, each element (called a node) contains the data and a reference (or pointer) to the next node in the sequence. Understanding linked lists is a core part of the Edexcel GCSE Computer Science specification, and you need to be able to explain how they work, compare them with arrays, and trace algorithms that manipulate them.
链表是一种动态数据结构，用于存储数据集合。与数组不同，链表中的元素并不存储在连续的内存位置中。每个元素（称为节点）包含数据部分和一个指向序列中下一个节点的引用（或指针）。理解链表是Edexcel GCSE计算机科学课程的核心内容，你需要能够解释链表的工作原理、与数组进行比较，并能追踪操作链表的算法。
1. What Is a Linked List? | 什么是链表？
A linked list is a sequence of nodes where each node stores data and a link to the next node. The first node is called the head, and the last node points to null (or None) to indicate the end of the list. This structure allows efficient insertion and deletion of nodes because you only need to update the pointers, without shifting other elements as you would in an array.
链表是节点的序列，每个节点存储数据以及指向下一个节点的链接。第一个节点称为头节点，最后一个节点指向 null（或 None）以标记列表的结尾。这种结构允许高效地插入和删除节点，因为只需更新指针，无需像数组那样移动其他元素。
A node is a record consisting of at least two fields: data and pointer. For example, if a node stores an integer and a pointer, we can visualise it as a box with two compartments. In pseudocode, a node might be defined as: Node = {data, next} where next holds the reference to the following node.
节点是一个至少包含两个字段的记录：数据和指针。例如，一个存储整数和指针的节点，可以想象成一个有两个隔间的盒子。在伪代码中，节点可以定义为：Node = {data, next}，其中 next 保存对下一个节点的引用。
2. Visualising a Linked List | 可视化链表
A typical diagram of a linked list shows nodes with arrows connecting them. The head pointer points to the first node. The last node's pointer field is drawn with a diagonal line or the word 'null'. It's important to read and draw such diagrams for your exam. Each arrow represents the address of the next node in memory.
链表的典型图示中，节点之间通过箭头相连。头指针指向第一个节点，最后一个节点的指针区域画一条斜线或标注“null”。考试中需要能够阅读和绘制此类示意图。每个箭头代表下一个节点在内存中的地址。
e with data 5). Node at 200 stores data=5 and next=350. Node at 350 stores data=12 and next=420. Node at 420 stores data=8 and next=null.
考虑一个存储数值 5、12、8 的链表。为了说明，内存地址是任意的：头指针存放地址 200（即数据为5的节点的位置）。地址 200 处的节点存储 data=5 和 next=350。地址 350 处的节点存储 data=12 和 next=420。地址 420 处的节点存储 data=8 和 next=null。
3. Creating and Initialising a Linked List | 创建并初始化链表
To create an empty linked list, you set the head pointer to null. To add the first node, you allocate memory for it, set its data, and set its next to null. Then make the head point to this new node. In some implementations, you use a separate 'tail' pointer to speed up adding to the end, but for GCSE, head is the main reference.
要创建一个空链表，需要将头指针设置为 null。要添加第一个节点，先为其分配内存，设置数据，并将其 next 设为 null，然后让头指针指向这个新节点。在某些实现中，会使用额外的尾指针以加快在末尾添加的速度，但对于 GCSE 而言，头指针是主要的引用。
Pseudocode for creating a list with one node: head = new Node(data_value, null). In a trace table, you would record the value of head as a memory address (like 100) and the fields of each node.
创建一个只有一个节点的链表的伪代码：head = new Node(data_value, null)。在追踪表中，你将把 head 的值记录为一个内存地址（如 100）以及每个节点的各个字段。
4. Traversing a Linked List | 遍历链表
Traversal means visiting each node in order, starting from the head. You use a temporary pointer, often called current, to move along the list. A while loop continues until current becomes null. This is essential for searching, counting, or outputting the data.
遍历是指从链表头开始，按顺序访问每个节点。使用一个临时指针（通常称为 current）沿链表移动。while 循环持续进行，直到 current 变为 null。这对于搜索、计数或输出数据至关重要。
Start with
current = head.从
current = head开始。While
current != null: processcurrent.data; move tocurrent.next.当
current != null时：处理current.data；移动到current.next。
A typical traversal algorithm to print all items would have complexity O(n) where n is the number of nodes. Unlike an array, you cannot directly access an element by index; you must start from the head and follow links.
打印所有元素的典型遍历算法复杂度为 O(n)，其中 n 是节点数。与数组不同，你不能通过索引直接访问元素；必须从头节点开始并沿着链接前进。
5. Inserting a Node | 插入节点
Insertion in a linked list is efficient if you have a reference to the node just before the insertion point. For example, to insert after a given node X, create a new node, set its next to X.next, then set X.next to the new node. This is O(1). For the exam, you must be able to trace insertion at the beginning, in the middle, and at the end.
如果你有插入位置之前节点的引用，链表的插入操作是高效的。例如，要在给定节点 X 后插入，创建新节点，将其 next 设置为 X.next，然后将 X.next 设置为新节点。这是 O(1) 操作。考试中，你需要能够追踪在链表开头、中间和末尾的插入过程。
Insert at front:
new_node.next = head; head = new_node.插入到开头：
new_node.next = head; head = new_node。Insert at end: traverse to the last node (where next == null), then set
last.next = new_nodeandnew_node.next = null.插入到末尾：遍历到最后一个节点（其 next == null），然后设置
last.next = new_node和new_node.next = null。Insert in middle: given previous node,
new_node.next = prev.next; prev.next = new_node.插入到中间：给定前一个节点，
new_node.next = prev.next; prev.next = new_node。
6. Deleting a Node | 删除节点
Deleting a node also involves updating pointers. If you want to delete the node immediately after a known node X, you simply set X.next = X.next.next. This bypasses the deleted node, which can then be freed. For deleting the head, you update head = head.next. Tracing deletion steps in pseudocode is a common exam task.
删除节点也包括更新指针。如果想删除已知节点 X 之后的节点，只需设置 X.next = X.next.next。这样绕过了被删除的节点，随后可以将其释放。删除头节点时，更新 head = head.next。在伪代码中追踪删除步骤是常见的考试任务。
Delete head:
head = head.next.删除头节点：
head = head.next。Delete from middle: find previous node, then
prev.next = prev.next.next.从中间删除：找到前一个节点，然后
prev.next = prev.next.next。Delete tail: traverse to the second-last node, set its next to null. This requires a loop that stops when
current.next.next == null.删除尾节点：遍历到倒数第二个节点，将其 next 设为 null。这需要在
current.next.next == null时停止的循环。
7. Searching a Linked List | 搜索链表
A linear search is performed by traversing the list until the target value is found or the end is reached. In the worst case, all nodes are examined. No binary search is possible because linked lists do not support direct access to the middle element without traversing from the head.
线性搜索通过遍历链表直到找到目标值或到达末尾来执行。最坏情况下，需要检查所有节点。链表不支持二分查找，因为如果不从头遍历，就无法直接访问中间元素。
Pseudocode for a search returning true/false: current = head; while current ! f current.data == target then return true; current = current.next; end while; return false.
返回 true/false 的搜索伪代码：current = head; while current ! f current.data == target then return true; current = current.next; end while; return false。
8. Comparison with Arrays | 与数组的比较
Linked lists and arrays each have advantages and disadvantages. This comparison is heavily examined in Edexcel GCSE.
链表和数组各有优缺点，此比较是 Edexcel GCSE 的重要考点。
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Static (fixed size) or dynamic in some languages, but contiguous | Dynamic (grows/shrinks), non-contiguous |
| Direct access | Fast O(1) – index-based | Not possible – must traverse O(n) |
| Insertion/Deletion | Slower O(n) – shifting required | O(1) if pointer to node known, otherwise O(n) to find position |
| Memory overhead | No extra pointers | Extra memory for each pointer |
| Cache efficiency | Good (contiguous) | Poor (scattered in memory) |
In summary, use arrays for fast random access and fixed-size collections; use linked lists when frequent insertions/deletions are expected and the size changes often.
总之，需要快速随机访问和固定大小的集合时使用数组；当需要频繁插入/删除且大小经常变化时使用链表。
9. Types of Linked Lists | 链表的类型
While the standard singly linked list is the main focus, the Edexcel specification also references other types. You should be able to describe them briefly.
虽然标准单向链表是主要焦点，但 Edexcel 规范也涉及其他类型，你应该能简要描述它们。
Singly linked list: each node has one pointer to the next node; traversal in one direction only.
单向链表：每个节点有一个指向下一个节点的指针；只能单向遍历。
Doubly linked list: each node has two pointers – one to the next and one to the previous node. This allows traversal in both directions, at the cost of more memory.
双向链表：每个节点有两个指针——一个指向下一个节点，一个指向前一个节点。这允许双向遍历，但需要更多内存。
Circular linked list: the last node points back to the first node instead of null. Used in applications like round-robin scheduling.
循环链表：最后一个节点指回第一个节点，而不是 null。用于循环调度等应用。
10. Exam-Style Tracing and Pseudocode | 考试风格追踪与伪代码
Edexcel questions often give you a linked list represented in a table of memory addresses or pseudocode. You may be asked to show the changes after adding or removing nodes, or to complete a trace table. Practice updating pointers step by step.
Edexcel 的题目通常以内存地址表或伪代码的形式给出一个链表。你可能需要展示添加或删除节点后的变化，或者完成追踪表。要练习逐步更新指针。
Example: Given head = 50, and nodes:
示例：给定 head = 50，节点如下：
| Address | Data | Next |
| 50 | 'apple' | 80 |
| 80 | 'banana' | 120 |
| 120 | 'cherry' | null |
If we delete the second node (data 'banana'), we set the Next of node 50 to 120. The list becomes: 50 -> 120 -> null. The node at 80 is logically removed.
如果删除第二个节点（数据为 'banana'），我们将节点 50 的 Next 设置为 120。链表变为：50 -> 120 -> null。地址 80 的节点在逻辑上被移除。
11. Advantages and Disadvantages in Real-World Contexts | 实际应用中的优缺点
Linked lists are ideal for implementing stacks, queues, and for applications where the number of items is unpredictable, such as playlists or dynamic memory allocation. However, the overhead of storing pointers and lack of direct access make them less suitable for lookup-intensive tasks.
链表非常适合实现栈、队列以及元素数量不可预测的应用，如播放列表或动态内存分配。但是，存储指针的开销和无法直接访问使得它们不太适合查找密集的任务。
An array might be better for storing a known list of student marks, where random access by index is needed. A linked list is better for a music player where songs are frequently added or removed from the current queue.
数组可能更适合存储已知的学生成绩列表，因为需要通过索引进行随机访问。链表更适合于音乐播放器，其中当前队列中的歌曲会频繁添加或移除。
12. Common Mistakes and Tips for the Exam | 常见错误与考试贴士
One common mistake is forgetting to update the head pointer when deleting the first node. Another is losing the reference to the rest of the list when inserting. Always assign the new node's next before updating the previous node's next. Use trace tables to verify your logic.
一个常见错误是删除第一个节点时忘记更新头指针。另一个错误是在插入时丢失对链表其余部分的引用。务必先分配新节点的 next，再更新前一个节点的 next。使用追踪表验证你的逻辑。
Practice writing pseudocode for finding the item before the target in a singly linked list, because deletion requires that previous node. Remember that deleting the last node requires special handling to update the second-last node's next to null.
练习编写在单向链表中查找目标项之前节点的伪代码，因为删除操作需要那个前一个节点。记住删除最后一个节点需要特殊处理，将倒数第二个节点的 next 更新为 null。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图