📚 Linked List in A-Level Computer Science: Key Points | A-Level 计算机：链表 考点精讲
A linked list is a dynamic data structure used to store a sequence of elements. Unlike arrays, its elements are not stored contiguously in memory; each item (node) contains data and a pointer to the next node. Understanding linked lists is fundamental for grasping memory management, algorithmic efficiency, and abstract data types at A-Level.
链表是一种动态数据结构，用于存储一系列元素。与数组不同，它的元素在内存中并非连续存储；每个元素（节点）包含数据和一个指向下一个节点的指针。理解链表对于在 A-Level 阶段掌握内存管理、算法效率和抽象数据类型至关重要。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of nodes, where each node holds a value and a reference (or pointer) to the next node in the sequence. The first node is called the head, and the last node points to null (or a sentinel node in some implementations). Linked lists allow efficient insertion and deletion at any position because no shifting of elements is required.
链表是节点的线性集合，每个节点包含一个值和一个指向序列中下一个节点的引用（或指针）。第一个节点称为头节点，最后一个节点指向空（或在某些实现中指向一个哨兵节点）。链表允许在任何位置高效地插入和删除，因为不需要移动元素。
2. Types of Linked Lists | 链表的类型
There are three core types tested at A-Level: singly linked lists, doubly linked lists, and circular linked lists. A singly linked list has nodes with a single pointer to the next node. A doubly linked list has pointers to both the next and previous nodes, enabling traversal in both directions. A circular linked list has the last node pointing back to the head, forming a loop.
A-Level 中考查三种核心类型：单向链表、双向链表和循环链表。单向链表的节点只有一个指向下一个节点的指针。双向链表既有指向下一个节点的指针，也有指向前一个节点的指针，支持双向遍历。循环链表的最后一个节点指向头节点，形成一个环。
| Type 类型 | Pointers per node 每节点指针 | Traversal 遍历 |
|---|---|---|
| Singly 单向 | 1 (next) | Forward only 仅向前 |
| Doubly 双向 | 2 (prev, next) | Forward & backward 向前和向后 |
| Circular 循环 | 1 or 2 (tail points to head) | Looped 循环 |
3. Node Structure and Implementation | 节点结构与实现
A node is typically defined using a class or a record with two fields: data and a pointer (or reference). In pseudocode or programming tasks, you must be comfortable declaring and manipulating nodes. For example, in Python-like pseudocode:
节点通常使用具有两个字段的类或记录来定义：数据和一个指针（或引用）。在伪代码或编程任务中，你必须熟练掌握节点的声明和操作。例如，在类 Python 伪代码中：
class Node: data : ItemType; next : Node
For doubly linked lists, an extra field prev is added.
对于双向链表，需添加额外的 prev 字段。
4. Traversing a Linked List | 遍历链表
To visit every element, start from the head and follow the next pointers until reaching null. In a traversal algorithm, a current pointer moves through the list. This is an O(n) operation. A typical loop condition is while current != null.
要访问每个元素，从头节点开始，沿着 next 指针移动直到到达 null。在遍历算法中，一个 current 指针在列表中移动。这是一个 O(n) 操作。典型的循环条件是 while current != null。
Recursion is sometimes used for backward traversal in singly linked lists, but A-Level exams may ask you to trace or write iterative loops.
有时用递归对单向链表进行逆向遍历，但 A-Level 考试可能要求你跟踪或编写迭代循环。
5. Insertion at Different Positions | 在不同位置插入
Inserting a node requires updating the surrounding pointers. For insertion at the head, set the new node’s next to the current head, then update head to the new node. This takes O(1) time. Insertion at the tail or a given position requires traversing to find the predecessor, making it O(n) in a singly linked list unless a tail pointer is maintained.
插入节点需要更新周围的指针。在头节点前插入时，将新节点的 next 设置为当前头节点，然后将 head 更新为新节点。这需要 O(1) 时间。在尾部或指定位置插入需要遍历以找到前驱节点，因此对于单向链表是 O(n)，除非维护了尾指针。
Always manage the pointer updates in the correct order to avoid breaking the chain. A common exam question asks for the sequence of statements.
务必以正确顺序管理指针更新，以避免断开链表。常见的考试题目会要求写出语句的顺序。
6. Deletion of a Node | 删除节点
Deleting a node involves re-routing the predecessor’s next pointer to bypass the node to be deleted. In languages without garbage collection (like C++), you must explicitly free the memory. In Python/Java, unreferenced nodes are automatically garbage collected. Deletion at the head is O(1); elsewhere, O(n) due to traversal. Always handle special cases such as deleting the only node or the last node.
删除节点需要重新路由前驱节点的 next 指针，以绕过要删除的节点。在没有垃圾回收的语言（如 C++）中，必须显式释放内存。在 Python/Java 中，无引用的节点会被自动垃圾回收。在头部删除是 O(1)；在其他位置由于需要遍历，是 O(n)。始终处理特殊情况，例如删除唯一的节点或最后一个节点。
7. Linked Lists vs. Arrays | 链表与数组的比较
This is a classic A-Level comparison question. Linked lists are dynamic, so size need not be predetermined; memory is allocated as needed. Insertions and deletions in a linked list do not require shifting elements, whereas arrays have O(n) shifting cost. However, arrays provide O(1) random access by index, while linked lists require O(n) traversal to reach a specific position. Arrays can be more cache-friendly due to contiguous storage.
这是典型的 A-Level 比较题。链表是动态的，因此大小不需要预先确定；内存按需分配。在链表中插入和删除不需要移动元素，而数组的移动开销为 O(n)。但是，数组通过索引提供 O(1) 的随机访问，而链表需要 O(n) 遍历才能到达特定位置。由于连续存储，数组对缓存更友好。
| Aspect 方面 | Linked List 链表 | Array 数组 |
|---|---|---|
| Memory 内存 | Dynamic, extra pointer overhead | Fixed/contiguous, may waste space |
| Random access 随机访问 | O(n) | O(1) |
| Insert/delete at head 头插/删 | O(1) | O(n) |
8. Memory Allocation and Heap Usage | 内存分配与堆的使用
Nodes are dynamically allocated on the heap (free store). This is crucial knowledge for A-Level, linking linked lists to the concept of dynamic memory and pointer manipulation. Diagrams often show memory boxes with addresses. You should be able to explain why a linked list can grow arbitrarily (as long as heap memory is available) and the overhead of storing pointers alongside the data.
节点在堆（自由存储区）上动态分配。这是 A-Level 的重要知识，将链表与动态内存和指针操作的概念联系起来。图示通常显示带有地址的内存盒子。你应该能够解释为什么链表可以任意增长（只要堆内存可用），以及存储指针与数据的开销。
9. Common Algorithms and Tracing | 常见算法与跟踪
Examiners often ask you to trace algorithms for counting nodes, finding the middle element (fast/slow pointer technique), reversing a list iteratively, or detecting cycles in a circular list (Floyd’s cycle-finding algorithm). Tracing involves drawing pointer states step by step. Reversing a singly linked list requires three pointers: prev, current, and next.
考官经常要求你跟踪计算节点数、查找中间元素（快慢指针技术）、迭代反转链表，或检测循环链表中的环（弗洛伊德判圈算法）等算法。跟踪需要逐步画出指针状态。反转单向链表需要三个指针：prev、current 和 next。
Example reversal pseudocode: prev = null; current = head; while current != null: next = current.next; current.next = prev; prev = current; current = next; head = prev;
反转伪代码示例：prev = null; current = head; while current != null: next = current.next; current.next = prev; prev = current; current = next; head = prev;
10. Doubly Linked List Operations | 双向链表操作
In a doubly linked list, insertions and deletions require updating both next and prev pointers of affected nodes. This allows easier backward traversal and deletion of a node given only a pointer to it (because you can access the predecessor via prev). However, the extra pointer increases memory overhead and the complexity of pointer updates.
在双向链表中，插入和删除需要更新受影响节点的 next 和 prev 指针。这使得向后遍历更容易，并且给定一个指向某节点的指针即可删除该节点（因为可以通过 prev 访问前驱）。但是，额外的指针增加了内存开销和指针更新的复杂度。
11. Circular Linked List Applications | 循环链表的应用
Circular linked lists are useful in applications that require continuous cycling through elements, such as round-robin scheduling in operating systems, multiplayer game turn management, or implementing a music playlist that loops. In a circular singly linked list, the tail’s next points to the head, so there is no null. Traversal must be controlled to avoid infinite loops.
循环链表在需要连续循环遍历元素的应用中很有用，例如操作系统中的轮转调度、多人游戏回合管理或实现循环播放的音乐列表。在单向循环链表中，尾节点的 next 指向头节点，因此没有 null。遍历时必须进行控制以避免无限循环。
12. Key Pitfalls and Exam Tips | 关键陷阱与应试技巧
Always check for empty lists before deletion. Be careful with the order of pointer reassignments—you can lose the rest of the list if you change a pointer too early. When inserting between two nodes, always connect the new node first to the next node before breaking the existing link. Use diagrams liberally in your answers. Understand that a linked list is an implementation of the list ADT; questions may ask you to compare array-based and linked-list-based implementations of stacks and queues.
删除前务必检查空链表。注意指针重新赋值的顺序——如果过早改变指针，可能会丢失链表的其余部分。在两个节点之间插入时，始终先将新节点连接到下一个节点，然后再断开现有链接。在答案中充分使用图示。要理解链表是列表 ADT 的一种实现；题目可能要求你比较基于数组和基于链表的栈和队列实现。
Time complexity is a key marking point: insertion/deletion at head O(1), search O(n), access by index O(n). For doubly linked lists, deletion given a node reference can be O(1). Remembering these differences is critical.
时间复杂度是关键得分点：头部插入/删除 O(1)，搜索 O(n)，按索引访问 O(n)。对于双向链表，给定节点引用的删除可以是 O(1)。记住这些差异至关重要。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导