📚 Linked Lists: Key Exam Points for IB & CIE Computer Science | 链表：IB与CIE计算机考点精讲
Linked lists are a staple in IB and CIE Computer Science exams, testing your understanding of dynamic data structures, pointer manipulation, and algorithmic thinking. Mastering their operations and trade-offs is crucial for both paper-based pseudocode questions and practical programming tasks.
链表是 IB 和 CIE 计算机科学考试中的常客，考查你对动态数据结构、指针操作和算法思维的理解。掌握链表的操作及其权衡，对于笔试伪代码题和实际编程任务都至关重要。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of nodes, where each node contains a data field and a reference (or pointer) to the next node in the sequence. The list is accessed via a head pointer that references the first node; the last node's pointer is set to a null value to mark the end.
链表是一种线性的节点集合，每个节点包含一个数据域和一个指向序列中下一个节点的引用（即指针）。通过指向第一个节点的头指针来访问链表；最后一个节点的指针设为 null 值以标记结尾。
Unlike arrays, linked list nodes are not stored contiguously in memory. This dynamic allocation allows the structure to grow or shrink at runtime without the need for pre-allocation or costly resizing.
与数组不同，链表节点在内存中并非连续存储。这种动态分配允许结构在运行时增长或收缩，无需预先分配或进行代价高昂的扩容操作。
2. Types of Linked Lists | 链表的类型
A singly linked list is the simplest form: each node holds a single pointer to the next node, enabling traversal in one direction only. It is memory-efficient but cannot be navigated backwards.
单向链表是最简单的形式：每个节点持有一个指向下一个节点的指针，只能单向遍历。它节省内存，但无法向后导航。
A doubly linked list includes an additional previous pointer in each node, allowing bidirectional traversal. This makes reverse operations easier but consumes more memory per node.
双向链表在每个节点中包含一个额外的指向前一个节点的指针，允许双向遍历。这使反向操作更容易，但每个节点消耗更多内存。
A circular linked list connects the last node's next pointer back to the head (or the first node), forming a loop. Circular lists can be singly or doubly linked and are useful for applications that cycle through data repeatedly.
循环链表将最后一个节点的 next 指针指回头节点（或第一个节点），形成一个环。循环链表可以是单向或双向的，适用于需要反复循环数据的应用。
3. Node Structure and Pointers | 节点结构与指针
In pseudocode, a node is commonly defined as a record with at least a data field and a pointer field. For a singly linked list: TYPE node = RECORD data : INTEGER; next : ^node END. The caret symbol (^) indicates a pointer type in many IB/CIE pseudocode styles.
在伪代码中，节点通常被定义为一个记录，至少包含一个数据域和一个指针域。对于单向链表：TYPE node = RECORD data : INTEGER; next : ^node END。在许多 IB/CIE 伪代码风格中，脱字符号 (^) 表示指针类型。
In a doubly linked list, the node record includes an extra prev : ^node field. Pointer variables like head, temp, and newNode are declared with the same pointer notation.
在双向链表中，节点记录包含一个额外的 prev : ^node 域。像 head、temp、newNode 这样的指针变量使用相同的指针符号声明。
Understanding pointer dereferencing is vital: node^.data accesses the data, while node^.next gives the pointer to the next node.
理解指针的解引用至关重要：node^.data 访问数据，而 node^.next 给出指向下一个节点的指针。
4. Traversal and Access | 遍历与访问
Traversal always begins at the head pointer. A variable (often called current) is set to head, and a loop follows current^.next until current becomes null. This is a sequential process; there is no random access.
遍历始终从头指针开始。将一个变量（通常称为 current）设置为 head，然后通过循环跟随 current^.next，直到 current 变为 null。这是一个顺序过程，没有随机访问。
Because of this, accessing the k-th element requires O(k) time, i.e. O(n) in the worst case. To check for an empty list, simply test head = null.
因此，访问第 k 个元素需要 O(k) 时间，即最坏情况为 O(n)。要检查空链表，只需测试 head = null。
5. Insertion Operations | 插入操作
Inserting at the head is straightforward: create a new node, set its next pointer to the current head, and update head to point to the new node. This operation runs in O(1) time.
在头部插入很简单：创建一个新节点，将其 next 指针指向当前头节点，然后更新 head 使其指向新节点。该操作的时间复杂度为 O(1)。
ext points to the new node, then tail is updated. Without a tail pointer, you must traverse to the end, leading to O(n) time.
在尾部插入（如果维护了尾指针）也是 O(1)：tail^.next 指向新节点，然后更新 tail。如果没有尾指针，你必须遍历到末尾，导致 O(n) 时间。
Inserting in the middle requires finding the predecessor node. After locating it, set the new node's next to the predecessor's next, then update the predecessor's next to the new node. Always perform pointer assignments in the correct order to avoid breaking the chain.
在中间插入需要找到前驱节点。定位后，将新节点的 next 设为前驱节点的 next，然后更新前驱节点的 next 使其指向新节点。务必按正确顺序执行指针赋值，以免断链。
6. Deletion Operations | 删除操作
To delete a node, you must modify the previous node's next pointer to bypass the targeted node. In a singly linked list, you need a reference to the predecessor. Once bypassed, the node can be disposed of (e.g., using FREE or dispose in pseudocode).
要删除一个节点，必须修改前一个节点的 next 指针以绕过目标节点。在单向链表中，你需要一个指向前驱的引用。一旦绕过，该节点便可被释放（例如在伪代码中使用 FREE 或 dispose）。
t and then free the old head. When deleting the only node, ensure head becomes null afterwards. Forgetting to handle an empty list or a single-element list is a common error.
删除头节点是一个特殊情况：只需将 head 前进到 head^.next，然后释放旧的头节点。如果删除的是唯一节点，确保 head 随后变为 null。忘记处理空链表或只有一个元素的链表是常见错误。
In a doubly linked list, deletion requires updating the predecessor's next and successor's prev pointers, making the operation slightly more involved but avoiding the need to maintain a trailing pointer during traversal.
在双向链表中，删除需要更新前驱的 next 和后继的 prev 指针，操作稍显复杂，但避免了遍历时需要维护追踪指针的问题。
7. Linked Lists vs Arrays | 链表与数组的比较
The following table summarises key differences between arrays and linked lists, which are frequently examined in IB and CIE papers.
下表总结了数组和链表之间的主要区别，这些是 IB 和 CIE 试卷中常考的内容。
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Static or dynamic contiguous block | Dynamic, non-contiguous nodes |
| Access time | O(1) random access | O(n) sequential access |
| Insertion/Deletion (at ends) | O(1) if space available, or O(n) for shifting | O(1) with tail/head pointer, O(n) for middle |
| Memory overhead | None (just data) | Extra pointer(s) per node |
| Size flexibility | Fixed or needs resizing | Grows and shrinks effortlessly |
Arrays offer speed in indexed access, whereas linked lists shine in scenarios with frequent insertions and deletions where shifting elements would be expensive. IB/CIE questions often ask you to justify the choice of data structure based on these trade-offs.
数组在索引访问方面速度更快，而链表在需要频繁插入和删除且移位代价高昂的场景中表现出色。IB/CIE 试题常要求你基于这些权衡来论证数据结构的选择。
8. Time Complexities | 时间复杂度
Understanding the Big O for common operations is essential for both analysis questions and algorithm design. For a singly linked list without a tail pointer: insertion at head is O(1); insertion at tail is O(n); insertion in the middle (after search) is O(1) for the link change, but the search itself is O(n). Deletion from head is O(1), while deleting any other known node requires finding the predecessor, thus O(n).
理解常见操作的大 O 符号对于分析题和算法设计都至关重要。对于没有尾指针的单向链表：头部插入 O(1)；尾部插入 O(n)；中间插入（搜索后）更改链接为 O(1)，但搜索本身是 O(n)。从头部删除是 O(1)，而删除任何其他已知节点需要找到前驱，因此为 O(n)。
If a tail pointer is maintained, appending becomes O(1). Doubly linked lists allow O(1) deletion of a node given a pointer to it, because the predecessor can be reached via the prev link.
如果维护了尾指针，追加操作变为 O(1)。双向链表在给定节点指针时允许 O(1) 删除，因为可以通过 prev 链接访问前驱。
9. Memory Management and Leaks | 内存管理与泄漏
In languages without automatic garbage collection (such as the pseudocode environments often assumed in IB/CIE), dynamically allocated nodes must be explicitly freed after they are removed. Failing to do so creates memory leaks.
在没有自动垃圾回收的语言中（如 IB/CIE 常用的伪代码环境），动态分配的节点在移除后必须显式释放。否则将造成内存泄漏。
When deleting a node, first store a temporary pointer to it, adjust the predecessor’s next, and then call dispose(temp) or equivalent. Never free a node before you have safely copied or rerouted the necessary links.
删除节点时，首先用一个临时指针保存它，调整前驱的 next，然后调用 dispose(temp) 或等效操作。在安全地复制或重定向必要的链接之前，切勿释放节点。
10. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧
One classic mistake is losing the head pointer when performing operations. Always ensure a reference to the list’s start is preserved. Another is performing pointer assignments in the wrong order, which can orphan part of the list.
一个经典错误是在执行操作时丢失头指针。务必确保保留对列表开头的引用。另一个错误是以错误的顺序执行指针赋值，这可能导致部分链表成为孤立节点。
Forgetting to handle edge cases—empty lists, single-node lists, inserting before the head, and deleting the last node—is a common cause of lost marks. Draw diagrams to trace pointer changes before writing code.
忘记处理边界情况——空链表、单节点链表、在头部前插入以及删除最后一个节点——是丢分的常见原因。在编写代码之前，画图来跟踪指针变化。
When asked to compare with arrays, do not just list properties—explain the practical implications. For instance, a linked list is preferable for a waiting queue with unpredictable size, while an array is better for a fixed-size lookup table.
当被要求与数组进行比较时，不要只罗列属性——要解释实际影响。例如，链表适用于大小不可预测的等待队列，而数组更适合固定大小的查找表。
11. Pseudocode/Code Examples | 伪代码/代码示例（IB 风格）
A typical IB/CIE question might ask you to write a procedure that inserts a node at the beginning of a linked list. The solution must show pointer manipulation clearly.
一个典型的 IB/CIE 问题可能要求你编写一个在链表开头插入节点的过程。解答必须清晰地展示指针操作。
PROCEDURE insertAtHead(BYREF head : ^node, data : INTEGER)
newNode ← NEW(node)
newNode^.data ← data
newNode^.next ← head
head ← newNode
ENDPROCEDURE
The NEW keyword allocates memory for a node; BYREF allows the procedure to modify the original head pointer. The order of the last two assignments ensures the chain is never broken.
关键字 NEW 为节点分配内存；BYREF 允许过程修改原始头指针。最后两条赋值语句的顺序确保了链表不会断开。
For deletion of a node after a given node (assuming it exists):
删除在给定节点之后的节点（假定其存在）：
PROCEDURE deleteAfter(nodePtr : ^node)
temp ← nodePtr^.next
IF temp ≠ null THEN
nodePtr^.next ← temp^.next
DISPOSE(temp)
ENDIF
ENDPROCEDURE
The procedure safely handles the case where nodePtr is the last node (temp is null), preventing a runtime error. Always include such guards in exam answers.
该过程安全地处理了 nodePtr 为最后一个节点（temp 为 null）的情况，避免了运行时错误。在考试答案中务必包含此类保护。
12. Application Scenarios | 应用场景
Linked lists serve as the underlying structure for stacks and queues; dynamic stacks can be implemented by pushing and popping at the head. Queues benefit from a singly linked list with both head and tail pointers to achieve O(1) enqueue and dequeue.
链表可用作栈和队列的底层结构；动态栈可以通过在头部压入和弹出实现。队列受益于同时带有头指针和尾指针的单向链表，以实现 O(1) 的入队和出队操作。
In graph representations, adjacency lists rely on an array of linked lists to store neighbours, which is memory-efficient for sparse graphs. Polynomial arithmetic and large integer manipulation also often use linked lists to hold coefficients and terms.
在图表示中，邻接表依赖于链表数组来存储邻居，对于稀疏图而言节省内存。多项式运算和大整数处理也常使用链表来存储系数和项。
Operating systems use linked lists for managing process queues, free memory blocks, and directory structures, making the topic both academically relevant and practically significant.
操作系统使用链表管理进程队列、空闲内存块和目录结构，使得该主题兼具学术价值与实践意义。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图