📚 Linked Lists for GCSE OCR Computer Science | GCSE OCR 计算机：链表考点精讲
In GCSE OCR Computer Science, data structures are fundamental to understanding how programs store and organise data. Among these, linked lists provide a dynamic alternative to arrays, allowing memory to be used more flexibly. This revision guide breaks down everything you need to know about linked lists, from node anatomy to traversal algorithms, tailored exactly to the OCR specification.
在 GCSE OCR 计算机科学中，数据结构是理解程序如何存储和组织数据的基础。其中，链表为数组提供了一种动态的替代方案，能够更灵活地使用内存。这份复习指南将为你拆解关于链表你需要掌握的全部知识点，从节点的结构到遍历算法，严格按照 OCR 考纲要求编写。
1. What is a Linked List? | 什么是链表？
A linked list is a linear data structure in which elements, called nodes, are connected using pointers. Unlike an array, the elements of a linked list are not stored in contiguous memory locations; instead, each node contains a reference to the next node in the sequence. This structure allows efficient insertion and deletion of elements without the need to shift data, which is a major advantage in many scenarios.
链表是一种线性数据结构，其中被称为节点的元素通过指针连接。与数组不同，链表的元素并非存储在连续的内存位置中；相反，每个节点都包含一个指向序列中下一个节点的引用。这种结构允许在不需移动数据的情况下高效地插入和删除元素，这在许多场景下是一个重要优势。
2. Nodes and Pointers | 节点与指针
The building block of every linked list is the node. A node typically consists of two parts: the data field, which holds the actual value (e.g., an integer, string, or even another object), and the pointer field, which stores the memory address of the next node. In a singly linked list, there is exactly one pointer; in a doubly linked list, there are two. A visual representation of a node is often shown as [ data | next ].
每个链表的构建模块是节点。一个节点通常由两部分组成：数据域，保存实际的值（例如整数、字符串甚至其他对象）；以及指针域，存储下一个节点的内存地址。在单向链表中，只有一个指针；在双向链表中有两个。节点的视觉表示常被描绘为[ 数据 | 下一个 ]。
The first node in a linked list is called the head. If the list is empty, the head pointer is set to null. The last node’s pointer points to null, indicating the end of the list. In languages like Python or Java, these pointers are implemented as references to objects rather than raw memory addresses, but the concept remains identical.
链表中的第一个节点称为头节点。如果链表为空，头指针被设置为空。最后一个节点的指针指向空，表示链表的结束。在 Python 或 Java 等语言中，这些指针被实现为对象的引用，而非原始的内存地址，但概念完全相同。
3. Singly Linked Lists | 单向链表
A singly linked list is the simplest form of a linked list. Each node stores its own data and a single pointer to the next node. Traversal can only be performed in one direction – from the head to the tail. To access a specific element, you must start at the head and follow the next pointers sequentially. This gives singly linked lists a time complexity of O(n) for search and random access.
单向链表是最简单的链表形式。每个节点存储自身数据以及一个指向下一个节点的指针。遍历只能沿一个方向进行——从头到尾。要访问特定元素，必须从头开始依次跟随 ‘下一个’ 指针。这使得单向链表在搜索和随机访问上的时间复杂度为 O(n)。
Consider a singly linked list containing the prime numbers 2, 3, 5. Its structure would be: Head → [2|•] → [3|•] → [5|null]. The arrow represents the next pointer. Operations like adding a node at the front are extremely fast (O(1)), because they only require changing the head pointer.
考虑一个包含质数 2、3、5 的单向链表。其结构为：头 → [2|•] → [3|•] → [5|null]。箭头代表 ‘下一个’ 指针。像在头部添加节点这样的操作非常快（O(1)），因为它们只需要改变头指针。
4. Doubly Linked Lists | 双向链表
A doubly linked list extends the node structure by including an extra pointer that references the previous node. A typical doubly linked node is represented as [ prev | data | next ]. This dual-linkage allows traversal in both forward and backward directions, which makes operations like deleting a node when given a reference to that node much simpler – there is no need to traverse from the head to find the predecessor.
双向链表通过增加一个指向前一个节点的额外指针来扩展节点结构。一个典型的双向链表节点表示为[ 前驱 | 数据 | 后继 ]。这种双链接允许向前和向后两个方向遍历，这使得当获得某个节点的引用后，删除该节点等操作变得简单得多——无需从头遍历来寻找前驱节点。
The trade-off is that each node requires more memory to store the additional pointer. Also, insertion and deletion must update two pointers in the node itself and one pointer in each of the neighbouring nodes, which adds a small constant overhead. In GCSE exams, you may be asked to draw a doubly linked list after a series of operations, so spend time visualising the pointer manipulations.
其代价是每个节点需要更多内存来存储额外的指针。此外，插入和删除操作必须更新节点自身的两个指针以及相邻节点中各一个指针，这增加了一些小的常数级开销。在 GCSE 考试中，你可能会被要求画出一系列操作后的双向链表，因此请花时间想象指针的操作过程。
5. Circular Linked Lists | 循环链表
In a circular linked list, the last node does not point to null; instead, its next pointer references the head of the list, forming a circular chain. A circular singly linked list can be traversed endlessly in one direction, while a circular doubly linked list can be traversed in both directions. Circular linked lists are particularly useful in applications where the data needs to be cycled continuously, such as in a round-robin scheduler in an operating system or in multiplayer game turn management.
在循环链表中，最后一个节点不指向空；相反，它的 ‘下一个’ 指针引用链表的头节点，形成一个环形链。单向循环链表可无限地在一个方向上遍历，而双向循环链表可以在两个方向上遍历。循环链表在需要连续循环数据的应用中尤其有用，例如操作系统中的轮转调度器或多人游戏中的回合管理。
When implementing a circular linked list, care must be taken to avoid infinite loops during traversal. A common technique is to store the starting node and stop when the next pointer equals the starting node again. Insertion into an empty circular list creates a node whose next pointer points to itself.
在实现循环链表时，必须注意避免遍历过程中出现无限循环。一种常用的技巧是存储起始节点，当 ‘下一个’ 指针再次等于起始节点时停止。向空循环链表中插入会创建一个节点，其 ‘下一个’ 指针指向自身。
6. Traversal of a Linked List | 链表的遍历
Traversal means visiting every node in the list, often to search for a particular piece of data or to perform an operation like printing all values. In a singly linked list, the standard algorithm uses a loop with a current pointer. Initially, current is set to head. While current is not null, process current.data and then update current = current.next. This step-by-step forward movement is fundamental and is frequently examined in pseudocode or programming questions.
遍历是指访问链表中的每个节点，通常是为了搜索特定数据或执行如打印所有值之类的操作。在单向链表中，标准算法使用一个带有当前指针的循环。初始时，当前指针设为头节点。只要当前指针不为空，就处理当前节点的数据，然后更新 current = current.next。这种逐步向前的移动是基础，经常在伪代码或编程题中被考查。
For a doubly linked list, traversal can go both ways. To traverse backwards, you would typically start from the tail (which could be maintained as a separate pointer) and follow prev pointers until you reach the head. The OCR specification expects you to be able to trace through such algorithms on paper.
对于双向链表，可以双向遍历。要向后遍历，通常从尾节点开始（可以维护一个单独的尾指针），并跟随 ‘前驱’ 指针直到到达头节点。OCR 考纲要求你能够在纸上追踪这类算法。
7. Insertion Operations | 插入操作
Insertion into a linked list can happen at various positions: at the beginning, at the end, or at a given index. Inserting at the head of a singly linked list involves creating a new node, setting its next pointer to the current head, and then updating the head to point to the new node. This is an O(1) operation.
链表可以在不同位置进行插入：头部、尾部或给定索引位置。在单向链表头部插入需要创建一个新节点，将其 ‘下一个’ 指针设为当前头节点，然后更新头指针指向新节点。这是一个 O(1) 操作。
To insert in the middle, you must traverse to the node immediately before the insertion point. Let that predecessor be P. The new node’s next pointer is set to P.next, and then P.next is set to point to the new node. The order of these pointer updates is crucial; if you update P.next first, you lose the reference to the rest of the list. A table summarises the steps:
要在中间插入，必须遍历到插入点前一个节点。设该前驱节点为 P。新节点的 ‘下一个’ 指针设为 P.next，然后将 P.next 设为指向新节点。这些指针更新的顺序至关重要；如果先更新 P.next，你会丢失对链表其余部分的引用。下表总结了步骤：
| Step | Action |
| 1 | Create a new node with the desired data. |
| 2 | Set newNode.next = P.next |
| 3 | Set P.next = newNode |
In a doubly linked list, insertion additionally requires updating the prev pointer of the node that originally followed P, as well as the prev pointer of the new node. These extra steps maintain the two-way linkage.
在双向链表中，插入还需要更新原位于 P 之后的节点的 ‘前驱’ 指针，以及新节点的 ‘前驱’ 指针。这些额外步骤维护了双向连接。
8. Deletion Operations | 删除操作
Deleting a node from a linked list also involves careful pointer manipulation. If you want to delete the first node, simply set head = head.next, and in languages without automatic garbage collection, free the memory of the old head node. If you delete a middle node, you must identify its predecessor P and then set P.next = P.next.next, effectively bypassing the node to be deleted.
从链表中删除节点同样涉及细致的指针操作。如果要删除第一个节点，只需设置 head = head.next，在没有自动垃圾回收的语言中，还需释放旧头节点的内存。如果删除中间节点，必须找到其前驱节点 P，然后设置 P.next = P.next.next，从而绕过待删除的节点。
In a doubly linked list, deletion requires updating the next pointer of the previous node and the prev pointer of the next node. For example, to delete node X, you would execute: X.prev.next = X.next and, if X.next is not null, X.next.prev = X.prev. This restores the chain without X. Practising these steps on a whiteboard is excellent exam preparation.
在双向链表中，删除需要更新上一节点的 ‘下一个’ 指针和下一节点的 ‘前驱’ 指针。例如，要删除节点 X，需执行：X.prev.next = X.next，并且如果 X.next 不为空，则 X.next.prev = X.prev。这就在没有 X 的情况下恢复了链条。在白板上练习这些步骤是绝佳的备考方式。
One common pitfall is forgetting to handle the case when the node to be deleted is the head or the tail. In such boundary cases, you need to update the head or tail pointer accordingly. OCR exam questions often test these edge conditions.
一个常见的误区是忘记处理待删除节点是头节点或尾节点的情况。在这类边界情况中，你需要相应地更新头指针或尾指针。OCR 试题经常考查这些边缘条件。
9. Linked Lists vs Arrays | 链表与数组的比较
Arrays and linked lists are both used to store collections of elements, but they have fundamentally different memory layouts and performance characteristics. The table below highlights the key differences that are frequently examined:
数组和链表都用于存储元素的集合，但它们的内存布局和性能特征有着根本的不同。下表突出了常考的关键差异：
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Static, contiguous block | Dynamic, non-contiguous |
| Access time | O(1) random access via index | O(n) sequential access |
| Insertion/Deletion | O(n) due to shifting | O(1) if position known, otherwise O(n) |
| Memory overhead | Minimal, just data | Extra storage for pointers |
| Cache performance | Better, spatial locality | Poor, scattered memory |
Choosing between them depends on the application. If frequent random access and memory efficiency are required, an array is often better. If insertions and deletions are frequent and memory is fragmented, a linked list may be the preferred choice.
选择哪一种取决于具体应用。如果需要频繁的随机访问和内存效率，数组通常更好。如果插入和删除操作频繁且内存碎片化，链表可能是更合适的选择。
10. Advantages and Disadvantages | 优缺点分析
Linked lists offer several distinct advantages. They can grow or shrink dynamically at runtime, no waste of memory due to overallocation, and insertion/deletion of nodes can be very fast once the position is located. They also serve as the foundation for more complex data structures such as stacks, queues, and graphs.
链表具有若干显著优势。它们可以在运行时动态地增长或收缩，不会因过度分配而浪费内存，并且在定位到位置后，节点的插入和删除可以非常快。它们还是栈、队列和图等更复杂数据结构的基础。
However, disadvantages include the lack of direct element access; the need for extra memory for pointers; and the potential for fragmented memory, which can lead to poor cache performance. Additionally, traversing a linked list to find an element is slower than array indexing. In the context of GCSE, you should be able to discuss these trade-offs with clear, technical arguments.
然而，其缺点包括缺乏直接的元素访问；需要为指针额外分配内存；以及潜在的内存碎片化，这可能导致缓存性能不佳。此外，遍历链表来寻找元素比数组索引更慢。在 GCSE 背景下，你应该能够用清晰、技术性的论据来讨论这些权衡。
11. Common Exam Misconceptions | 常见考试误区
Many students confuse a linked list node’s pointer with an array index. A pointer is not a position number; it is a reference to a memory location. Another frequent mistake is assuming that deleting a node from a linked list automatically removes the data from memory – in reality, the node might still exist until garbage collected or explicitly freed, but it is no longer reachable from the list.
许多学生将链表节点的指针与数组下标混淆。指针不是位置编号；它是对内存位置的引用。另一个常见错误是假设从链表中删除节点会自动从内存中移除数据——实际上，节点在被垃圾回收或显式释放之前可能依然存在，但已无法从链表访问到它。
In pseudocode questions, a typical error is forgetting to update both the next and previous pointers in a doubly linked list insertion or deletion. Always re-draw the list after each operation and check that every connection is correct. Also, be cautious about special cases: inserting into an empty list, deleting the only node, and operations on the head or tail.
在伪代码题中，一个典型错误是在双向链表的插入或删除操作中忘记同时更新 ‘下一个’ 和 ‘前驱’ 指针。务必在每次操作后重新画出链表，并检查每个连接是否正确。此外，要小心特殊情况：向空链表中插入、删除唯一节点以及对头节点或尾节点的操作。
OCR mark schemes often reward precise terminology and methodical breakdown of steps. Revising these pointer handling details aloud or by writing them in a structured way can help secure full marks.
OCR 的评分标准通常奖励精确的术语和有条理的步骤分解。通过口头叙述或以结构化方式写下这些指针处理细节来进行复习，有助于获得满分。
12. Summary and Revision Tips | 总结与复习建议
Linked lists are a dynamic, pointer-based data structure that contrasts sharply with static arrays. Remember the anatomy of a node, the differences between singly, doubly, and circular variants, and the standard algorithms for traversal, insertion, and deletion. Being able to compare linked lists with arrays in terms of time complexity and memory usage is a crucial exam skill.
链表是一种动态的、基于指针的数据结构，与静态数组形成鲜明对比。记住节点的结构、单向、双向和循环变体之间的差异，以及遍历、插入和删除的标准算法。能够在时间复杂度和内存使用方面对链表与数组进行比较是一项关键的考试技能。
When revising, draw diagrams for each operation. Use a pencil and paper to trace through pseudocode. Practise rewriting the insertion steps without looking at notes, and explain the process in both English and Chinese to solidify your understanding. Aim to clearly articulate why O(1) and O(n) operations arise in each case.
复习时，请为每种操作绘制示意图。用铅笔和纸追踪伪代码。尝试在不看笔记的情况下重写插入步骤，并用中英双语解释这一过程以巩固理解。力求清晰地阐述每种情况下为何会出现 O(1) 和 O(n) 操作。
Finally, familiarise yourself with OCR past paper questions. They often present a partially drawn linked list and ask you to complete it after a sequence of operations, or to compare the suitability of an array and a linked list for a given scenario. With thorough understanding and practice, linked lists will become one of your strongest topics.
最后，请熟悉 OCR 历年真题。它们通常会给出部分绘制的链表，要求你在完成一系列操作后补全它，或比较数组与链表在给定场景下的适用性。通过深入理解和充足练习，链表将成为你最擅长的专题之一。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导