Linked Lists: Core Concepts for AQA A-Level Computer Science | 链表：AQA A-Level 计算机考点精讲

📚 Linked Lists: Core Concepts for AQA A-Level Computer Science | 链表：AQA A-Level 计算机考点精讲

A linked list is a dynamic data structure used to store an ordered collection of items. Unlike arrays, elements are not stored in contiguous memory locations. Instead, each element (node) contains a data field and a reference (pointer) to the next node in the sequence. This structure allows efficient insertion and deletion of nodes without shifting other elements, making it a fundamental concept in the AQA A-Level Computer Science specification.

链表是一种动态数据结构，用于存储有序的数据集合。与数组不同，链表中的元素并非存储在连续的内存位置。每个元素（节点）包含一个数据域和一个指向序列中下一个节点的引用（指针）。这种结构允许在不移动其他元素的情况下高效地插入和删除节点，因此成为 AQA A-Level 计算机科学课程中的一个基本概念。

1. Node Structure and Pointer Mechanics | 节点结构及指针机制

A node is the building block of a linked list. It typically consists of two components: a ‘data’ field holding the value, and a ‘next’ field storing the memory address of the subsequent node. In a doubly linked list, an additional ‘previous’ field is included.

节点是链表的基本构建单元。它通常包含两个部分：一个“数据”字段保存值，另一个“下一个”字段存储后继节点的内存地址。在双向链表中，还会增加一个“前一个”字段。

The pointer (or reference) is a variable that explicitly stores the memory address of another node. In pseudocode, we often represent this as an arrow: NodeA → NodeB. The last node in a singly linked list has its ‘next’ pointer set to null or None, indicating the end of the list.

指针（或引用）是一个变量，显式地存储另一个节点的内存地址。在伪代码中，我们通常用箭头表示：NodeA → NodeB。单向链表最后一个节点的“下一个”指针设置为空（null 或 None），以表示链表的末尾。

A key concept is the head pointer. This external reference points to the very first node. If the list is empty, the head pointer is set to null. Maintaining the head pointer is critical; losing it means losing access to the entire list.

一个关键概念是头指针。这个外部引用指向链表的第一个节点。如果链表为空，头指针设置为空。保持头指针至关重要；丢失头指针意味着无法访问整个链表。

---

2. Singly Linked Lists: Traversal and Basic Operations | 单向链表：遍历与基本操作

Traversal means visiting each node starting from the head and following ‘next’ pointers until null is reached. This is the only way to access elements, as direct indexing is not supported.

遍历是指从头节点开始，沿着“下一个”指针依次访问每个节点，直到遇到空指针。这是访问元素的唯一方式，因为链表不支持直接索引。

To insert a node at the beginning, create a new node, set its ‘next’ to the current head, and update the head pointer to the new node. The time complexity is O(1). Inserting at the end requires traversing to the last node (O(n) unless a tail pointer is maintained) and then updating its ‘next’ to the new node.

在开头插入节点时，创建一个新节点，将其“下一个”设为当前头节点，并将头指针更新为新节点。时间复杂度为 O(1)。在末尾插入需要遍历到最后一个节点（除非维护了尾指针，否则为 O(n)），然后将其“下一个”更新为新节点。

Deleting a node involves bypassing it. If deleting the node after a given node, simply set the current node’s ‘next’ to point to the node after the one being deleted. The deleted node becomes garbage (unreachable) and its memory is eventually freed by automatic garbage collection or explicit deallocation depending on the programming environment.

删除一个节点需要绕过它。如果要删除给定节点之后的节点，只需将当前节点的“下一个”指向被删除节点之后的节点。被删除的节点变成垃圾（不可达），其内存最终由自动垃圾回收或显式释放来回收，具体取决于编程环境。

---

3. Doubly Linked Lists and Bidirectional Navigation | 双向链表与双向导航

A doubly linked list node has three fields: data, a pointer to the next node, and a pointer to the previous node. This enables traversal in both forward and backward directions, enhancing flexibility for certain algorithms.

双向链表的节点有三个字段：数据、指向下一个节点的指针和指向前一个节点的指针。这使得可以向前和向后遍历，增强了某些算法的灵活性。

Insertion and deletion in a doubly linked list require updating more pointers. For example, to insert a node X between A and B, you must set X.next = B, X.prev = A, A.next = X, and B.prev = X. This extra bookkeeping makes the structure slightly more complex but allows O(1) deletion if a direct reference to the node is given.

在双向链表中插入和删除节点需要更新更多指针。例如，在 A 和 B 之间插入节点 X，必须设置 X.next = B，X.prev = A，A.next = X，以及 B.prev = X。这些额外的簿记使结构稍微复杂，但如果给出了对节点的直接引用，则允许 O(1) 的删除。

AQA specifications may ask students to implement or trace algorithms for doubly linked lists, focusing on correct pointer manipulation to avoid broken chains. A common pitfall is updating pointers in the wrong order, which can orphan nodes.

AQA 考试可能要求学生实现或追踪双向链表的算法，重点关注正确的指针操作以避免链断裂。一个常见的陷阱是以错误的顺序更新指针，这可能导致节点成为孤岛。

---

4. Circular Linked Lists: Closing the Loop | 循环链表：闭合循环

In a circular linked list, the last node’s ‘next’ pointer points back to the head node, forming a circle. There is no null reference at the end unless the list is empty. A circular singly linked list uses only ‘next’ pointers, while a circular doubly linked list connects both ends.

在循环链表中，最后一个节点的“下一个”指针指向头节点，形成一个环。除非链表为空，否则末尾没有空引用。单向循环链表仅使用“下一个”指针，而双向循环链表则两端相连。

A tail pointer is often used instead of a head pointer for efficient insertion at both ends. If the tail pointer references the last node, inserting at the front or the rear becomes O(1) because tail.next gives direct access to the head.

通常使用尾指针代替头指针，以便在两端进行高效插入。如果尾指针引用最后一个节点，那么插入到开头或末尾的时间复杂度为 O(1)，因为 tail.next 直接指向头节点。

This structure is ideal for applications that require repetitive cycling through a list, such as a round-robin scheduler in an operating system or a continuous music playlist.

这种结构非常适合需要反复循环遍历列表的应用场景，例如操作系统中的轮询调度程序或连续音乐播放列表。

---

5. Memory Allocation: The Heap and Dynamic Nature | 内存分配：堆与动态特性

Linked list nodes are dynamically allocated on the heap at runtime. This means memory is allocated when a node is created and can be freed when it is no longer needed. The size of the list can grow or shrink as required, avoiding the fixed-size limitation of static arrays.

链表节点在运行时动态地从堆（heap）中分配。这意味着内存是在创建节点时分配的，并在不再需要时释放。链表的大小可以根据需要增长或缩小，避免了静态数组的固定大小限制。

Unlike an array, which occupies a contiguous block of memory, linked list nodes are scattered throughout the heap. This eliminates the need for large contiguous memory but introduces a memory overhead per node for storing pointers. AQA exam questions may ask students to compare these memory characteristics.

与占用连续内存块的数组不同，链表节点分散在整个堆中。这消除了对大块连续内存的需求，但每个节点会因存储指针而产生内存开销。AQA 试题可能会要求学生比较这些内存特性。

The use of pointers means that linked lists are reference-based data structures. In languages like C# or Python (with explicit object references), manipulating a linked list involves assigning object references, which directly maps to the concept of pointers in pseudocode.

使用指针意味着链表是基于引用的数据结构。在 C# 或 Python（含有显式对象引用）等语言中，操作链表涉及分配对象引用，这直接映射到伪代码中指针的概念。

---

6. Linked Lists vs Arrays: A Comparative Analysis | 链表与数组：对比分析

The choice between linked lists and arrays depends on the intended operations. The table below summarises key trade-offs that are frequently assessed in AQA examinations.

在链表和数组之间进行选择取决于预期的操作。下表总结了 AQA 考试中经常评估的关键权衡。

Feature | 特性	Array | 数组	Linked List | 链表
Access time | 访问时间	O(1) direct indexing | O(1) 直接索引	O(n) sequential traversal | O(n) 顺序遍历
Insertion/Deletion at start | 在开头插入/删除	O(n) shifting required | O(n) 需要移位	O(1) pointer update | O(1) 更新指针
Memory usage | 内存使用	Fixed size, contiguous block | 固定大小，连续块	Dynamic size, scattered, extra pointer overhead | 动态大小，分散，额外指针开销
Cache performance | 缓存性能	Better spatial locality | 更好的空间局部性	Poor cache locality | 缓存局部性差

Arrays are more cache-friendly because they store elements sequentially in memory. Linked lists, however, excel when the number of elements is unknown in advance and frequent insertions/deletions occur at various positions, provided a pointer to the location is known.

数组对缓存更友好，因为它们在内存中顺序存储元素。然而，当元素数量事先未知且需要在不同位置频繁插入/删除时，只要已知该位置的指针，链表就表现出色。

---

7. Implementing Abstract Data Types: Stacks and Queues | 实现抽象数据类型：栈与队列

A linked list can be used as the underlying data structure for a stack. A stack follows Last-In-First-Out (LIFO) discipline. By inserting and removing nodes at the head of a singly linked list, push and pop operations both achieve O(1) complexity.

链表可用作栈的底层数据结构。栈遵循后进先出（LIFO）原则。通过在单向链表的头部插入和删除节点，入栈（push）和出栈（pop）操作都可达到 O(1) 的复杂度。

For a queue (First-In-First-Out, FIFO), we maintain both a head pointer for deletion (dequeue) and a tail pointer for insertion (enqueue). This ensures both operations are O(1). Without a tail pointer, enqueue would require O(n) traversal to reach the end.

对于队列（先进先出，FIFO），我们同时维护一个用于删除（出队）的头指针和一个用于插入（入队）的尾指针。这样可以确保两个操作都是 O(1)。如果没有尾指针，入队操作需要 O(n) 的遍历才能到达末尾。

In AQA exams, you may be asked to draw the linked list structure after a sequence of stack or queue operations, demonstrating how pointers are modified. Clearly indicating the new head or tail after each step is essential for full marks.

在 AQA 考试中，可能会要求你在一系列栈或队列操作之后画出链表结构，展示指针是如何修改的。在每一步之后清晰地标明新的头指针或尾指针对于获得满分至关重要。

---

8. Searching and Updating in Linked Lists | 链表中的查找与更新

Searching for a specific value in a linked list requires a linear traversal, starting from the head and comparing each node’s data field until a match is found or the end is reached. The worst-case complexity is O(n).

在链表中查找特定值需要进行线性遍历，从头节点开始，比较每个节点的数据字段，直到找到匹配项或到达末尾。最坏情况复杂度为 O(n)。

If the list is ordered, a linear search can stop early when the current element is greater than the target, but the complexity remains O(n) in the worst case. Binary search is not feasible on a standard linked list because direct middle-element access is impossible.

如果链表是有序的，线性搜索可以在当前元素大于目标值时提前停止，但最坏情况下复杂度仍为 O(n)。在标准链表中无法进行二分查找，因为无法直接访问中间元素。

Updating a node’s value once found is trivial O(1) after the O(n) search. In AQA algorithms, a ‘found’ boolean flag or a pointer to the node is often used to control the search loop and subsequent update.

找到节点后，更新其值是微不足道的 O(1) 操作（在 O(n) 搜索之后）。在 AQA 的算法中，经常使用一个“是否找到”的布尔标志或指向该节点的指针来控制搜索循环和后续的更新。

---

9. Common Pitfalls and Error Handling | 常见陷阱与错误处理

Handling an empty list is paramount. Before performing a deletion or traversal, always check if the head pointer is null. Attempting to access ‘head.next’ on an empty list results in a runtime null reference error.

处理空链表至关重要。在进行删除或遍历操作之前，始终检查头指针是否为空。在空链表上尝试访问“head.next”会导致运行时出现空引用错误。

When deleting the only node in a singly linked list, the head pointer must be set to null. Forgetting this step leaves a dangling head pointer referencing a freed node, which can cause unpredictable behaviour.

删除单向链表中唯一的节点时，必须将头指针设置为空。忘记这一步会使头指针悬空，引用一个已释放的节点，这可能导致不可预测的行为。

In doubly linked lists, ensuring that the ‘previous’ pointer of the head remains null and the ‘next’ pointer of the tail remains null is crucial for maintaining list integrity. Off-by-one errors during insertion loops are frequently tested in trace table questions.

在双向链表中，确保头节点的“前一个”指针保持为空，尾节点的“下一个”指针保持为空，对于维护链表的完整性至关重要。在插入循环中出现的“差一”错误经常在追踪表问题中进行测试。

---

10. Exam-Style Traversal and Pointer Tracing | 考试风格的遍历与指针追踪

A typical AQA question provides a diagram of linked nodes with values, and asks you to write the state after executing a pseudocode fragment. Carefully stepping through the code and updating each pointer on a scratch diagram is a reliable strategy.

一个典型的 AQA 题目会给出一个带有值的链表节点示意图，要求写出执行一段伪代码后的状态。仔细单步执行代码并在草图上更新每个指针是一种可靠的策略。

For example, given a list: 5 → 12 → 7 → null, and the instruction to insert 9 after the node with value 12. You create node(9), set node(9).next = node(12).next (which points to 7), then set node(12).next = node(9). The result is 5 → 12 → 9 → 7 → null.

例如，给定链表：5 → 12 → 7 → null，并要求在数值为 12 的节点之后插入 9。你创建节点(9)，设置 node(9).next = node(12).next（它指向 7），然后设置 node(12).next = node(9)。结果是 5 → 12 → 9 → 7 → null。

Trace tables are commonly used. Columns might include ‘head’, ‘current’, ‘temp’, and ‘output’. Students must be meticulous in recording how each pointer variable changes after a line of code, especially in iterative deletion or reversal algorithms.

追踪表很常用。列可能包括“头指针”、“当前指针”、“临时指针”和“输出”。学生必须一丝不苟地记录每行代码之后每个指针变量如何变化，特别是在迭代删除或反转算法中。

---

11. Advanced Topic: Recursive Operations on Linked Lists | 进阶主题：链表的递归操作

Although iteration is common, linked lists are inherently recursive data structures (a node plus a smaller linked list). Recursive algorithms can elegantly traverse, count, or reverse a list. For instance, a recursive length function: if head is null return 0 else return 1 + length(head.next).

虽然迭代很常见，但链表本质上是递归数据结构（一个节点加上一个更小的链表）。递归算法可以优雅地遍历、计数或反转链表。例如，一个计算长度的递归函数：如果 head 为空返回 0，否则返回 1 + length(head.next)。

In a recursive reversal, the base case is the empty list or a single node. The recursive call reverses the rest of the list; then the original head’s next node’s next pointer is set to head, and head’s next is set to null. Tracing such recursion without a clear call stack can be tricky, so AQA may test this at a higher level of abstraction.

在递归反转中，基准情况是空链表或仅有一个节点。递归调用反转链表的其余部分；然后将原头节点的下一个节点的“next”指针设置为 head，并将 head 的“next”设置为空。在没有清晰的调用栈情况下追踪这类递归可能很棘手，因此 AQA 可能会在更高层次上考察这种抽象。

---

12. Practical Implementation and Memory Management in AQA Coding | AQA 编码中的实际实现与内存管理

In AQA’s preferred high-level languages (Python, VB.NET, C#), linked lists are often built using a Node class containing data and a reference to the next Node object. In C#, this reference is a managed object reference; in Python, it is simply another instance assigned to self.next.

在 AQA 偏好的高级语言（Python、VB.NET、C#）中，链表通常使用一个包含数据和下一个 Node 对象引用的 Node 类来构建。在 C# 中，这个引用是一个托管对象引用；在 Python 中，它仅仅是分配给 self.next 的另一个实例。

Memory deallocation differs: C# relies on the garbage collector to reclaim unreachable nodes. Python uses reference counting and garbage collection. VB.NET works similarly to C#. This means you do not need explicit free() calls, unlike in lower-level languages, but you should still conceptually understand when a node becomes unreachable.

内存回收方式不同：C# 依赖垃圾回收器来回收不可达的节点。Python 使用引用计数和垃圾回收。VB.NET 与 C# 类似。这意味着你不需要像低级语言那样显式调用 free()，但你仍然应该在概念上理解一个节点何时变得不可达。

Exam pseudocode, however, uses the keywords like ‘newnode’, ‘free’, and explicit pointer assignments. You must be able to translate between this pseudocode and your chosen language’s syntax, always keeping the underlying pointer logic intact.

然而，考试伪代码使用诸如“newnode”、“free”和显式指针赋值之类的关键字。你必须能够在伪代码和你所选语言的语法之间进行翻译，始终保持底层的指针逻辑不变。

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

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