Linked Lists in IGCSE OCR Computer Science | IGCSE OCR 计算机：链表考点精讲

📚 Linked Lists in IGCSE OCR Computer Science | IGCSE OCR 计算机：链表考点精讲

A linked list is a dynamic data structure used to store an ordered collection of elements. Unlike arrays, the elements are not stored in contiguous memory locations; each node points to the next one, allowing efficient insertion and deletion. In IGCSE OCR Computer Science, you need to understand how linked lists work, be able to trace their operations, and compare them with other structures such as arrays.

链表是一种动态数据结构，用于存储有序的元素集合。与数组不同，这些元素并不是存储在连续的内存空间中；每一个节点都指向下一个节点，从而能够高效地进行插入和删除操作。在IGCSE OCR计算机科学课程中，你需要理解链表的工作原理，能够追踪其操作过程，并将其与数组等其他结构进行比较。

1. What Is a Linked List? | 什么是链表？

A linked list consists of a sequence of nodes. Each node contains a data field (the actual value being stored) and a pointer (or link) that stores the address of the next node in the sequence. The very first node is called the head, and the last node’s pointer points to null (or a terminator such as /0) to indicate the end of the list.

链表由一系列节点（node）组成。每个节点包含一个数据域（存储实际的值）和一个指针（或称链接），该指针存储序列中下一个节点的地址。第一个节点称为头节点（head），最后一个节点的指针指向空（或某个结束符如/0），表示列表的结尾。

2. Nodes and Pointers | 节点与指针

A node is a record-like structure, typically represented in pseudocode with at least two fields: data and next. The data field can be of any type (integer, string, etc.). The next field is a pointer that holds the address of the following node. In diagrams, we often draw nodes as boxes split into two parts: one labelled ‘Data’ and the other ‘Pointer’.

节点是一种类似记录的结构，在伪代码中通常至少包含两个字段：data 和 next。data 字段可以是任何类型（整数、字符串等）。next 字段是一个指针，保存下一个节点的地址。在示意图中，我们通常将节点画成分成两部分的方框：一部分标为“数据”（Data），另一部分标为“指针”（Pointer）。

3. Singly Linked List (Linear List) | 单向链表（线性表）

The simplest form is the singly linked list, where each node has only one pointer to the next node. Traversal is possible only in one forward direction. The head pointer stores the start of the list. If the list is empty, the head pointer holds null.

最简单的形式是单向链表，每个节点只有一个指向下一个节点的指针。只能沿正向遍历。头指针存储列表的起始位置。如果链表为空，头指针的值为空（null）。

Example of a singly linked list storing three numbers: 5, 12, 9. The head points to the node containing 5; that node’s next pointer points to the node containing 12, whose next pointer points to the node containing 9, whose next pointer points to null.

示例：一个存储三个数字 5、12、9 的单向链表。头指针指向包含 5 的节点；该节点的 next 指针指向包含 12 的节点，其 next 指针指向包含 9 的节点，而 9 的 next 指针指向 null。

4. Traversing a Linked List | 遍历链表

To traverse a linked list, you start at the head and follow the next pointers until you encounter null. Pseudocode typically uses a variable current (or ptr) that begins at head and moves to current.next in a loop while current != null.

要遍历链表，从 head 开始，沿着 next 指针前进，直到遇到 null。伪代码通常使用一个变量 current（或 ptr），让它从 head 开始，并在循环中移动到 current.next，循环条件是 current != null。

current ← head
while current ≠ null
    OUTPUT current.data
    current ← current.next
endwhile

This traversal is very common in exam trace-table questions, where you must show how the output is produced step by step.

这种遍历在考试中常见的追踪表问题中经常出现，你需要逐步展示输出的生成过程。

5. Inserting a Node into a Linked List | 在链表中插入节点

Insertion does not require shifting elements as in an array; only pointer changes are needed. Common insertion positions are at the beginning, in the middle, or at the end. For inserting at the front, the new node’s next pointer is set to the current head, and then head is updated to point to the new node.

插入不需要像数组那样移动元素，只需要改变指针即可。常见的插入位置有开头、中间或末尾。在开头插入时，将新节点的 next 指针设置为当前 head，然后将 head 更新为指向新节点。

For inserting in the middle, you must first find the node after which the new node is to be inserted (let’s call it prev). The new node’s next pointer is assigned prev.next, and then prev.next is set to point to the new node. The order of these two steps is crucial to avoid breaking the chain.

在中间插入时，必须先找到要在其后插入的节点（记为 prev）。新节点的 next 指针被赋予 prev.next，然后将 prev.next 指向新节点。这两个步骤的顺序至关重要，避免断开链。

6. Deleting a Node from a Linked List | 从链表中删除节点

Deletion also only requires pointer manipulation. To delete the first node, simply move the head pointer to the second node (if it exists). To delete a middle node, you need a reference to the node before the one to be deleted (prev). Then set prev.next to the node after the deleted node; the deleted node becomes unreachable and will be garbage-collected or freed.

删除也只需要操作指针。要删除第一个节点，只需将 head 指针移到第二个节点（如果存在）。要删除中间节点，需要一个指向待删除节点前一个节点的引用（prev）。然后将 prev.next 设置为待删除节点之后的节点；被删除的节点变得不可达，将被垃圾回收或释放。

In exams, you must be careful to show that the node’s memory is logically removed by losing the pointer reference to it. No data shifting is required, which highlights the advantage of linked lists for frequent insertion/deletion operations.

在考试中，你必须小心展示通过丢失指向该节点的指针引用，从而在逻辑上删除了节点。不需要移动数据，这突显了链表在频繁插入/删除操作时的优势。

7. Linked Lists vs. Arrays – Key Comparisons | 链表与数组对比 – 关键比较

Feature / 特性	Linked List / 链表	Array / 数组
Memory storage / 存储方式	Non-contiguous (nodes anywhere) / 非连续（节点可分散）	Contiguous block / 连续块
Size flexibility / 大小灵活性	Dynamic – grows and shrinks easily / 动态——易于扩展和收缩	Static (or dynamic with overhead) / 静态（或动态但有额外开销）
Access time / 访问时间	Sequential (O(n)) – must traverse / 顺序访问（O(n)），必须遍历	Random access (O(1)) via index / 通过索引随机访问（O(1)）
Insertion/deletion / 插入/删除	Efficient (O(1)) if position known; just change pointers / 若已知位置则高效（O(1)）；仅改变指针	Inefficient – shifting required (O(n)) / 低效——需要移动元素（O(n)）
Extra memory / 额外内存	Overhead of pointers / 指针的开销	No overhead (just data) / 无额外开销（仅数据）

This table is extremely useful for exam questions that ask you to justify the choice of data structure. OCR examiners expect you to explain the trade-offs clearly.

这张表对考试中要求你论证数据结构选择的题目非常有用。OCR考官期望你能清晰地解释这些权衡。

8. Dynamic Memory Allocation and the Heap | 动态内存分配与堆

Linked list nodes are usually created at runtime using dynamic memory allocation. In high-level languages, this corresponds to `new` or `malloc`. The memory is taken from the heap, not the stack. This means the list can grow as long as there is free memory, without a predetermined size limit.

链表的节点通常是在运行时通过动态内存分配创建的。在高级语言中，这对应于 `new` 或 `malloc`。内存来自堆而非栈。这意味着只要还有空闲内存，链表就可以增长，没有预设的大小限制。

In IGCSE pseudocode, you won’t be required to write memory allocation commands, but you need to know that nodes are created dynamically and that they stay in memory until the pointer to them is removed.

在IGCSE伪代码中，不会要求你写出内存分配命令，但你需要知道节点是动态创建的，并且它们会一直留在内存中，直到指向它们的指针被移除。

9. Implementing Linked List Operations in Pseudocode | 用伪代码实现链表操作

OCR pseudocode uses a particular style. For example, a node might be defined as a record:

OCR伪代码采用特定风格。例如，一个节点可定义为记录：

TYPE Node
    DECLARE data : INTEGER
    DECLARE next : INTEGER  // stores index or pointer
ENDTYPE

Traversal, insertion, and deletion algorithms are expected to be written using simple variables. You must know how to handle boundary cases such as an empty list or deleting the only node.

遍历、插入和删除算法要求能用简单的变量写出。你必须知道如何处理边界情况，比如空链表或删除唯一节点。

Example of inserting at the start:

在开头插入的示例：

PROCEDURE InsertAtStart(value)
    CREATE newNode
    newNode.data ← value
    newNode.next ← head
    head ← newNode
ENDPROCEDURE

Deleting the first node:

删除第一个节点：

IF head = null THEN
    OUTPUT "List empty"
ELSE
    head ← head.next
ENDIF

10. Common Exam Pitfalls and How to Avoid Them | 常见考试陷阱及如何避免

Many students lose marks by confusing the order of pointer updates during insertion, leading to a broken link. Always ensure the new node first points to the rest of the list, and then the previous node is linked to the new node.

许多学生因为在插入时混淆了指针更新顺序而失分，导致链接断开。务必确保新节点先指向链表剩余部分，然后将前一个节点链接到新节点。

Another common mistake is forgetting to handle the empty-list case. In deletion and insertion, always check whether the head pointer is null before operating. Furthermore, when traversing, failing to move the current pointer within the loop will cause an infinite loop.

另一个常见错误是忘记处理空链表的情况。在删除和插入操作中，务必在操作前检查头指针是否为 null。此外，遍历时若不在循环内移动当前指针，将导致无限循环。

In trace-table questions, students sometimes miss that they must update a pointer to null at the end of a list after a deletion. Practice drawing diagrams to visualise pointer changes before writing pseudocode.

在追踪表问题中，学生有时会忽略在删除操作后需要将链表末尾的指针更新为 null。建议在编写伪代码前练习绘制示意图，以可视化指针的变化。

11. Advantages and Disadvantages – Exam-Style Evaluation | 优点与缺点 – 考试风格评估

Linked lists shine when frequent insertions and deletions are required and random access is not needed. They make efficient use of memory because they can grow and shrink on demand, avoiding the waste of pre-allocated array space. However, the extra memory for storing pointers and the overhead of traversal for accessing elements are significant drawbacks. The lack of cache locality (because nodes are scattered in memory) can also degrade performance in real-world systems, though this is beyond IGCSE scope.

当需要频繁插入和删除且不需要随机访问时，链表表现出色。它们能高效利用内存，因为可以按需增长和收缩，避免预先分配的数组空间浪费。然而，存储指针需要额外内存，且访问元素时必须遍历，这些是明显的缺点。由于节点分布在内存各处，缺乏缓存局部性在实际系统中也可能降低性能，不过这已超出IGCSE范围。

For static collections where the size is known and random access is essential, arrays are a better choice. Always refer to the context of the problem in your answer; examiners look for justified decisions.

对于大小已知且随机访问至关重要的静态集合，数组是更好的选择。在作答时务必结合问题背景；考官期望看到有理有据的决策。

12. Practice Question Walkthrough | 练习题详解

A typical IGCSE question: “A singly linked list contains the values 10, 20, 30. Its head pointer points to the node with 10. Show the state of the list after running pseudocode to delete the second node.” You would be expected to show the updated pointers: head still points to 10, the next of the first node now points to 30, and the node containing 20 is not referenced.

一道典型的IGCSE题目：“一个单向链表包含数值 10、20、30。其头指针指向含有 10 的节点。展示运行伪代码删除第二个节点后链表的状态。”你应展示更新后的指针：head 仍指向 10，第一个节点的 next 现在指向 30，而含有 20 的节点不再被引用。

Another question might ask you to compare linked lists and arrays for a given scenario, such as storing a playlist where songs are added and removed frequently. In this case, a linked list is appropriate because inserts/deletes are fast and the playlist is likely traversed sequentially. Use the table from Section 7 to structure your answer.

另一问题可能要求你针对给定场景比较链表和数组，比如存储一个频繁添加和删除歌曲的播放列表。这时链表是合适的，因为插入/删除快速且播放列表通常是顺序遍历的。利用第7节的表格组织你的答案。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Linked Lists in IGCSE OCR Computer Science | IGCSE OCR 计算机：链表 考点精讲