📚 GCSE WJEC Computer Science: Linked Lists Revision Guide | GCSE WJEC 计算机：链表 考点精讲
Welcome to your focused revision guide on linked lists for the WJEC GCSE Computer Science specification. This article breaks down the core concepts, common algorithms, and typical exam questions you will encounter. Whether you are learning about nodes, pointers, or comparing linked lists with arrays, this guide provides clear explanations, practical pseudocode, and essential tips to help you succeed.
欢迎阅读这份针对 WJEC GCSE 计算机科学的链表考点精讲。本文拆解了核心概念、常见算法以及你将遇到的典型考题。无论你正在学习节点、指针还是链表与数组的对比，这份指南都会提供清晰的解释、实用的伪代码以及帮助你考试成功的关键技巧。
1. What is a Linked List? | 什么是链表？
A linked list is a dynamic data structure used to store a collection of items. Unlike arrays, the elements in a linked list 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. This chain of nodes forms the list. The first node is known as the head, and the last node points to a null value, indicating the end of the list.
链表是一种用于存储数据集合的动态数据结构。与数组不同，链表中的元素并不存储在连续的内存位置中。每个元素称为一个节点，包含数据和指向序列中下一个节点的引用（或指针）。这种节点链条构成了链表。第一个节点称为头节点，最后一个节点指向一个空值，表示链表的结束。
- Head (头节点) – the starting point of the list （链表的起始点）
- Null (空值) – indicates the end of the chain （表示链的结尾）
2. Anatomy of a Node | 节点的结构
Each node in a linked list typically consists of two fields: a data field to hold the value and a pointer field (often called ‘next’) to store the memory address of the subsequent node. In a singly linked list, the pointer only goes one way. The last node’s pointer is set to null. Understanding this structure is fundamental to tracing and writing linked-list algorithms.
链表中的每个节点通常包含两个字段：一个数据字段用于存储值，一个指针字段（通常称为 ‘next’）用于存储下一个节点的内存地址。在单链表中，指针只有一个方向。最后一个节点的指针设为空。理解这个结构是追踪和编写链表算法的基础。
Node: [ Data | Next ]
节点: [ 数据 | Next ]
3. Traversing a Singly Linked List | 遍历单链表
Traversal means visiting each node in the list, usually to search for an item or to process all data. You start at the head and follow the next pointers until you reach null. A typical traversal loop uses a temporary pointer variable that moves along the chain. You must handle an empty list (head is null) as a special case.
遍历意味着访问列表中的每个节点，通常是为了搜索某个项或处理所有数据。你从头节点开始，沿着 next 指针移动，直到遇到空。一个典型的遍历循环使用一个临时指针变量沿着链条移动。你必须处理空列表（头节点为空）这种特殊情况。
Pseudocode for traversal:
遍历的伪代码：
current = head
WHILE current != null
OUTPUT current.data
current = current.next
ENDWHILE
This will print every element in order. If the list is empty, the loop body is never executed.
这将按顺序打印每个元素。如果列表为空，循环体将不会执行。
4. Inserting a Node | 插入节点
Insertion is one of the main operations on a linked list. The position of insertion determines the algorithm: at the beginning, at the end, or at a specific index. Unlike arrays, you do not need to shift elements; you only modify the pointers. This makes insertion efficient when you have a reference to the node just before the insertion point.
插入是链表上的主要操作之一。插入的位置决定了算法：在开头插入、在末尾插入，或在特定索引处插入。与数组不同，你不需要移动元素；只需要修改指针。这使得当你拥有指向插入点之前节点的引用时，插入操作变得高效。
Insert at start (在开头插入):
newNode.next = head
head = newNode
The new node points to the old head, then we update head to the new node. This is an O(1) operation.
新节点指向旧的头节点，然后我们将头节点更新为新节点。这是一个 O(1) 操作。
Insert at end (在末尾插入):
IF head == null
head = newNode
ELSE
current = head
WHILE current.next != null
current = current.next
ENDWHILE
current.next = newNode
ENDIF
We traverse to the last node and update its next pointer to the new node. This is O(n) for a singly linked list.
我们遍历到最后一个节点，并将其 next 指针更新为新节点。对于单链表，这是一个 O(n) 操作。
5. Deleting a Node | 删除节点
Deletion involves removing a node and relinking the previous node’s next pointer to skip the deleted node. If the node to delete is the head, you simply update the head. For any other node, you need a reference to the node before the one you wish to remove. The deleted node becomes inaccessible and its memory can be freed.
删除操作涉及移除一个节点，并重新链接前一个节点的 next 指针以跳过被删除的节点。如果待删除节点是头节点，你只需要更新头节点。对于任何其他节点，你需要一个指向待删除节点前一个节点的引用。被删除的节点变得不可访问，其内存可以被释放。
Pseudocode to delete a node with a given value:
删除具有给定值的节点的伪代码：
IF head == null THEN RETURN
IF head.data == target THEN
head = head.next
RETURN
ENDIF
current = head
WHILE current.next != null
IF current.next.data == target THEN
current.next = current.next.next
RETURN
ENDIF
current = current.next
ENDWHILE
This algorithm handles the head deletion separately and then scans the rest of the list. Note that it stops after deleting the first occurrence.
该算法单独处理头节点的删除，然后扫描列表的其余部分。注意，它在删除第一次出现的节点后就会停止。
6. Linked Lists vs. Arrays | 链表与数组的比较
For WJEC GCSE, you must be able to compare linked lists and arrays in terms of memory usage, access speed, and flexibility. The table below summarises the key differences.
对于 WJEC GCSE，你必须能够从内存使用、访问速度和灵活性等方面比较链表和数组。下表总结了关键差异。
| Feature （特性） | Array （数组） | Linked List （链表） |
|---|---|---|
| Memory allocation （内存分配） | Static (fixed size) or dynamic contiguous block （静态固定大小或动态连续块） | Dynamic, non-contiguous nodes （动态、非连续节点） |
| Access time （访问时间） | O(1) random access （O(1) 随机访问） | O(n) sequential access （O(n) 顺序访问） |
| Insertion/deletion （插入/删除） | O(n) due to shifting elements （因移动元素导致 O(n)） | O(1) if node reference known, else O(n) for searching （若已知节点引用为 O(1)，搜索时 O(n)） |
| Memory overhead （内存开销） | No extra pointers （没有额外指针） | Extra storage for pointers in each node （每个节点需要额外存储指针） |
| Size flexibility （大小灵活性） | Fixed unless dynamic array resized (costly) （固定，除非动态数组调整大小，成本高昂） | Grows or shrinks easily at runtime （运行时轻松增长或缩小） |
Exam questions often ask you to justify the choice of data structure for a given scenario. Using a linked list is ideal when the number of elements is unknown and frequent insertions/deletions occur. Arrays are better when fast random access is required.
考题经常要求你为给定场景选择数据结构并说明理由。当元素数量未知且频繁发生插入/删除操作时，链表是理想选择。当需要快速随机访问时，数组更合适。
7. Memory and Dynamic Data Structures | 内存与动态数据结构
Linked lists are a prime example of a dynamic data structure. They use memory from the heap, and nodes can be allocated and deallocated as needed. This contrasts with static structures where memory size is fixed at compile time. Understanding the stack and heap distinction is not required in depth, but you should know that linked lists can grow without reallocation of the whole structure.
链表是动态数据结构的一个典型例子。它们使用堆内存，节点可以根据需要被分配和释放。这与静态结构形成对比，静态结构的内存大小在编译时就被固定。你不必深入理解栈和堆的区别，但应当知道链表可以在不需要重新分配整个结构的情况下增长。
Because each node stores an explicit pointer to the next, memory overhead is higher than arrays. However, this is the trade-off for flexibility.
由于每个节点都显式存储指向下一个的指针，内存开销比数组更大。然而，这是为了灵活性而做出的权衡。
8. Common Applications of Linked Lists | 链表的常见应用
Linked lists are used in many real-world computing contexts. For GCSE, you might see them in implementations of stacks and queues, undo functions in software (each action is a node), music playlist management, or as building blocks for more complex structures like hash tables (chaining).
链表在许多现实世界的计算环境中都有应用。对 GCSE 而言，你可能会在以下情形中见到它们：栈和队列的实现、软件中的撤销功能（每个操作是一个节点）、音乐播放列表管理，或者作为更复杂结构（如哈希表的链地址法）的构建块。
- Implementing a dynamic queue where dequeuing simply moves the front pointer （实现动态队列，出队只需移动前指针）
- Image viewer: browsing pictures forward and backward (doubly linked) （图片查看器：前后浏览图片，使用双向链表）
- Operating systems: managing processes in a ready queue （操作系统：管理就绪队列中的进程）
9. WJEC-Style Pseudocode and Algorithm Questions | WJEC 风格的伪代码与算法题
In the exam, you may be asked to read, complete, or write pseudocode for linked-list operations. WJEC uses a specific pseudocode style: loops with WHILE … ENDWHILE, conditions with IF … ENDIF, and outputs with OUTPUT. You should be comfortable tracing through code that manipulates nodes using the next pointer.
在考试中，你可能会被要求阅读、完成或编写链表操作的伪代码。WJEC 使用特定的伪代码风格：循环用 WHILE … ENDWHILE，条件用 IF … ENDIF，输出用 OUTPUT。你应该能够熟练追踪通过 next 指针操作节点的代码。
Example: Trace the following pseudocode for a linked list containing 3 → 5 → 7 → 9.
示例：对于包含 3 → 5 → 7 → 9 的链表，追踪以下伪代码。
current = head
total = 0
WHILE current != null
total = total + current.data
current = current.next
ENDWHILE
OUTPUT total
This sums the values, outputting 24. Similar questions may require you to identify the purpose of an algorithm or spot an error, such as an infinite loop if you forget to advance current.
这段代码计算值的和，将输出 24。类似的问题可能要求你识别算法的目的，或找出错误，例如如果忘记移动 current 指针会导致无限循环。
10. Key Exam Tips for WJEC GCSE | WJEC GCSE 考试要点
When answering linked-list questions, keep these tips in mind to avoid common pitfalls:
在回答链表问题时，请牢记以下提示以避免常见错误：
- Always initialise and update the head pointer correctly when the list becomes empty or the first node changes. （当链表变为空或第一个节点发生变化时，始终正确初始化和更新头指针。）
- Check for null pointers to prevent runtime errors – always handle the empty list case. （检查空指针以防止运行时错误——务必处理空列表的情况。）
- When drawing diagrams, label the next pointers clearly and use arrows to show the correct linking. （在画图时，清晰地标注 next 指针，并使用箭头显示正确的链接。）
- For insertion/deletion, draw a ‘before’ and ‘after’ sketch to confirm that the pointers are reassigned in the correct order. （在插入/删除时，画出操作前和操作后的草图，以确认指针按正确顺序重新赋值。）
- Memorise the typical pseudocode patterns for traversal, insert at start, and delete from start, as they appear frequently. （记住遍历、在开头插入和从开头删除的典型伪代码模式，因为它们经常出现。）
- In comparison questions, use the table format to organise your answer and always include a balanced conclusion linking to the scenario. （在比较题中，使用表格来组织你的答案，并始终包含一个与场景相关的平衡结论。）
Practice writing pseudocode without syntax highlighting or autocomplete, just as you will in the exam. Simulate the process on paper with a small dataset to build confidence.
练习在没有语法高亮和自动补全的情况下编写伪代码，就像在考试中那样。用一个小型数据集在纸上模拟过程，以建立信心。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply