Linked Lists: Exam Essentials for IB & AQA Computer Science | 链表：IB与AQA计算机考试要点

📚 Linked Lists: Exam Essentials for IB & AQA Computer Science | 链表：IB与AQA计算机考试要点

Linked lists form a fundamental part of the data structures syllabus in both AQA A-level and IB Diploma Computer Science. Understanding how nodes are linked dynamically through pointers is essential for mastering topics such as memory management, efficiency analysis, and abstract data types (ADTs). This article provides exam-focused coverage of linked lists, including operations, complexities, and comparison with arrays, tailored to both IB and AQA specifications.

链表是 AQA A-level 和 IB 文凭计算机科学课程中数据结构部分的基础内容。理解节点如何通过指针动态连接，对于掌握内存管理、效率分析和抽象数据类型等主题至关重要。本文针对 IB 和 AQA 考纲，精讲链表的操作、复杂度及其与数组的比较，帮助考生全面复习。

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

A linked list is a linear collection of data elements, called nodes, where each node points to the next node via a reference. The list maintains a reference to the first node, known as the head, which provides the entry point for traversal.

链表是一种线性数据元素集合，每个元素称为节点，每个节点通过引用指向下一个节点。链表维护一个指向第一个节点的引用，称为头节点，作为遍历的入口点。

Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, nodes are individually allocated in heap memory and connected via pointers. This dynamic structure makes insertion and deletion efficient, but direct access by index is not possible.

与数组不同，链表不会在连续内存位置存储元素。节点在堆内存中单独分配，通过指针连接。这种动态结构使得插入和删除效率很高，但无法按索引直接访问。

In IB and AQA syllabi, you are expected to describe linked lists as an example of a dynamic data structure and explain how references implement the logical ordering of items.

在 IB 和 AQA 大纲中，你需要将链表描述为动态数据结构的一个例子，并解释引用如何实现元素的逻辑顺序。

2. Node Structure and Pointers | 节点结构与指针

A node in a singly linked list contains two fields: a data field holding the value, and a next field holding a reference to the following node. The last node has its next field set to nil / null, indicating the end of the list.

单向链表中的节点包含两个字段：存放值的数据域，以及存放指向下一个节点引用的 next 域。最后一个节点的 next 域设为 nil / null，表示链表结束。

We can visualise a node as:

Node = [data | next]

我们可以将节点可视化如下：

节点 = [data | next]

The head pointer stores the address of the first node. If the list is empty, head = null. Some implementations also maintain a tail pointer for efficient appending at the end.

头指针存储第一个节点的地址。若链表为空，head = null。某些实现还会维护一个尾指针，以便于高效地在末尾追加。

In an object-oriented context, a node is typically implemented as a class with two attributes. In pseudocode for IB exams, you may see record or class definitions using TYPE…ENDTYPE.

在面向对象情境下，节点通常实现为具有两个属性的类。在 IB 考试的伪代码中，你可能会看到使用 TYPE…ENDTYPE 的记录或类定义。

3. Singly Linked List Operations | 单向链表操作

The core operations examined in both IB and AQA specifications are insertion, deletion, traversal, and search. Understanding these algorithms is vital for answering trace-table and pseudocode questions.

IB 和 AQA 大纲中考查的核心操作包括插入、删除、遍历和搜索。理解这些算法对于回答跟踪表和伪代码题目至关重要。

Traversal: Start at head and follow next pointers until reaching null. At each node, access the data field. Time complexity is O(n).

遍历：从头节点开始，沿着 next 指针前进直到 null。在每个节点访问数据域。时间复杂度为 O(n)。

Search: Traverse the list while comparing each node’s data with the target key. Success returns the node; failure returns null after full traversal. Average and worst-case time: O(n).

搜索：遍历链表，同时将每个节点的数据与目标键比较。成功时返回该节点；完全遍历后仍未找到则返回 null。平均和最坏情况时间：O(n)。

Insertion: Adjust pointers to include a new node at the desired position. This can be at the head, tail, or a specific index. Pointer manipulation is O(1) once the position is found.

插入：调整指针以在所需位置包含新节点。可以在头部、尾部或特定索引处进行。一旦找到位置，指针操作的时间为 O(1)。

Deletion: Modify the next pointer of the previous node to bypass the deleted node. Actual memory freeing depends on the programming environment and is not always tested in pseudocode.

删除：修改前一个节点的 next 指针以绕过被删节点。实际内存释放取决于编程环境，在伪代码中不总是考查。

4. Insertion at Head, Tail and Middle | 插入头部、尾部和中间

Insert at head: Create a new node, set its next to the current head, then update head to point to the new node. This is O(1) and extremely efficient.

在头部插入：创建一个新节点，将其 next 设为当前 head，然后更新 head 指向新节点。此操作为 O(1)，非常高效。

Insert at tail: If a tail pointer exists, set tail.next to the new node, then update tail. Otherwise, traverse to the end (O(n)) and attach the new node. Maintaining a tail reference reduces insertion to O(1).

在尾部插入：如果存在尾指针，将 tail.next 设为新节点，然后更新 tail。否则，遍历至末尾 (O(n)) 并附加新节点。维护尾引用可将插入简化为 O(1).

Insert at index k: Traverse to the (k-1)th node. Set new.next = current.next, and then current.next = new. Traversal takes O(k) time; pointer adjustments are O(1).

在索引 k 处插入：遍历到第 (k-1) 个节点。设置 new.next = current.next，然后 current.next = new。遍历耗时 O(k)，指针调整为 O(1).

In IB Paper 2 and AQA Paper 1 pseudocode, you must be able to write these algorithms clearly, handling edge cases such as empty list or insertion at position 0.

在 IB 试卷 2 和 AQA 试卷 1 的伪代码中，你必须能够清晰地书写这些算法，并处理边缘情况，如空链表或在位置 0 插入。

5. Deletion Operations | 删除操作

Delete from head: Simply update head to head.next. The original head becomes unreachable and is garbage collected in languages like Java. O(1) time.

删除头部：只需将 head 更新为 head.next。原头节点变为不可达，在 Java 等语言中会被垃圾回收。时间 O(1).

Delete from tail: If only head pointer exists, traverse to the second-last node and set its next to null. Without a tail, this is O(n). With a tail and doubly linked list, deletion can be O(1).

删除尾部：若只有头指针，需遍历到倒数第二个节点并将其 next 设为 null。无尾指针时此操作为 O(n)。若为双向链表且有尾指针，删除可 O(1).

Delete by value: Traverse while maintaining a previous pointer. Once found, set previous.next = current.next. If the value is not found, the list remains unchanged. Time O(n).

按值删除：遍历时维护 previous 指针。找到后，设置 previous.next = current.next。若未找到值，链表保持不变。时间 O(n).

Deletion algorithms must consider special cases: deleting the only node leaves head = null. Both IB and AQA mark schemes reward handling of these boundary conditions.

删除算法需考虑特殊情况：删除唯一节点后 head = null。IB 和 AQA 的评分标准均对处理这些边界条件给予嘉奖。

6. Traversal and Searching | 遍历与搜索

Traversal is the process of visiting each node sequentially from head to tail. It is the backbone of all other operations, including searching, counting, and printing the list.

遍历是从头到尾依次访问每个节点的过程。它是所有其他操作的基础，包括搜索、计数和打印链表。

Typical traversal pseudocode in IB/AQA style uses a loop:

current = head
while current != null
    OUTPUT current.data
    current = current.next
endwhile

典型的 IB/AQA 风格遍历伪代码使用循环：

current = head
while current != null
    输出 current.data
    current = current.next
结束循环

Searching extends traversal by adding a comparison inside the loop. A flag or early exit is used when the item is found. If the item is not found after full traversal, the algorithm returns an appropriate indicator.

搜索在遍历基础上增加循环内的比较。找到时使用标志位或提前退出。若完全遍历后未找到，算法返回适当的指示符。

IB often asks for recursive search implementations. The base case is when the node is null or the data matches; the recursive step moves to node.next. Be aware of stack overflow risks for long lists.

IB 常要求递归搜索实现。基本情况是节点为 null 或数据匹配；递归步骤移至 node.next。注意长链表可能造成栈溢出风险。

7. Doubly Linked Lists | 双向链表

A doubly linked list node contains an additional prev pointer, enabling traversal in both directions. This added flexibility simplifies tail deletion and makes certain algorithms more intuitive.

双向链表节点包含额外的 prev 指针，可实现双向遍历。增加的灵活性简化了尾部删除，并使某些算法更直观。

Node structure: [prev | data | next]. Head.prev = null, Tail.next = null. Insertion and deletion require updating two pointer pairs, but the complexities remain O(1) per operation once the node is located.

节点结构：[prev | data | next]。Head.prev = null，Tail.next = null。插入和删除需要更新两对指针，但一旦找到节点，每次操作复杂度仍为 O(1)。

Common uses include implementation of undo/redo features, browser history, and music playlist navigation. In exams, you may be asked to write deletion routines for a given node in a doubly linked list.

常见用途包括实现撤销/重做功能、浏览器历史记录和音乐播放列表导航。考试中可能要求为双向链表中的给定节点编写删除例程。

The extra pointer consumes more memory than a singly linked list, creating a space-time trade-off. Both IB and AQA expect you to compare these variants.

额外指针比单向链表消耗更多内存，形成时空权衡。IB 和 AQA 都要求你比较这些变体。

8. Circular Linked Lists | 循环链表

In a circular singly linked list, the last node’s next pointer references the head instead of null. This creates a ring structure, which is useful for applications requiring repetitive cycling, such as round-robin scheduling.

在循环单向链表中，最后一个节点的 next 指针引用头节点而不是 null。这形成一个环状结构，适用于需要重复循环的应用，如轮询调度。

A circular doubly linked list connects head.prev to tail and tail.next to head. Insertion algorithms must maintain the circular links, but traversal condition changes from current != null to current != head.

循环双向链表将 head.prev 连接到 tail，tail.next 连接到 head。插入算法必须维护环形链接，但遍历条件从 current != null 变为 current != head。

In IB Computer Science, circular linked lists are often discussed alongside static data structures to highlight dynamic memory usage. AQA may ask about their application in operating systems or multimedia players.

在 IB 计算机科学中，循环链表常与静态数据结构一起讨论，以突显动态内存使用。AQA 可能问及其在操作系统或多媒体播放器中的应用。

9. Comparison with Arrays | 与数组的比较

A fundamental exam topic is comparing linked lists with arrays. The following table summarises the key differences, which you should be able to explain in structured answers.

一个基本考题是比较链表与数组。下表总结了关键差异，你应该能够用结构化的答案进行解释。

Feature	Array	Linked List
Memory allocation	Static, contiguous	Dynamic, non-contiguous
Size	Fixed at creation	Grows and shrinks at runtime
Direct access	O(1) via index	O(n), sequential access
Insert/delete at start	O(n) due to shifting	O(1) with head pointer
Memory overhead	Minimal	Extra pointer per node

In exam conditions, always relate these features to a scenario. For example, if a program requires frequent resizing and insertion at the front, a linked list is preferred. If random access is essential, choose an array.

在考试中，务必将这些特征与场景关联。例如，若程序需要频繁调整大小和在前面插入，首选链表；若必须随机访问，则选择数组。

10. Time and Space Complexity | 时间复杂度与空间复杂度

Complexity analysis is a core requirement for both IB Paper 2 and AQA Paper 1. You must know Big O notation for standard operations.

复杂度分析是 IB 试卷 2 和 AQA 试卷 1 的核心要求。你必须了解标准操作的大 O 表示法。

Access by index: O(n) for linked lists because we must traverse. Search by value: O(n) on average. Insertion/Deletion at head: O(1). Insertion/Deletion at arbitrary position: O(n) to locate, O(1) to change pointers.

按索引访问：链表为 O(n)，因为必须遍历。按值搜索：平均 O(n)。在头部插入/删除：O(1)。在任意位置插入/删除：定位 O(n)，改变指针 O(1)。

Space complexity is O(n) for storing n elements. The constant factor is higher than arrays because each node stores an additional next pointer (and possibly prev). Typical sizes: on 64-bit systems, a singly linked node with a 4-byte integer and a pointer uses around 12–16 bytes.

空间复杂度存储 n 个元素为 O(n)。常数因子比数组高，因为每个节点存储额外的 next 指针（可能还有 prev）。典型大小：64位系统上，含 4 字节整数和一个指针的单向链表节点约占用 12-16 字节。

Do not confuse O(1) insertion with overall time; you must include the search time unless a direct reference exists. IB mark schemes often deduct marks for ignoring traversal cost.

不要混淆 O(1) 插入与总时间；除非存在直接引用，否则必须计入搜索时间。IB 评分方案常因忽略遍历开销而扣分。

11. Implementing Linked Lists in Pseudocode | 伪代码实现

Here is a typical IB-style pseudocode for a singly linked list insertion at the head. Note the use of TYPE definitions and pointer assignments.

以下是典型的 IB 风格伪代码，实现在头部插入单向链表。注意 TYPE 定义和指针赋值。

TYPE ListNode
    DECLARE data : INTEGER
    DECLARE next : ListNode*
ENDTYPE

PROCEDURE insertHead(BYREF head : ListNode*, data : INTEGER)
    newNode = new ListNode
    newNode.data = data
    newNode.next = head
    head = newNode
ENDPROCEDURE

对应的 IB 风格伪代码描述：

类型 ListNode
    声明 data : 整数
    声明 next : ListNode*
结束类型

过程 insertHead(引用传递 head : ListNode*, data : 整数)
    新建节点 = new ListNode
    新建节点.data = data
    新建节点.next = head
    head = 新建节点
结束过程

For AQA, pseudocode may follow a different syntax but the logic is the same. Practice writing search, insert-at-end, and delete functions in a consistent notation.

对于 AQA，伪代码可能遵循不同语法，但逻辑相同。练习用一致的符号书写搜索、在末尾插入和删除函数。

When implementing a linked list, always initialise the head to null. Use a loop for traversal and a trailing pointer for deletion. Clearly indicate cases where the list is empty or contains a single node.

实现链表时，务必将 head 初始化为 null。使用循环进行遍历，并使用尾随指针进行删除。清楚标明链表为空或只包含一个节点的情况。

12. Common Exam Questions and Pitfalls | 常见考题与易错点

Question 1: Explain why deleting the last node in a singly linked list is O(n). A: Because you must traverse to the second-last node to set its next to null; there is no direct back-link.

问题 1：解释为何在单向链表中删除最后一个节点是 O(n)。答：因为必须遍历到倒数第二个节点并将其 next 设为 null；没有直接的后向链接。

Question 2: Given a node pointer, can you delete it in O(1) from a singly linked list? A: Not directly unless it is the head or you can copy data from the next node (which fails for the tail).

问题 2：给定节点指针，能否在 O(1) 内从单向链表中删除该节点？答：不能直接实现，除非它是头节点或能从下一个节点复制数据（对尾节点无效）。

Common mistakes: forgetting to update head after deletion, losing reference to the rest of the list during insertion, and using wrong termination conditions (e.g., checking current.next != null instead of current != null).

常见错误：删除后忘记更新 head、插入时丢失对链表其余部分的引用，以及使用错误的终止条件（如检查 current.next != null 而非 current != null）。

In longer written answers, both exam boards expect you to justify choices between static and dynamic structures, and to discuss trade-offs such as memory usage versus speed.

在较长的书面回答中，两个考试局都期望你能证明在静态和动态结构之间选择的合理性，并讨论内存使用与速度之间的权衡。

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

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

Linked Lists: Exam Essentials for IB & AQA Computer Science | 链表：IB与AQA计算机考试要点