GCSE CCEA Computer Science: Linked Lists | 链表考点精讲

📚 GCSE CCEA Computer Science: Linked Lists | 链表考点精讲

Linked lists are dynamic data structures that play a key role in GCSE CCEA Computer Science. Unlike arrays, linked lists use nodes connected by pointers, allowing efficient insertion and deletion of data without needing to shift elements. This guide will walk you through everything you need to know about linked lists, from the basic structure to typical exam questions, helping you build confidence and achieve top marks.

链表是动态的数据结构，在GCSE CCEA计算机科学中占有重要地位。与数组不同，链表通过指针连接的节点来存储数据，无需移动元素即可高效地插入和删除数据。本指南将带你梳理链表的所有核心知识，从基本结构到常见考题，帮助你建立信心，获取高分。

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

A linked list is a sequence of data elements, called nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. The list is dynamic in size: nodes can be created and destroyed at runtime. This makes linked lists particularly useful when the amount of data to be stored is not known in advance or changes frequently.

链表是由一系列称为“节点”的数据元素组成的序列，每个节点包含数据以及指向序列中下一个节点的引用（或指针）。链表的大小是动态的：节点可以在程序运行时创建和销毁。当需要存储的数据量未知或频繁变化时，链表尤其有用。

2. Basic Structure: Nodes and Pointers | 基本结构：节点与指针

A node is the fundamental building block of a linked list. It typically contains two fields: the data field (which holds the actual information, such as an integer or a string) and the next pointer field (which stores the memory address of the next node, or NULL/none if it is the last node). In diagrams, nodes are often drawn as boxes divided into two parts.

节点是链表的基本构建块。它通常包含两个域：数据域（存储实际信息，如整数或字符串）和下一个指针域（存储下一个节点的内存地址，如果是最后一个节点则为NULL或none）。在图表中，节点通常画成被分成两部分的方框。

Data: The payload, e.g. 5 or “Alice”. | 数据：有效载荷，例如5或”Alice”。
Pointer/Next: The link to the successor node. | 指针/下一个：指向后继节点的链接。

Node: [ Data | Next ]

A node in memory: a block with a data value and a pointer. | 内存中的节点：一个带有数据值和指针的数据块。

3. The Head Pointer | 头指针

The head pointer (or start pointer) is a special variable that stores the memory address of the first node in the list. If the list is empty, the head pointer contains NULL. Losing the head pointer means you lose access to the entire list, as the only way to reach a node is by following pointers from the head. In exam questions, maintaining the head pointer correctly is crucial.

头指针（或起始指针）是一个特殊的变量，存储链表中第一个节点的内存地址。如果链表为空，则头指针包含NULL。丢失头指针意味着失去对整个链表的访问，因为到达任意节点的唯一方法是从头开始跟随指针。在考题中，正确维护头指针至关重要。

For example, in pseudocode: head = NULL means the list is empty. After adding the first node, head points to that node. | 例如，在伪代码中：head = NULL 表示链表为空。添加第一个节点后，head 将指向该节点。

4. Traversing a Linked List | 遍历链表

Traversal means visiting each node in the list, one after another, starting from the head. A common way is to use a temporary pointer variable (often called current or ptr) that moves along the list. In pseudocode: set current = head; while current != NULL, process the data and then move current = current.next. Traversal is essential for operations like searching, counting, or displaying all items.

遍历是指从头部开始逐个访问链表中的每个节点。常用的方法是使用一个临时指针变量（经常命名为current或ptr）沿着链表移动。在伪代码中：设置current = head；当current != NULL时，处理数据，然后移动current = current.next。遍历对于搜索、计数或显示所有项等操作至关重要。

Time complexity to visit all nodes is O(n). | 访问所有节点的时间复杂度为O(n)。
You cannot go backwards in a singly linked list without extra mechanisms. | 在单向链表中，如果没有额外机制，无法向后移动。

5. Inserting Nodes | 插入节点

One of the main advantages of linked lists is efficient insertion. To insert a new node, you only need to adjust the pointer of the preceding node to point to the new node, and set the new node’s pointer to the following node. No data shifting is required. There are three typical insertion cases:

链表的主要优势之一是高效插入。要插入一个新节点，你只需调整前一个节点的指针使其指向新节点，并设置新节点的指针指向后续节点。无需移动数据。有三种典型的插入情况：

Case	Description	Key steps
At the beginning	New node becomes the first node.	newNode.next = head; head = newNode
At the end	New node is attached after the last node.	traverse to last node; last.next = newNode; newNode.next = NULL
In the middle	New node is placed between two existing nodes.	newNode.next = previous.next; previous.next = newNode

6. Deleting Nodes | 删除节点

Deletion also requires pointer adjustment without moving data. To delete a node, you need to locate it and make the previous node’s pointer skip over it, pointing directly to the node after the one being deleted. The three deletion cases are:

删除同样只需调整指针，无需移动数据。要删除一个节点，你需要找到它，并让前一个节点的指针跳过它，直接指向被删节点后面的节点。三种删除情况如下：

Delete the first node: head = head.next (the old head is abandoned). | 删除第一个节点：head = head.next（旧头部被丢弃）。
Delete a middle node: previous.next = current.next. | 删除中间节点：previous.next = current.next。
Delete the last node: previous.next = NULL (found after traversal). | 删除最后一个节点：previous.next = NULL（遍历后找到）。

Remember that in a real programming language, you might also need to free the memory of the deleted node if the system does not use garbage collection. In GCSE pseudocode, just updating the pointers is enough. | 请记住，在实际编程语言中，如果系统不使用垃圾回收机制，你可能还需要释放被删除节点的内存。在GCSE伪代码中，只需更新指针即可。

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

Understanding the differences between linked lists and arrays is a favourite exam topic. The table below summarises the key comparisons:

理解链表和数组之间的区别是考试中的热门考点。下表总结了关键对比：

Feature	Array	Linked List
Size	Fixed (static) or dynamic resizing is costly.	Dynamic; nodes added/removed easily.
Memory	Contiguous block; may waste space if not full.	Non-contiguous; extra memory for pointers.
Access	Random access O(1) via index.	Sequential access O(n) must traverse.
Insert/Delete	Requires shifting elements O(n).	Adjust pointers O(1) if position known.

8. Singly, Doubly and Circular Lists (CCEA Scope) | 单向、双向及循环链表（CCEA考点范围）

The CCEA specification mainly focuses on singly linked lists, but you should be aware that other types exist. A doubly linked list has nodes with both next and previous pointers, allowing traversal in both directions. A circular linked list is one where the last node points back to the first node instead of NULL. These variations can be asked about in scenario-based questions, so understanding their structure is beneficial.

CCEA考纲主要关注单向链表，但你也应了解其他类型的存在。双向链表的节点同时拥有下一个和前一个指针，允许双向遍历。循环链表的最后一个节点指回头节点而非NULL。这些变体可能出现在基于场景的题目中，因此理解它们的结构大有益处。

Singly linked: node → node → NULL. | 单向：节点 → 节点 → NULL。
Doubly linked: node ↔ node ↔ NULL (or with previous pointers). | 双向：节点 ↔ 节点 ↔ NULL（或带有前向指针）。
Circular: last node points back to head (no NULL at end). | 循环：最后一个节点指回头部（尾部无NULL）。

9. Implementing Linked Lists in Pseudocode | 用伪代码实现链表

Exam questions often require you to read or write pseudocode for linked list operations. You should be comfortable with defining a node type, creating nodes, and manipulating pointers. Below is a typical way to define a node and an insertion routine:

考试题经常要求你阅读或编写链表操作的伪代码。你应该熟悉节点类型的定义、节点的创建以及指针的操作。下面是定义节点和插入例程的典型方式：

Node definition: | 节点定义：

TYPE Node
DECLARE data : INTEGER
DECLARE next : INTEGER (or reference)
END TYPE

Insert at beginning: | 插入开头：

PROCEDURE InsertAtHead(BYREF head, value)
CREATE newNode
newNode.data ← value
newNode.next ← head
head ← newNode
END PROCEDURE

Practice drawing pointer diagrams alongside such pseudocode; visualisation helps prevent pointer errors, which examiners love to test. | 在编写此类伪代码的同时，练习绘制指针示意图；可视化有助于避免指针错误，而这正是考官喜欢考查的。

10. Typical Exam Traps and How to Avoid Them | 常见考试陷阱与规避方法

CCEA exam questions on linked lists often include common pitfalls. Be mindful of these traps:

CCEA关于链表的考题经常包含常见陷阱。请注意以下问题：

Losing the head pointer: If you override head without saving the previous first node, you lose the whole list. Always use a temporary variable when modifying the head. | 丢失头指针：如果你覆盖head而没有保存之前的第一个节点，则整个链表丢失。修改头部时务必使用临时变量。
Dangling pointers: When deleting, make sure the previous node’s pointer properly bypasses the deleted node. A node left pointing to a deleted location can cause logical errors. | 悬空指针：删除时，确保前一个节点的指针正确绕过被删节点。指向前向已删除位置的节点可能导致逻辑错误。
Empty list operations: Always check if the list is empty (head == NULL) before performing delete or traversal. | 空链表操作：执行删除或遍历之前，始终检查链表是否为空（head == NULL）。
Off-by-one in traversal: Make sure your loop condition stops exactly at NULL, not too early or too late. | 遍历中的差一错误：确保循环条件恰好在NULL处停止，不早也不晚。

11. Linked Lists in Context: Stacks and Queues | 链表在实际应用中的使用：栈和队列

Linked lists are often used to implement other abstract data types, such as stacks and queues. A stack (LIFO) can be implemented using a linked list by always inserting and deleting at the head. A queue (FIFO) can be implemented using two pointers: a head for deletion and a tail for insertion. This demonstrates the versatility of linked lists and is a common connection question in CCEA papers.

链表经常用于实现其他抽象数据类型，如栈和队列。栈（后进先出）可以通过在头部始终进行插入和删除的链表来实现。队列（先进先出）可以使用两个指针实现：head用于删除，tail用于插入。这体现了链表的多功能性，也是CCEA试卷中常见的联系性题目。

For example, pushing onto a stack is like insert-at-head, and popping is like delete-the-first-node. | 例如，压栈相当于在头部插入，弹栈相当于删除第一个节点。

12. Revision Summary and Top Tips | 复习总结与应试技巧

To excel in linked list questions on your GCSE CCEA Computer Science exam, remember the following:

要在GCSE CCEA计算机科学考试中出色完成链表题目，请牢记以下几点：

Draw diagrams: always sketch the nodes and pointers when tackling a problem. | 画图：解决问题时，始终画出节点和指针的草图。
Understand the role of NULL: it marks the end of the list and is essential for termination conditions. | 理解NULL的作用：它标记链表的结束，是终止条件的关键。
Know the algorithms for insertion, deletion, and traversal by heart, including the necessary pointer updates. | 熟记插入、删除和遍历的算法，包括必要的指针更新。
Compare linked lists with arrays: be ready to discuss relative advantages in terms of memory, speed, and flexibility. | 将链表与数组进行比较：准备好讨论它们在内存、速度和灵活性方面的相对优势。
Watch out for edge cases: empty list, one single node, and operations at the very start or very end. | 注意边界情况：空链表、只有一个节点，以及在链表最前或最后进行的操作。

By mastering pointer manipulation and practising past paper questions, you will be able to handle any linked list challenge confidently. | 通过掌握指针操作并练习历年真题，你将能够自信地应对任何链表考题。

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

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

GCSE CCEA Computer Science: Linked Lists | 链表考点精讲