📚 Linked Lists in A-Level CIE Computer Science | A-Level CIE 计算机：链表 考点精讲
In A-Level CIE Computer Science (9618), a linked list is one of the core dynamic data structures you must master. Unlike static arrays, linked lists allocate memory at runtime and use pointers to connect individual nodes, enabling efficient insertion and deletion. This revision guide covers every essential concept, from node anatomy and list types to traversal algorithms, pointer management, and practical implementations of stacks and queues, all aligned with the Cambridge assessment objectives.
在 A-Level CIE 计算机科学 (9618) 中，链表是你必须掌握的核心动态数据结构之一。与静态数组不同，链表在运行时分配内存，并使用指针连接各个节点，从而实现高效的插入与删除。本考点精讲覆盖所有基本概念——从节点结构、链表类型到遍历算法、指针管理，再到栈和队列的实际实现，完全贴合剑桥考评目标。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of data elements, called nodes, where the order is not given by their physical placement in memory. Each node points to the next node; the list can grow or shrink dynamically without wasting memory.
链表是由数据元素（称为节点）构成的线性集合，其顺序不依赖于内存中的物理位置。每个节点指向下一个节点；链表可以动态扩大或缩小，不会浪费内存。
The start of the list is maintained by a special pointer called the head (or first). If the head is NULL, the list is empty. The last node points to NULL, indicating the end.
链表的起点由一个特殊指针 head（或 first）维护。如果 head 为 NULL，链表为空。最后一个节点指向 NULL，表示链表结束。
2. The Node Structure | 节点结构
A node typically contains two fields: the data (or item) and a pointer (or link) to the next node. In object-oriented programming, this is implemented as a class with attributes for data and a reference to the next node.
节点通常包含两个字段：数据（data）和指向下一个节点的指针（pointer）。在面向对象编程中，这通过一个带有数据属性和 next 引用的类实现。
For a singly linked node in Python-like pseudocode:
对于单向链表节点，类 Python 的伪代码为：
CLASS Node
DECLARE data : INTEGER
DECLARE next : Node
ENDCLASS
In a doubly linked node, an extra prev pointer is added to link to the previous node. In a circular list, the last node's next pointer links back to the head.
在双向节点中，会增加一个 prev 指针指向前一个节点。在循环链表中，最后一个节点的 next 指针会指回头节点。
3. Singly Linked Lists | 单向链表
A singly linked list allows traversal in only one direction – from head to tail. Each node stores a reference to the next node, making operations like insertion and deletion relatively straightforward but requiring careful pointer reassignment.
单向链表只允许从头部到尾部单向遍历。每个节点存储下一个节点的引用，这使得插入和删除等操作较为直接，但需要小心地重新分配指针。
To traverse: start at head, follow node.next until NULL is reached. To insert at front: set the new node's next to the current head, then update head to the new node. Inserting at the end requires iterating to the tail first.
遍历方式：从头节点开始，沿着 node.next 前进，直到遇到 NULL。在头部插入：将新节点的 next 设为当前头节点，再将头节点更新为新节点。在尾部插入则需要先遍历到链表末尾。
4. Doubly Linked Lists | 双向链表
A doubly linked list contains nodes with two pointers: next and prev. This enables backward traversal and simplifies deletion because you can access the predecessor directly without a separate search.
双向链表的节点包含两个指针：next 和 prev。这使得可以反向遍历，并简化了删除操作，因为你可以直接访问前驱节点而无需单独搜索。
Inserting a node in the middle requires updating four pointers: the new node's next and prev, the predecessor's next, and the successor's prev. Memory overhead is higher because each node stores an extra reference, but the added flexibility is beneficial for operations like reversing a list or implementing a deque.
在中间插入一个节点需要更新四个指针：新节点的 next 和 prev，前驱节点的 next，以及后继节点的 prev。内存开销较高，因为每个节点存储了一个额外引用，但增加的灵活性对于反转链表或实现双端队列等操作非常有益。
5. Circular Linked Lists | 循环链表
In a circular linked list, the last node does not point to NULL; instead, its next pointer refers back to the head of the list. A circular list can be singly or doubly linked.
在循环链表中，最后一个节点不指向 NULL，其 next 指针会指回链表头节点。循环链表可以是单向的也可以是双向的。
This structure is useful when applications require continuous cycling through elements, such as in a round-robin scheduler or a music playlist that loops forever. Traversal must avoid infinite loops; a sentinel node or a counter can be used to know when the full circle is complete.
这种结构适用于需要循环遍历元素的应用，例如轮询调度程序或无限循环的音乐播放列表。遍历时必须避免无限循环；可以使用哨兵节点或计数器来判断什么时候完成一整圈。
6. Traversing a Linked List | 遍历链表
Traversal is the process of visiting each node sequentially, starting from the head. The standard algorithm uses a current pointer initialised to head, and a loop that continues while current is not NULL.
遍历是依次访问每个节点的过程，从头节点开始。标准算法使用一个 current 指针初始化为 head，并在 current 不为 NULL 时循环。
current ← head
WHILE current ≠ NULL
OUTPUT current.data
current ← current.next
ENDWHILE
In a doubly linked list, you can traverse backwards by starting at the tail (which might be stored separately) and following prev pointers. Always check for an empty list (head == NULL) before traversing.
在双向链表中，可以从尾部（可能单独存储）开始，沿着 prev 指针向后遍历。遍历前始终要检查链表是否为空 (head == NULL)。
7. Inserting a Node | 插入节点
Insertion can happen at the front, at the end, or at a specific position. The key is to update pointers in the correct order so that no link is broken prematurely.
插入可以发生在头部、尾部或指定位置。关键是要以正确顺序更新指针，避免过早断开链接。
Insert at front (singly): newNode.next ← head; head ← newNode. If the list is empty, head simply becomes newNode.
在头部插入（单向）： newNode.next ← head; head ← newNode。如果链表为空，head 直接设为 newNode。
Insert at end: if empty, head ← newNode; otherwise traverse to the last node (tail) and set tail.next ← newNode. For circular lists, newNode.next ← head and tail.next ← newNode.
在尾部插入：如果链表为空，head ← newNode；否则遍历到最后一个节点（tail），设置 tail.next ← newNode。对于循环链表，newNode.next ← head 且 tail.next ← newNode。
Insert in middle: find predecessor (node at position - 1), then newNode.next ← predecessor.next, predecessor.next ← newNode. If a tail pointer exists and insertion happens at the end, update it accordingly.
在中间插入：找到前驱节点（位置 - 1 处的节点），然后 newNode.next ← predecessor.next，predecessor.next ← newNode。如果存在尾指针且在尾部插入，需要相应更新。
8. Deleting a Node | 删除节点
Deletion requires locating the node to be removed and then rerouting pointers around it. In languages without automatic garbage collection, the removed node's memory must be freed explicitly.
删除需要定位待删除的节点，然后重新路由指针绕过该节点。在没有自动垃圾回收的语言中，必须显式释放被删除节点的内存。
Delete from front: head ← head.next. If the list becomes empty, set tail (if used) to NULL.
从头部删除： head ← head.next。如果链表变空，将尾指针（若有）设置为 NULL。
Delete from end: traverse to the second-last node and set its next to NULL. In a doubly linked list, you can go to tail directly and do tail ← tail.prev; tail.next ← NULL.
从尾部删除：遍历到倒数第二个节点，将其 next 设为 NULL。在双向链表中，可以直接去到尾节点，执行 tail ← tail.prev; tail.next ← NULL。
Delete a specific node: find predecessor; predecessor.next ← nodeToDelete.next. In a doubly list, update the successor's prev as well. Always handle edge cases: deleting the head, deleting a node that does not exist, and deleting from an empty list.
删除指定节点：找到前驱节点；predecessor.next ← nodeToDelete.next。在双向链表中，还要更新后继节点的 prev。始终处理边界情况：删除头节点、删除不存在的节点，以及从空链表中删除。
9. Searching in a Linked List | 搜索链表
Searching for a value in a linked list follows a linear scan from head to tail. In the worst case, the entire list is examined, giving a time complexity of O(n).
在链表中搜索某个值需要从头到尾进行线性扫描。最坏情况下会检查整个链表，时间复杂度为 O(n)。
A typical search algorithm returns the node containing the target, or NULL if not found. Because there is no random access, binary search is not feasible on a singly linked list unless it is converted into an array or indexed structure.
典型的搜索算法返回包含目标值的节点，若未找到则返回 NULL。由于没有随机访问能力，无法对单向链表执行二分查找，除非将其转换为数组或索引结构。
For ordered linked lists, insertion becomes slightly more complex because you must locate the correct logical position, but searching still requires O(n) time.
对于有序链表，插入操作会稍微复杂一些，因为必须找到正确的逻辑位置，但搜索仍然需要 O(n) 时间。
10. Arrays vs. Linked Lists | 数组与链表的比较
Understanding the trade-offs between static arrays and dynamic linked lists is a frequent exam topic. CIE expects you to discuss memory usage, access speed, and insertion/deletion efficiency.
理解静态数组与动态链表之间的权衡是常见的考试主题。CIE 要求你讨论内存使用、访问速度以及插入/删除的效率。
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Static, contiguous block | Dynamic, non-contiguous nodes |
| Access | Random access O(1) | Sequential access O(n) |
| Insertion/Deletion (end) | O(1) if space available | O(n) to find tail, then O(1) |
| Insertion/Deletion (front/middle) | O(n) due to shifting | O(1) if pointer known |
| Memory overhead | None (just data) | Extra pointer(s) per node |
| Overflow | Can occur if fixed size | No overflow (uses heap) |
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 静态，连续内存块 | 动态，非连续节点 |
| 访问 | 随机访问 O(1) | 顺序访问 O(n) |
| 插入/删除（尾部） | 若空间足够 O(1) | 找到尾部 O(n)，然后 O(1) |
| 插入/删除（头部/中间） | 因移动元素 O(n) | 若已知指针 O(1) |
| 内存开销 | 无额外开销（仅数据） | 每个节点有额外指针 |
| 溢出 | 固定大小时可能溢出 | 无溢出（使用堆内存） |
Linked lists are often preferred when the size of the dataset is unknown or changes rapidly, and when frequent insertions/deletions at the beginning are required. Arrays shine when fast indexed access is needed.
当数据集大小未知或变化迅速，并且需要频繁在开头进行插入/删除时，链表往往是首选。数组则在需要快速索引访问时表现出色。
11. Implementing Stacks and Queues | 用链表实现栈和队列
Linked lists provide an ideal foundation for the dynamic implementation of abstract data types (ADTs) like stacks and queues. CIE exams frequently ask for pseudocode or program code to implement these ADTs using linked nodes.
链表为栈和队列等抽象数据类型（ADT）的动态实现提供了理想基础。CIE 考试经常要求用链表节点编写实现这些 ADT 的伪代码或程序代码。
Stack (LIFO): push inserts at the head; pop removes from the head. Both operations are O(1) because no traversal is required. A top-of-stack pointer acts exactly as the head.
栈（后进先出）： push 在头部插入；pop 从头部移除。两个操作都是 O(1)，因为无需遍历。栈顶指针的作用完全相当于 head。
PROCEDURE push(value)
newNode ← new Node(value)
newNode.next ← top
top ← newNode
ENDPROCEDURE
Queue (FIFO): given a queue implemented with head and tail pointers, enqueue adds at the tail, dequeue removes from the head. Both are O(1). Without a tail pointer, enqueue would be O(n).
队列（先进先出）：给定一个用 head 和 tail 指针实现的队列，enqueue 在尾部添加，dequeue 从头部移除。两者都是 O(1)。如果没有尾指针，enqueue 将是 O(n)。
PROCEDURE enqueue(value)
newNode ← new Node(value)
IF head = NULL THEN
head ← newNode
tail ← newNode
ELSE
tail.next ← newNode
tail ← newNode
ENDIF
ENDPROCEDURE
12. Key Algorithms and Pseudocode | 核心算法与伪代码
A solid understanding of pointer manipulation is tested through algorithms. Below is a complete example for inserting a node into a sorted singly linked list, a classic exam question.
考试通过算法来考察对指针操作的掌握程度。下面是一个将节点插入有序单向链表的完整示例，这是经典的考题。
PROCEDURE insertSorted(value)
newNode ← new Node(value)
IF head = NULL OR value <= head.data THEN
newNode.next ← head
head ← newNode
ELSE
current ← head
WHILE current.next != NULL AND current.next.data < value
current ← current.next
ENDWHILE
newNode.next ← current.next
current.next ← newNode
ENDIF
ENDPROCEDURE
The algorithm carefully handles an empty list, insertion before the head, and insertion in the middle or at the tail. Tracing these operations on paper is a must before the exam.
此算法小心地处理了空链表、在 head 前插入以及在中间或尾部插入的情况。考试前务必在纸上追踪这些操作。
Another common task is reversing a singly linked list iteratively:
另一个常见任务是迭代反转单向链表：
PROCEDURE reverse()
prev ← NULL
current ← head
WHILE current != NULL
nextTemp ← current.next
current.next ← prev
prev ← current
current ← nextTemp
ENDWHILE
head ← prev
ENDPROCEDURE
Understanding these building-block algorithms gives you the confidence to tackle any linked-list problem on Paper 2 (algorithms and programming) and Paper 4 (practical implementation).
掌握这些基本算法后，你就能自信地应对 Paper 2（算法与编程）和 Paper 4（实践实现）中的任何链表问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图