Linked Lists in A-Level CCEA Computer Science | A-Level CCEA 计算机：链表考点精讲

📚 Linked Lists in A-Level CCEA Computer Science | A-Level CCEA 计算机：链表考点精讲

Linked lists are a fundamental dynamic data structure in computer science, allowing data to be stored in non-contiguous memory locations through nodes connected by pointers. In the CCEA A-Level Computer Science specification, understanding how linked lists work, their implementation, and their advantages over static arrays is essential for both exam success and practical programming. This article breaks down every key concept, operation, and exam tip you need to master linked lists.

链表是计算机科学中一种基本的动态数据结构，通过由指针连接的节点将数据存储在非连续的内存位置中。在 CCEA A-Level 计算机科学考试大纲中，理解链表的工作原理、实现方式以及相对于静态数组的优势，对于考试成功和实际编程都至关重要。本文将详细解析你需要掌握的每一个核心概念、操作和考试技巧。

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

A linked list is a collection of nodes, where each node contains a data field and at least one pointer field that stores the memory address of the next node in the sequence. Unlike arrays, linked list elements are not stored in consecutive memory locations, which allows the structure to grow or shrink dynamically at runtime without the need to pre-allocate a fixed block of memory.

链表是一个节点的集合，每个节点包含一个数据字段和至少一个指针字段，该指针存储序列中下一个节点的内存地址。与数组不同，链表元素不存储在连续的内存位置中，这使得该结构能在运行时动态增长或收缩，而无需预先分配固定内存块。

The first node is called the head, and it is the only entry point to the list. The last node points to null (or a sentinel value), indicating the end of the list. In languages without built-in garbage collection, careful management of pointers is vital to avoid memory leaks.

第一个节点称为头节点，它是访问链表的唯一入口。最后一个节点指向 null（或一个哨兵值），表示链表的结束。在没有内置垃圾回收的语言中，小心地管理指针对于避免内存泄漏至关重要。

2. Singly Linked Lists | 单向链表

A singly linked list contains nodes that each hold a single pointer linking to the next node. Traversal can only be done in one direction—from the head to the tail. This simplicity makes it memory-efficient (only one pointer per node) but limits certain operations.

单向链表中的每个节点只包含一个指向下一个节点的指针。遍历只能单向进行——从头节点到尾节点。这种简单性使其内存效率较高（每个节点只有一个指针），但限制了某些操作。

The typical structure for a singly linked list node can be thought of as:
Node: [ Data | Next ]

单向链表节点的典型结构可以理解为：节点: [ 数据 | 下一个 ]

To delete a node, you must have a pointer to the previous node, because singly linked lists cannot go backwards. This leads to the common exam question of implementing deletion given only the head pointer.

要删除一个节点，必须有一个指向前一个节点的指针，因为单向链表不能向后移动。这就产生了考试中常见的问题：在仅给定头指针的情况下实现删除操作。

3. Doubly Linked Lists | 双向链表

In a doubly linked list, each node contains two pointers: one to the next node (next) and one to the previous node (prev). This bidirectional linkage makes both forward and backward traversal possible, and simplifies operations such as deletion, because you can access the preceding node directly from the target node.

在双向链表中，每个节点包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这种双向链接使得向前和向后遍历都成为可能，并简化了删除等操作，因为你可以直接从目标节点访问其前驱节点。

Node structure: [ Prev | Data | Next ]

节点结构：[ 前驱 | 数据 | 后继 ]

However, the extra pointer increases memory overhead. In CCEA exams, you may be asked to compare the two types of linked lists in terms of space complexity and the ease of implementing specific operations like reversing the list.

然而，额外的指针增加了内存开销。在 CCEA 考试中，你可能会被要求比较这两种链表在空间复杂度以及实现特定操作（如反转链表）的难易程度方面的差异。

4. Circular Linked Lists | 循环链表

A circular linked list is a variation where the last node points back to the head node, forming a closed loop. In a circular singly linked list, the next pointer of the tail node references the head; in a circular doubly linked list, the prev pointer of the head points to the tail, and the next pointer of the tail points to the head.

循环链表是一种变体，其中最后一个节点指回头节点，形成一个闭环。在循环单向链表中，尾节点的 next 指针指向头节点；在循环双向链表中，头节点的 prev 指针指向尾节点，尾节点的 next 指针指向头节点。

This structure is useful for applications that require continuous cycling through a set of items, such as in the scheduling of processes or turn-based games. Traversal must be carefully controlled to avoid infinite loops.

这种结构对于需要循环访问一组项目的应用很有用，例如进程调度或回合制游戏。遍历时必须小心控制，以避免无限循环。

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

An array is a static data structure: its size is fixed at compile time (in many lower-level implementations) and elements are stored contiguously. A linked list is a dynamic data structure capable of growing and shrinking during program execution, using pointers to allocate and deallocate nodes on the heap.

数组是一种静态数据结构：其大小在编译时（在许多底层实现中）就已确定，且元素连续存储。链表是一种动态数据结构，能够在程序执行期间利用指针在堆上分配和释放节点，从而动态增长和收缩。

Property / 属性	Array / 数组	Linked List / 链表
Memory allocation / 内存分配	Contiguous (static) / 连续（静态）	Non-contiguous (dynamic) / 非连续（动态）
Size flexibility / 大小灵活性	Fixed at creation / 创建时固定	Dynamic, can grow/shrink / 动态增减
Random access / 随机访问	O(1) / 常数时间	O(n) / 线性时间
Memory overhead / 内存开销	None (just data) / 无（仅数据）	Extra pointer(s) per node / 每个节点额外指针
Insertion/Deletion at head / 头部插入/删除	O(n) shifting required / O(n) 需移动	O(1) / 常数时间

6. Node Representation and Creation | 节点的表示与创建

In exam pseudocode or Python/Java implementations, a node is typically represented as a class or record with a data field and a pointer (reference) field. For a singly linked list node, the minimal definition in a Python-like syntax would be:

在考试伪代码或 Python/Java 实现中，节点通常表示为一个具有数据字段和指针（引用）字段的类或记录。对于单向链表节点，Python 风格的最小定义如下：

class Node:
self.data = value
self.next = None

For a doubly linked list node, an extra self.prev attribute is included. CCEA exam questions often ask candidates to trace or write code that creates new nodes and connects them by updating pointer fields. Remember that assigning a new node’s next pointer must happen before the new node replaces an existing node to avoid broken links.

对于双向链表节点，会额外包含一个 self.prev 属性。CCEA 考题常要求考生追踪或编写创建新节点并通过更新指针字段连接它们的代码。请记住，分配新节点的 next 指针必须在新节点替换现有节点之前进行，以避免断开链接。

7. Traversal Algorithms | 遍历算法

Traversing a linked list involves starting at the head and following the next pointers until a null is encountered. The key exam pitfall is forgetting to check that the current node is not null before accessing its data, which can cause a runtime error on an empty list.

遍历链表需要从头节点开始，沿着 next 指针前进，直到遇到 null。考试中常见的问题是忘记在访问当前节点数据之前检查它是否为 null，这可能在空链表上导致运行时错误。

A basic traversal algorithm in pseudocode:

CURRENT = HEAD
WHILE CURRENT ≠ NULL
OUTPUT CURRENT.DATA
CURRENT = CURRENT.NEXT
ENDWHILE

Traversal complexity is O(n). To find a specific element, you must continue traversing and compare the data field with the target value. Binary search is not possible on a standard linked list due to lack of random access.

遍历的时间复杂度是 O(n)。要查找特定元素，你必须继续遍历并将数据字段与目标值进行比较。由于缺乏随机访问，标准链表无法进行二分搜索。

8. Insertion Operations | 插入操作

Inserting a node into a linked list can happen at the head, at the tail, or at a specific position in between. Head insertion in a singly linked list is O(1) – simply redirect the new node’s next to the old head, then update the head pointer to the new node.

向链表中插入一个节点可以发生在头部、尾部或中间的特定位置。在单向链表中，头部插入的时间复杂度是 O(1) – 只需将新节点的 next 指向旧头节点，然后更新头指针指向新节点即可。

Inserting at a given index (i.e., after the n-th node) requires traversing to the (n-1)th node, then adjusting pointers. The steps are:

Create the new node.
Set new_node.next = prev_node.next.
Set prev_node.next = new_node.

在给定下标处插入（即在第 n 个节点之后）需要遍历到第 (n-1) 个节点，然后调整指针。步骤如下：

创建新节点。
设置 new_node.next = prev_node.next。
设置 prev_node.next = new_node。

If the insertion is after a specific node given by reference, the operation is O(1); if given by value or index, it is O(n) due to the traversal step. In doubly linked lists, you must also update the prev pointer of the next node (if it exists).

如果插入位置是通过引用给定的特定节点之后，则操作是 O(1)；如果是按值或下标给定，则由于需要遍历，时间复杂度为 O(n)。在双向链表中，还必须更新下一个节点的 prev 指针（如果存在）。

9. Deletion Operations | 删除操作

Deleting a node from a singly linked list usually requires a pointer to the node immediately before the one to be deleted, because you must bypass the deleted node by setting prev.next = curr.next. A common exam task is to delete a specific value: traverse until the value is found while keeping track of the previous node, then adjust the pointers.

从单向链表中删除一个节点通常需要一个指向待删节点前驱节点的指针，因为你必须通过设置 prev.next = curr.next 来绕过被删除的节点。考试中常见的任务是删除特定值：在遍历寻找该值的同时跟踪前一个节点，然后调整指针。

Deleting the head node is a special case: you simply move the head pointer to head.next. For bounded memory management, the removed node should be freed (in languages like C) or dereferenced (in Python/Java, left for garbage collection). CCEA mark schemes often reward identifying these special cases.

删除头节点是一种特殊情况：你只需将头指针移动到 head.next。对于有界内存管理，被移除的节点应该被释放（在 C 等语言中）或取消引用（在 Python/Java 中，留给垃圾回收处理）。CCEA 的评分标准通常会奖励识别这些特殊情况的做法。

10. Reversing a Linked List | 反转链表

Reversing a singly linked list is one of the most frequently tested algorithms. The iterative approach uses three pointers: previous, current, and next. You iterate through the list, and for each node, temporarily store next, then point current.next to previous, and finally advance previous and current one step forward.

反转单向链表是最常考察的算法之一。迭代方法使用三个指针：previous、current 和 next。你遍历链表，对每个节点临时存储 next，然后将 current.next 指向 previous，最后将 previous 和 current 向前推进一步。

PREV = NULL
CURR = HEAD
WHILE CURR ≠ NULL
  NEXT = CURR.NEXT
  CURR.NEXT = PREV
  PREV = CURR
  CURR = NEXT
ENDWHILE
HEAD = PREV

This reverses the list in-place with O(n) time and O(1) extra space. Understanding this algorithm deepens your insight into pointer manipulation and is excellent preparation for the CCEA A2 paper.

这可以在 O(n) 时间和 O(1) 额外空间内原地反转链表。理解这个算法能加深你对指针操作的理解，并为 CCEA A2 考试做好充分准备。

11. Comparing Linked Lists and Arrays for Exam Questions | 考试题中链表与数组的比较

CCEA often includes comparison questions that ask you to discuss the suitability of linked lists versus arrays for a given scenario. Key points include:

Linked lists excel when frequent insertions and deletions are required and the maximum number of elements is unknown.
Arrays provide constant-time access by index, making them better for applications like lookup tables or matrices.
Linked lists use more memory per element (overhead of pointers).
Arrays enable efficient cache performance due to spatial locality; linked lists do not.

CCEA 经常包含比较题，要求你讨论链表与数组在给定场景下的适用性。要点包括：

当需要频繁进行插入和删除且元素最大数量未知时，链表表现出色。
数组支持常数时间的索引访问，因此更适合查找表或矩阵等应用。
链表每个元素占用更多内存（指针开销）。
数组由于空间局部性，能实现高效的缓存性能；链表则无法做到。

These comparisons are particularly relevant in the context of abstract data types like stacks, queues, and priority queues, which can be implemented using either structure, each with different trade-offs.

这些比较在栈、队列和优先队列等抽象数据类型的上下文中尤其相关，因为可以使用任一结构实现它们，且各自有不同的权衡。

12. Exam Tips and Common Mistakes | 考试技巧与常见错误

When tackling CCEA linked list questions, always initialise pointers clearly and include boundary condition checks (empty list, single element, head/tail operations). Drawing diagrams on the exam paper can help keep track of pointer reassignments.

在解答 CCEA 链表题时，始终清晰地初始化指针，并包含边界条件检查（空链表、单个元素、头尾操作）。在试卷上画图有助于跟踪指针重新赋值。

Common student mistakes include:

Losing the reference to the next node before reassigning, causing the rest of the list to be orphaned.
Forgetting to handle the head as a special case during deletion or insertion at the beginning.
Confusing the data and pointer fields when tracing.
Assuming arrays are always faster – specifically, overlooking that insertion at the start of an array forces O(n) shifts.

学生的常见错误包括：

在重新赋值之前丢失了指向下一个节点的引用，导致剩余链表丢失。
在开头进行删除或插入时忘记将头节点作为特殊情况处理。
在追踪时混淆数据字段和指针字段。
认为数组总是更快——特别是忽略了在数组开头插入会导致 O(n) 的元素移动。

Practice writing algorithms for both singly and doubly linked lists, as well as reasoning about circular list termination conditions. Thorough understanding of pointer manipulation will also help in the programming project component.

练习单向链表和双向链表的算法，并推理循环链表的终止条件。对指针操作的透彻理解也将对编程项目部分有所帮助。

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

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

Linked Lists in A-Level CCEA Computer Science | A-Level CCEA 计算机：链表 考点精讲