IGCSE CCEA Computer Science: Linked Lists – Key Exam Points | IGCSE CCEA 计算机：链表考点精讲

📚 IGCSE CCEA Computer Science: Linked Lists – Key Exam Points | IGCSE CCEA 计算机：链表考点精讲

A linked list is a dynamic data structure that stores a collection of nodes connected via pointers. In the IGCSE CCEA Computer Science specification, you are expected to understand how linked lists work, compare them with arrays, and trace operations such as insertion and deletion. This article provides a focused revision guide to help you master the key exam points.

链表是一种动态数据结构，通过指针连接一系列节点。在 IGCSE CCEA 计算机科学大纲中，你需要理解链表的工作原理、比较其与数组的异同、并跟踪插入和删除等操作。本文提供考点精讲，助你掌握核心应试要点。

1. Node Structure of a Linked List | 链表的节点结构

A linked list is made up of nodes. Each node contains at least two components: a data field that holds the actual value, and a pointer field (often called ‘next’) that stores the memory address of the following node. The last node’s pointer is set to null (or nil), indicating the end of the list. In CCEA exams, you may be asked to label a node diagram or identify these fields.

链表由节点组成。每个节点至少包含两个部分：存放实际值的数据域，以及存储下一个节点内存地址的指针域（通常称为 next）。最后一个节点的指针设为 null（或 nil），表示链表结束。在 CCEA 考试中，可能要求你标注节点图或识别这些域。

Data field: can be a number, character, string, or any data type.

数据域：可以是数字、字符、字符串或任何数据类型。
Next pointer: holds the address of the next node; if there is no next node, it contains null.

Next 指针：存放下一节点的地址；若无下一节点，则存放 null。

[ data | next ] → [ data | next ] → null

You must remember that the head pointer is a separate variable that points to the first node. If the list is empty, head is null.

必须记住头指针是一个单独的变量，指向第一个节点。若链表为空，头指针即为 null。

2. Types of Linked Lists | 链表的类型

Singly linked list: each node has a single pointer to the next node. Traversal is strictly forward. This is the most common type examined at IGCSE.

单向链表：每个节点只包含一个指向下一个节点的指针。遍历只能向前进行。这是 IGCSE 最常考查的类型。

Doubly linked list: each node has two pointers – one to the next node and one to the previous node. This allows traversal in both directions but uses more memory per node.

双向链表：每个节点有两个指针——一个指向下一个节点，一个指向前一个节点。可以双向遍历，但每个节点占用更多内存。

Circular linked list: the last node points back to the first node, forming a circle. It can be singly or doubly linked. Useful for applications that need to loop through data continuously.

循环链表：最后一个节点指向第一个节点，形成环形。可以是单向或双向。适用于需要循环访问数据的场景。

In CCEA questions, you may be shown a diagram and asked to identify the list type or state the advantages of one type over another.

在 CCEA 考题中，可能会给出图示，要求你识别链表类型或说明某种类型的优势。

3. Traversing a Linked List | 遍历链表

To visit every element, you start at the head and follow the next pointers until you encounter null. A temporary pointer (often called ‘current’) is used to move through the list without losing the head reference.

要访问每个元素，从头节点开始，沿 next 指针移动直到遇到 null。通常使用一个临时指针（常称为 current）来遍历链表，以免丢失头引用。

Pseudocode for traversal: current = head; while current != null: output current.data; current = current.next;

遍历伪代码：current = head; while current != null: output current.data; current = current.next;

The time complexity of traversal is O(n) because each node is visited once. If the list is empty, the loop body is not executed.

遍历的时间复杂度为 O(n)，因为每个节点访问一次。若链表为空，循环体不执行。

CCEA exam tasks often include filling in a trace table showing the values of current and data at each step.

CCEA 考试任务常包括填写追踪表，显示每一步 current 和 data 的值。

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

Insertion requires creating a new node and updating the relevant pointers. The correct order of pointer updates is vital to avoid losing parts of the list.

插入操作需创建新节点并更新相关指针。正确的指针更新顺序至关重要，以避免丢失链表的一部分。

Inserting at the head: set the new node’s next to the current head, then update head to point to the new node. This is an O(1) operation.

在头部插入：将新节点的 next 设为当前头节点，然后更新头指针指向新节点。此操作时间复杂度为 O(1)。

Inserting in the middle: suppose you want to insert after a node pointed to by ‘prev’. First set new node’s next to prev’s next, then change prev’s next to the new node. Reversing these steps would cause the rest of the list to be lost.

在中间插入：假设要插入到由 prev 指向的节点之后。先将新节点的 next 设为 prev 的 next，再将 prev 的 next 改为新节点。颠倒这两步会导致链表余下部分丢失。

Inserting at the end: traverse to the last node, then set its next to the new node and ensure the new node’s next is null.

在末尾插入：遍历到最后一个节点，将其 next 设为新节点，并确保新节点的 next 为 null。

You should practice drawing ‘before’ and ‘after’ diagrams for each scenario, as this is a common CCEA exam requirement.

应练习绘制每种情况的“之前”和“之后”图示，这是 CCEA 考试的常见要求。

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

Deletion bypasses a node so that it is no longer part of the list. The memory occupied by the deleted node may be freed, but at IGCSE level we focus on the pointer changes.

删除操作绕过某个节点，使其不再属于链表。被删节点占用的内存可能被释放，但在 IGCSE 阶段我们关注指针的变化。

Deleting the head node: simply set head = head.next. The original head becomes unreachable.

删除头节点：只需令 head = head.next。原来的头节点变得不可访问。

Deleting an interior node: identify the node immediately before the one to be deleted (call it ‘prev’). Set prev.next = prev.next.next (or target.next). This effectively links prev directly to the node after the target.

删除内部节点：找到要删除节点前一个节点（称为 prev）。令 prev.next = prev.next.next（或 target.next）。这样就使 prev 直接链接到目标节点之后的节点。

Deleting the last node: traverse to the second-last node and set its next to null.

删除最后一个节点：遍历到倒数第二个节点，将其 next 设为 null。

A typical CCEA question provides a linked list diagram and asks you to redraw it after deleting a specific value, showing all pointer updates.

典型的 CCEA 题目给出链表图，要求你重绘删除指定值后的链表，显示所有指针更新。

6. Searching in a Linked List | 在链表中搜索

Searching for a target value involves a linear traversal from the head, comparing each node’s data with the target. If found, the search can return the node’s position (or a Boolean true). If the end is reached without a match, the value is not in the list.

搜索目标值需要从头部开始线性遍历，比较每个节点的数据与目标。如果找到，搜索可以返回节点位置（或布尔值 true）。如果到达末尾仍未匹配，则列表中不存在该值。

Pseudocode: current = head; while current != null: if current.data == target then return true; current = current.next; return false;

伪代码：current = head; while current != null: if current.data == target then return true; current = current.next; return false;

The worst-case time complexity is O(n). You cannot perform a binary search on a standard linked list because there is no direct index access.

最坏时间复杂度为 O(n)。不能在标准链表上进行二分搜索，因为没有直接索引访问。

CCEA questions sometimes ask you to count the number of comparisons made during a search, so be prepared to trace through an algorithm step by step.

CCEA 题目有时要求计算搜索过程中比较的次数，因此需准备好逐步跟踪算法。

7. Arrays vs Linked Lists | 数组与链表的比较

Understanding when to use an array or a linked list is a key part of the IGCSE CCEA syllabus. The table below summarises the main differences.

理解何时使用数组或链表是 IGCSE CCEA 大纲的关键部分。下表总结了主要差异。

Feature	Array	Linked List
Memory arrangement	Contiguous (one block) – static or dynamic	Non-contiguous – nodes allocated anywhere
Access method	Random (direct) access using index – O(1)	Sequential access – must traverse – O(n)
Insertion / deletion	Shifting elements needed – O(n)	Pointer updates – O(1) if position known, but O(n) to find position
Memory overhead	No extra pointers – just the data	Each node stores one or two extra pointers
Size flexibility	Fixed size (static array) – can lead to waste or overflow	Dynamic – grows and shrinks as needed, no overflow if memory available
Cache performance	Better spatial locality	Poorer locality – nodes may be scattered

In exam scenarios, you need to justify your choice. For example, if the application involves many insertions and deletions, a linked list is often preferred. If frequent direct access by index is required, an array is better.

在考试场景中，你需要证明你的选择。例如，如果应用包含大量插入和删除操作，链表通常更合适；如果需要频繁通过索引直接访问，则数组更佳。

8. Dynamic vs Static Data Structures | 动态与静态数据结构

A linked list is a classic example of a dynamic data structure because its size can change at runtime. In contrast, a static array has a fixed size determined at compile time. CCEA expects you to distinguish between these two categories.

链表是动态数据结构的典型例子，因为其大小可以在运行时改变。相比之下，静态数组的大小在编译时确定，不可改变。CCEA 要求你区分这两类结构。

Dynamic structures allocate memory from the heap as needed, making efficient use of memory. However, they introduce extra complexity and pointer overhead.

动态结构根据需要从堆中分配内存，内存使用效率更高。但它们引入了额外的复杂性和指针开销。

When a question asks for an ‘advantage of a linked list over a static array’, you can mention: no need to predict the maximum size; no memory wastage from unused slots; easier insertion and deletion in the middle.

当题目要求列举“链表相对于静态数组的优势”时，你可以提到：无需预测最大大小；没有未使用槽位造成的内存浪费；在中间插入和删除更容易。

9. Pseudocode for Linked List Operations | 链表操作的伪代码

CCEA exam papers often include questions where you must write or interpret pseudocode. The syntax is informal but must be clear. Always use a temporary pointer when traversing, and make sure to handle the head pointer correctly.

CCEA 试卷常包含编写或解读伪代码的题目。语法不要求严格形式，但必须清晰。遍历时务必使用临时指针，并确保正确处理头指针。

Example – adding a node at the front:

示例 – 在表头添加节点：

PROCEDURE addFront(head, data) newNode = new Node() newNode.data = data newNode.next = head head = newNode RETURN head ENDPROCEDURE

Example – deleting a node with a specific value:

示例 – 删除具有特定值的节点：

PROCEDURE deleteNode(head, target) if head == null then return head if head.data == target then return head.next prev = head current = head.next while current != null: if current.data == target then prev.next = current.next return head prev = current current = current.next return head ENDPROCEDURE

Notice how boundary cases are handled: empty list and deleting the head are checked first.

注意边界情况的处理：先检查空链表和删除头节点。

10. Common Exam Mistakes and Tips | 常见考试错误与提示

Mistake 1: reversing the order of pointer assignments during insertion. Always set the new node’s next before overwriting the previous pointer. If you do it the other way, you lose the remaining nodes.

错误 1：在插入时颠倒指针赋值的顺序。务必先设置新节点的 next，再覆盖前一个指针。否则会丢失其余节点。

Mistake 2: forgetting to update the head pointer after inserting at the front or deleting the first node. The head must always point to the first valid node.

错误 2：在表头插入或删除第一个节点后忘记更新头指针。头指针必须始终指向第一个有效节点。

Mistake 3: not drawing null clearly in diagrams. Always indicate null with a ground symbol or the word ‘null’ to show where the list terminates.

错误 3：在图中未清晰画出 null。务必使用接地符号或单词 null 标明链表的终止位置。

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

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

IGCSE CCEA Computer Science: Linked Lists – Key Exam Points | IGCSE CCEA 计算机：链表 考点精讲