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

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

A linked list is a dynamic data structure used to store an ordered sequence of elements. Unlike arrays, the elements of a linked list 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. For A-Level WJEC Computer Science, it is essential to understand the structure, operations, and relative merits of linked lists compared to arrays.

链表是一种动态数据结构，用于存储有序的元素序列。与数组不同，链表的元素并不存储在连续的内存位置上；相反，每个元素（节点）包含一个数据域和一个指向序列中下一个节点的引用（指针）。对于A-Level WJEC计算机科学，理解链表的结构、操作及其与数组相比的优缺点至关重要。

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

A linked list is a collection of nodes where each node holds one data item and a link (or pointer) to the next node. The list itself is accessed via a reference to the first node, called the head. If the list is empty, the head is a null pointer. The last node in the list typically points to null, indicating the end of the list.

链表是节点的集合，每个节点包含一个数据项和一个指向下一个节点的链接（或指针）。链表本身通过一个指向第一个节点的引用（称为头指针）来访问。如果链表为空，头指针为空指针。链表中的最后一个节点通常指向空，表示链表的结束。

2. Nodes and Pointers | 节点与指针

Each node is an abstract data type with two components: a data field (which stores the element) and a next field (which stores a reference to the next node). In a high-level language, a node can be implemented as a class or record. For example, in pseudocode: TYPE Node = RECORD data : INTEGER; next : ^Node END.

每个节点是一种抽象数据类型，包含两个部分：数据域（存储元素）和指针域（存储下一个节点的引用）。在高级语言中，节点可以实现为类或记录。例如，在伪代码中：TYPE Node = RECORD data : INTEGER; next : ^Node END。

The pointer holds the memory address of another node. The head pointer is not a node itself but simply a reference to the first node. If the head is null, the list contains no nodes.

指针保存的是另一个节点的内存地址。头指针本身不是节点，而仅仅是对第一个节点的引用。如果头指针为空，则链表不包含任何节点。

3. Singly Linked Lists | 单向链表

In a singly linked list, each node has a single pointer to the next node. Traversal is possible in only one direction (forward). The last node points to null. This is the simplest form of linked list and is efficient for forward-only processing.

在单向链表中，每个节点只有一个指向下一个节点的指针。遍历只能沿一个方向（向前）进行。最后一个节点指向空。这是最简单的链表形式，适用于仅需前向处理的情况。

Diagram: Head → [data|next] → [data|next] → null. Operations like insertion and deletion require careful updating of pointers to avoid breaking the chain.

结构示意：头指针 → [数据|指针] → [数据|指针] → 空。插入和删除等操作需要小心更新指针，以避免断开链。

4. Doubly Linked Lists | 双向链表

A doubly linked list extends the node to include a previous pointer as well as a next pointer. This allows traversal in both directions. The head node’s previous pointer is null, and the tail node’s next pointer is null.

双向链表扩展了节点，使其同时包含一个指向前一个节点的指针（prev）和一个指向下一个节点的指针（next）。这样就能在两个方向上遍历。头节点的前驱指针为空，尾节点的后续指针为空。

The extra pointer increases memory overhead but simplifies operations like deletion of a node given a reference to it, because we can access the predecessor directly without traversing from the head.

额外的指针增加了内存开销，但简化了某些操作，例如在已知节点引用的情况下删除该节点，因为可以直接访问前驱节点，无需从头部遍历。

5. Circular Linked Lists | 循环链表

In a circular linked list, the last node’s next pointer points back to the first node instead of to null. A circular singly linked list allows continuous traversal from any node. A circular doubly linked list has the head’s previous pointer pointing to the tail, and the tail’s next pointer pointing to the head.

在循环链表中，最后一个节点的指针指回第一个节点，而不是指向空。循环单向链表可以从任意节点开始连续遍历。循环双向链表中，头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。

This structure is useful for applications that require cycling through data repeatedly, such as round-robin scheduling or a playlist that loops.

这种结构对于需要反复循环处理数据的应用很有用，例如轮转调度或循环播放列表。

6. Traversal of a Linked List | 链表的遍历

Traversal means visiting each node in the list in sequence. In a singly linked list, we start with a current pointer equal to head. While current is not null, we access the data, then move current to current.next. The time complexity of traversal is O(n), where n is the number of nodes.

遍历意味着按顺序访问链表中的每个节点。在单向链表中，我们用一个当前指针等于头指针开始。当当前指针非空时，访问其数据，然后将当前指针移动到 current.next。遍历的时间复杂度为 O(n)，其中 n 是节点数。

Pseudocode example:
current = head WHILE current ≠ NULL OUTPUT current.data current = current.next ENDWHILE
This loops through every node exactly once.

伪代码示例：
current = head WHILE current ≠ NULL OUTPUT current.data current = current.next ENDWHILE
这个循环访问每个节点恰好一次。

7. Insertion into a Linked List | 插入到链表

Insertion can occur at the head, at the tail, or at a specific position in the list. Inserting at the head of a singly linked list is O(1): create a new node, set its next pointer to the current head, and update the head to point to the new node.

插入可以发生在头部、尾部或链表的特定位置。在单向链表的头部插入的时间复杂度为 O(1)：创建一个新节点，将其 next 指针指向当前头节点，然后更新头指针指向新节点。

Inserting at the tail of a singly linked list is O(n) if we only have a head pointer, because we must traverse to the last node. If we maintain a tail pointer, insertion at the tail becomes O(1). Insertion at an arbitrary position requires traversing to the node before the insertion point (predecessor), then updating pointers.

如果只有头指针，在单向链表尾部插入是 O(n) 的，因为必须遍历到最后一个节点。如果维护尾指针，尾部插入可变为 O(1)。在任意位置插入需要遍历到插入点之前的节点（前驱），然后更新指针。

For a doubly linked list, the steps for inserting after a given node X are:
1. Create new node N with data.
2. Set N.prev = X
3. Set N.next = X.next
4. If X.next is not null, set X.next.prev = N
5. Set X.next = N
Care must be taken to update pointers in the correct order.

对于双向链表，在给定节点 X 之后插入的步骤为：
1. 创建包含数据的新节点 N。
2. 设置 N.prev = X
3. 设置 N.next = X.next
4. 如果 X.next 非空，设置 X.next.prev = N
5. 设置 X.next = N
必须注意按正确顺序更新指针。

8. Deletion from a Linked List | 从链表删除

Deletion of a node requires updating the pointers to bypass the node. To delete the head node, simply move the head pointer to head.next (and optionally free the old node memory). This is O(1).

删除节点需要更新指针以绕过该节点。删除头节点时，只需将头指针移动到 head.next（并可释放旧节点内存）。这是 O(1) 操作。

To delete a node given by reference X in a singly linked list, we need the predecessor node. Since we cannot traverse backward, we must either have the predecessor known or traverse from head to find it, making deletion O(n) in general. In a doubly linked list, we can delete X directly in O(1) because we can access its predecessor via X.prev.

在单向链表中删除给定引用 X 所指的节点，需要前驱节点。由于无法反向遍历，我们必须知道前驱节点或从头部遍历找到它，这使得删除操作通常为 O(n)。在双向链表中，可以直接利用 X.prev 访问前驱，从而在 O(1) 时间内删除 X。

The general deletion steps (doubly linked list) for node X:
1. If X.prev ≠ null, set X.prev.next = X.next
2. Else, update head (X is head).
3. If X.next ≠ null, set X.next.prev = X.prev
4. Free X’s memory (or discard reference).

双向链表中删除节点 X 的一般步骤：
1. 如果 X.prev ≠ null，设置 X.prev.next = X.next
2. 否则，更新头指针（X 是头节点）。
3. 如果 X.next ≠ null，设置 X.next.prev = X.prev
4. 释放 X 的内存（或丢弃引用）。

9. Searching in a Linked List | 在链表中查找

Searching for a particular value in a linked list, even if sorted, requires linear traversal from the head, because direct access to an index is not possible. The time complexity is O(n). This is a significant disadvantage compared to binary search on sorted arrays (O(log n)).

在链表中搜索特定值，即使链表已排序，也需要从头部线性遍历，因为无法直接按索引访问。时间复杂度为 O(n)。与已排序数组的二分搜索（O(log n)）相比，这是一个显著劣势。

To search, we maintain a current pointer and iterate, comparing current.data with the target. If found, we can return the node reference or a Boolean true. If the list becomes null, the element is not present.

查找时，我们维护当前指针并迭代，比较 current.data 与目标值。如果找到，可返回节点引用或布尔值 true。如果指针变为空，则元素不存在。

10. Comparison with Arrays | 与数组的对比

Feature / 特性	Array / 数组	Linked List / 链表
Memory allocation / 内存分配	Static, contiguous / 静态，连续	Dynamic, non-contiguous / 动态，非连续
Access time / 访问时间	O(1) direct access / 常数时间直接访问	O(n) sequential access / 线性时间顺序访问
Insertion/Deletion at head / 头部插入/删除	O(n) (requires shifting) / O(n)（需要移动元素）	O(1) / 常数时间
Insertion at tail / 尾部插入	O(1) if space available / 若有空间 O(1)	O(1) with tail pointer / 若有尾指针 O(1)
Memory overhead / 内存开销	Minimal (just data) / 极少（仅数据）	Extra memory for pointers / 指针占用额外内存
Search (sorted) / 搜索（已排序）	O(log n) binary search / 二分搜索 O(log n)	O(n) linear search / 线性搜索 O(n)

Linked lists are preferred when frequent insertion/deletion at the beginning or middle is required and the number of elements is unknown in advance. Arrays are better for random access and cache performance.

当需要频繁在开头或中间插入/删除，且元素数量事先未知时，链表更合适。数组更适合随机访问和缓存性能。

11. Advantages and Disadvantages of Linked Lists | 链表的优缺点

Advantages:

Dynamic size – no need to pre-allocate memory; grows and shrinks at runtime.
Efficient insertion and deletion – O(1) at head, and O(1) in the middle if the node reference is known.
No wasted memory due to unused slots, as nodes are allocated on demand.
Easily implements other data structures like stacks, queues, and graphs.

优点：

动态大小 – 无需预先分配内存；在运行时动态增减。
高效插入和删除 – 头部操作为 O(1)，若已知节点引用，中间操作也为 O(1)。
不会因为未使用的槽位浪费内存，节点按需分配。
易于实现栈、队列和图等其他数据结构。

Disadvantages:

No random access – must traverse sequentially to reach a given index, O(n).
Extra memory per node for pointer storage.
Poor cache locality – nodes are scattered in memory, reducing performance.
More complex to implement, with pointer manipulation prone to errors.

缺点：

无随机访问 – 必须顺序遍历才能到达给定索引，O(n)。
每个节点需要额外内存存储指针。
缓存局部性差 – 节点分散在内存中，降低性能。
实现更复杂，指针操作易出错。

12. Real-World Applications | 实际应用

Linked lists appear in many computing areas: dynamic memory allocation uses free lists; operating systems maintain process queues using linked lists; undo functionality in software often uses a doubly linked list of states; music playlists can be implemented as circular linked lists; and adjacency lists for graph representation often use linked lists. Understanding these applications helps students reason about data structure choices in algorithm design.

链表出现在许多计算领域：动态内存分配使用空闲链表；操作系统用链表维护进程队列；软件的撤销功能常用双向链表存储状态；音乐播放列表可实现为循环链表；图的邻接表表示常使用链表。理解这些应用有助于学生在算法设计中合理选择数据结构。

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

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

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