Linked Lists for IB CCEA Computer Science | IB CCEA 计算机：链表考点精讲

📚 Linked Lists for IB CCEA Computer Science | IB CCEA 计算机：链表考点精讲

A linked list is one of the fundamental dynamic data structures that every IB Computer Science student must master for the CCEA specification. Unlike arrays, linked lists do not store elements in contiguous memory locations; instead, each element (called a node) contains a reference to the next node in the sequence. This structural difference gives linked lists unique advantages in memory utilisation and flexibility when inserting or deleting elements. In this comprehensive revision guide, we will explore every aspect of linked lists that is likely to appear in your examinations, from basic node anatomy to advanced operations and typical pitfalls.

链表是每位 IB 计算机科学学生必须掌握的 CCEA 考试核心动态数据结构之一。与数组不同，链表并不将元素存储在连续的内存位置中；相反，每个元素（称为节点）都包含一个指向序列中下一个节点的引用。这种结构差异使得链表在内存利用以及插入、删除元素时拥有独特的灵活性和优势。在这份全面的复习指南中，我们将逐一讲解考试中可能出现的链表考点，从基础的节点结构到高级操作以及常见陷阱。

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

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a dynamic data structure, meaning the number of nodes can grow or shrink as the program runs. This is particularly useful when the maximum size of a dataset is unknown in advance. The linked list is built from independent nodes that are connected via pointers, forming a chain. The start of the list is marked by a special reference called the head pointer; if the list is empty, the head pointer holds a null value.

链表是一种数据元素的线性集合，其顺序并非由元素在内存中的物理位置决定，而是每个元素都指向下一个元素。它是一种动态数据结构，这意味着节点数量可以在程序运行时增长或缩小。当数据集的最大大小事先未知时，这一特性尤其有用。链表由独立的节点通过指针连接形成一条链。链表的开头由一个称为头指针的特殊引用标记；如果链表为空，头指针则保存空值。

Because nodes are not stored contiguously, linked lists make no requirement for a single block of free memory. Nodes can be scattered across memory, connected by pointers. This contrasts sharply with arrays, which require a block of contiguous memory. For CCEA exams, you must be able to explain why linked lists are more memory-efficient in certain scenarios and less efficient in others.

由于节点并非连续存储，链表不要求一整块连续的空闲内存。节点可以分散在内存各处，通过指针连接。这与需要一块连续内存的数组形成了鲜明对比。在 CCEA 考试中，你必须能够解释为什么链表在某些场景下内存效率更高，而在其他场景下效率更低。

2. Node Structure and the Head Pointer | 节点结构与头指针

Every node in a linked list contains at least two components: the data field and a pointer field. The data field holds the actual value, which could be an integer, a string, a record, or even another data structure. The pointer field stores a reference (memory address) to the next node in the list. In a singly linked list, the last node has its pointer set to NULL or None, indicating the end of the chain. In CCEA pseudocode, a node is often represented as a record or object with two attributes: ‘data’ and ‘next’.

链表中的每个节点至少包含两个部分：数据域和指针域。数据域存放实际的值，可以是整数、字符串、记录，甚至是另一个数据结构。指针域存储对链表中下一个节点的引用（内存地址）。在单向链表中，最后一个节点的指针被设置为 NULL 或 None，表示链的结束。在 CCEA 伪代码中，节点通常被表示为一个记录或对象，具有两个属性：’data’ 和 ‘next’。

The head pointer is a variable that stores the address of the first node. If the list is empty, the head pointer is set to NULL. Any operation on the list—traversal, insertion, deletion—begins by examining or following the head pointer. Losing the head pointer means losing access to the entire list, which is a common source of memory leaks. Diagrams in exam questions will typically show nodes as boxes divided into two sections labelled ‘data’ and ‘next’, with arrows representing the pointers.

头指针是一个变量，存储第一个节点的地址。如果链表为空，头指针则设为 NULL。任何对链表的操作——遍历、插入、删除——都从检查或跟随头指针开始。丢失头指针意味着失去对整个链表的访问，这是内存泄漏的常见原因。考试题目中的示意图通常会将节点画成被分割为两个部分的方框，分别标注 ‘data’ 和 ‘next’，并用箭头表示指针。

3. Singly, Doubly, and Circular Linked Lists | 单向、双向和循环链表

The CCEA specification recognises three main variants of linked lists. A singly linked list provides navigation in one direction only: each node has a single ‘next’ pointer. This simplicity reduces memory overhead per node but makes operations like deleting the last node or inserting before a node less efficient because you cannot traverse backwards.

CCEA 考试大纲认可三种主要的链表变体。单向链表只允许单向导航：每个节点只有一个 ‘next’ 指针。这种简单性减少了每个节点的内存开销，但会使删除最后一个节点或在某个节点之前插入等操作效率降低，因为你无法向后遍历。

A doubly linked list extends each node with an additional ‘prev’ pointer that references the previous node. This bidirectional traversal enables more efficient insertions and deletions at both ends and in the middle, at the cost of extra memory for the second pointer. The first node’s ‘prev’ and the last node’s ‘next’ are set to NULL.

双向链表为每个节点增加了一个额外的 ‘prev’ 指针，指向其前驱节点。这种双向遍历可以在两端和中间进行更高效的插入和删除操作，代价是需要为第二个指针增加额外内存。第一个节点的 ‘prev’ 和最后一个节点的 ‘next’ 都被设为 NULL。

A circular linked list forms a ring: the last node’s ‘next’ pointer points back to the first node, and in a doubly circular variant, the first node’s ‘prev’ points to the last node. Circular lists are particularly useful in applications that cycle repeatedly through a set of data, such as round‑robin scheduling in operating systems. You may be asked to sketch or trace algorithms for circular lists in your exam.

循环链表形成一个环：最后一个节点的 ‘next’ 指针指回第一个节点，而在双向循环变体中，第一个节点的 ‘prev’ 也指向最后一个节点。循环链表在需要重复遍历一组数据的应用中特别有用，例如操作系统中的轮转调度。考试中可能会要求你画出或跟踪循环链表的算法。

4. Traversing a Linked List | 遍历链表

Traversal is the process of visiting each node in the list sequentially, starting from the head. A typical traversal algorithm uses a temporary pointer (often called ‘current’) that is initialised to the head. While ‘current’ is not NULL, you process the node’s data and then move ‘current’ to ‘current.next’. This loop continues until the end of the list is reached. Traversal is an O(n) operation, where n is the number of nodes.

遍历是按顺序访问链表中每个节点的过程，从头节点开始。典型的遍历算法使用一个临时指针（通常称为 ‘current’），将其初始化为 head。当 ‘current’ 不为 NULL 时，处理节点的数据，然后将 ‘current’ 移动到 ‘current.next’。该循环一直持续到链表末尾。遍历是一种 O(n) 操作，其中 n 是节点数量。

For CCEA exams, you need to be able to write traversal pseudocode and dry‑run it on a given list. Be aware that forgetting to advance the pointer will result in an infinite loop. Traversal is the foundation for many other operations such as searching, counting nodes, and printing the list. When traversing a circular linked list, you must use a different termination condition, such as checking whether ‘current’ has returned to the head after one full pass.

在 CCEA 考试中，你需要能够写出遍历伪代码并在给定链表上进行手工执行跟踪。注意，忘记移动指针将导致无限循环。遍历是许多其他操作的基础，如搜索、计数节点和打印链表。在遍历循环链表时，必须使用不同的终止条件，例如检查 ‘current’ 是否在完整绕回一圈后回到了头节点。

5. Inserting a Node | 插入节点

Insertion is one of the strongest advantages of a linked list, as it does not require shifting elements like an array does. The three fundamental cases are: inserting at the head, inserting at the tail, and inserting at a given position. For insertion at the head, a new node is created, its ‘next’ is set to the current head, and the head pointer is updated to point to the new node. This takes O(1) constant time.

插入是链表的一个最大优势，因为它不像数组那样需要移动元素。三种基本情况是：在头部插入、在尾部插入以及在指定位置插入。在头部插入时，创建一个新节点，将其 ‘next’ 设置为当前 head，然后更新 head 指针指向新节点。这需要 O(1) 的常数时间。

Inserting at the tail requires first traversing the entire list to find the last node. Once the last node is found, its ‘next’ is set to the new node, and the new node’s ‘next’ is set to NULL. This is O(n) for a singly linked list unless a separate tail pointer is maintained. Inserting in the middle involves locating the node that will precede the new node, setting the new node’s ‘next’ to that predecessor’s ‘next’, and then updating the predecessor’s ‘next’ to the new node. The order of pointer assignments is critical; if you update the predecessor’s ‘next’ first, you lose the rest of the list.

在尾部插入需要先遍历整个链表找到最后一个节点。找到后，将其 ‘next’ 设置为新节点，并将新节点的 ‘next’ 设为 NULL。对于单向链表而言，这是 O(n) 的操作，除非维护了一个单独的 tail 指针。在中间插入则涉及定位到将位于新节点之前的那个节点，将新节点的 ‘next’ 设为该前驱节点的 ‘next’，然后更新前驱节点的 ‘next’ 使其指向新节点。指针赋值的顺序至关重要；如果先更新前驱节点的 ‘next’，就会丢失链表的其余部分。

6. Deleting a Node | 删除节点

Deletion also comes in three forms: deleting the head, deleting the tail, and deleting a specific node. To delete the head, you simply move the head pointer to the second node (head = head.next). The original first node becomes unreachable and can be deallocated. This is O(1).

删除同样有三种形式：删除头节点、删除尾节点和删除指定节点。要删除头节点，只需将 head 指针移动到第二个节点（head = head.next）。原来的第一个节点变得不可达，可以解除分配。这是 O(1) 操作。

Deleting the tail is trickier in a singly linked list because you need the penultimate node to set its ‘next’ to NULL. You must traverse the list until you find the node whose ‘next’ points to the tail. This traversal makes the operation O(n). In a doubly linked list, you can reach the tail directly (if a tail pointer exists) and set tail.prev.next to NULL, which is constant time.

在单向链表中删除尾节点较为棘手，因为需要倒数第二个节点来将其 ‘next’ 设为 NULL。你必须遍历链表直到找到某个节点，其 ‘next’ 指向尾节点。这种遍历使该操作成为 O(n)。而在双向链表中，如果存在 tail 指针，你可以直接访问尾部，并设置 tail.prev.next 为 NULL，这是常数时间。

To delete a specific node by value, you first search for it while keeping a pointer to the previous node. Once found, you bypass the node by setting ‘prev.next’ to the node’s ‘next’. The deleted node is then free to be removed from memory. Special care must be taken when the node to delete is the head, as there is no previous node. CCEA exam questions often ask you to write deletion algorithms and handle edge cases such as an empty list or a value not found.

要通过值删除特定节点，首先需要搜索该节点并同时持有指向前一个节点的指针。找到后，将 ‘prev.next’ 设置为该节点的 ‘next’，从而绕过该节点。然后可以将被删除的节点从内存中释放。当要删除的节点是头节点时，需要特别小心，因为没有前驱节点。CCEA 考试题目经常要求你编写删除算法并处理空链表或值未找到等边界情况。

7. Searching and Updating Values | 搜索与更新值

Searching a linked list is a linear operation: start at the head, compare each node’s data with the target, and move to the next. In the worst case, the target is at the tail or not present, giving O(n) time complexity. You cannot use binary search on a standard linked list because there is no random access to the middle element. However, if the list is sorted, you can stop early when you pass the potential position, but the worst‑case remains linear.

在链表中搜索是一种线性操作：从头开始，比较每个节点的数据与目标值，然后移动到下一个节点。最坏情况下，目标值在尾部或不存在，时间复杂度为 O(n)。你不能在标准链表上使用二分搜索，因为无法随机访问中间元素。然而，如果链表是排序的，可以在越过潜在位置时提前停止，但最坏情况依然是线性的。

Updating a value is straightforward once the node is located: simply change its data field. The search step remains O(n). When updating based on an index position, you must count nodes as you traverse, which is inefficient compared to an array’s direct access. Examiners like to ask about the efficiency of these operations in comparison questions, so be prepared to justify your answers.

一旦找到节点，更新值就很简单：只需更改其数据域。搜索步骤依然是 O(n)。当基于索引位置进行更新时，必须在遍历时计数节点，与数组的直接访问相比效率很低。考官喜欢在比较题中询问这些操作的效率，因此请准备好为自己的回答提供理由。

8. Linked Lists vs Arrays | 链表与数组的比较

This is a classic CCEA examination topic. Arrays provide O(1) random access through index calculations but are static in size and require contiguous memory. Inserting or deleting an element in the middle of an array involves shifting elements, which is O(n) on average. Linked lists offer O(1) insertion and deletion at the head (and at the tail if a tail pointer is kept), but searching and accessing an element by index is O(n).

这是经典的 CCEA 考试主题。数组通过索引计算提供 O(1) 的随机访问，但大小是静态的，并且需要连续的内存空间。在数组中间插入或删除元素需要移动其他元素，平均时间复杂度为 O(n)。链表在头部（如果保留尾部指针则在尾部）提供 O(1) 的插入和删除，但搜索和按索引访问元素是 O(n)。

Memory overhead is another key distinction. Each node in a linked list requires extra memory for the pointer(s). An array of integers has no such overhead, but may waste memory if the allocated capacity exceeds the number of elements. Linked lists grow and shrink dynamically, fitting the exact number of elements, which can be more memory-efficient for frequently changing datasets. In your answers, always link the choice of structure to the requirements of the problem, such as frequent insertions/deletions versus heavy random access.

内存开销是另一个关键区别。链表中的每个节点都需要为指针额外占用内存。整数数组没有这种开销，但如果分配的容量超过实际元素数量，可能会浪费内存。链表可以动态增长和收缩，正好适应元素的确切数量，对于频繁变化的数据集可能更为内存高效。在你的回答中，始终要将数据结构的选择与问题需求联系起来，例如频繁的插入/删除与大量的随机访问之间的权衡。

Feature / 特性	Array / 数组	Linked List / 链表
Access / 访问	O(1) direct / 直接	O(n) sequential / 顺序
Insert/Delete at head / 头部插入/删除	O(n) shift needed / 需移动	O(1) / 常数时间
Memory / 内存	Fixed size, contiguous / 固定大小，连续	Dynamic, extra pointer overhead / 动态，额外指针开销

9. Real‑World Applications of Linked Lists | 链表的实际应用

Understanding practical uses helps you answer application‑based questions. Operating systems use circular linked lists for process scheduling, where the CPU cycles through processes in a round‑robin fashion. Doubly linked lists are often used to implement undo/redo functionality in text editors or image editing software, as they allow both forward and backward navigation through states.

理解实际用途有助于你回答应用题。操作系统使用循环链表进行进程调度，CPU 以轮转方式循环执行进程。双向链表常用于实现文本编辑器或图像编辑软件中的撤销/重做功能，因为它们允许通过状态进行向前和向后的导航。

Music players employ linked lists to manage playlists, where songs can be easily added, removed, and reordered without moving large blocks of data. In memory management, free lists of available memory blocks are maintained as linked lists. Hash table collision resolution is sometimes implemented using linked lists in separate chaining. CCEA may ask you to identify or justify which linked list variant suits a given scenario.

音乐播放器使用链表来管理播放列表，可以轻松地添加、移除和重新排序歌曲，而无需移动大量数据块。在内存管理中，可用内存块的空闲列表以链表的形式维护。哈希表的冲突解决有时使用分离链接法中的链表实现。CCEA 考试可能会要求你识别或证明哪种链表变体适合给定的场景。

10. Implementing Linked Lists in Pseudocode | 使用伪代码实现链表

CCEA exam papers frequently include questions that require you to write pseudocode for linked list operations. A typical node class in pseudocode might be defined as:

CCEA 考试卷子经常包含要求你编写链表操作伪代码的题目。典型的节点类在伪代码中可能被定义为：

TYPE Node
DECLARE data : INTEGER
DECLARE next : POINTER TO Node
END TYPE

To create a new node, you allocate memory dynamically and assign values. The head pointer is declared globally or passed to procedures. It is essential to handle the case when the list is empty. When writing insertion procedures, always consider the empty list case separately if the head pointer needs updating. Common procedures include insertAtFront(head, data), insertAtEnd(head, data), deleteNode(head, target), and printList(head).

要创建新节点，你需要动态分配内存并赋值。头指针被声明为全局变量或传递给过程。必须处理链表为空的情况。在编写插入过程时，如果头指针需要更新，始终单独考虑空链表的情况。常见的过程包括 insertAtFront(head, data)、insertAtEnd(head, data)、deleteNode(head, target) 和 printList(head)。

For a doubly linked list node, you would add a ‘prev’ pointer. When inserting into a doubly linked list, you must update both the ‘next’ and ‘prev’ pointers of surrounding nodes. Examiners often test your ability to correctly order these pointer assignments to avoid breaking the list. Practise dry‑running your pseudocode on simple diagrams to catch logic errors before the exam.

对于双向链表节点，你需要增加一个 ‘prev’ 指针。在双向链表中插入时，必须同时更新相邻节点的 ‘next’ 和 ‘prev’ 指针。考官经常测试你正确排列这些指针赋值顺序的能力，以避免破坏链表。在考前，通过简单的示意图对手工执行伪代码进行练习，以发现逻辑错误。

11. Common Mistakes and How to Avoid Them | 常见错误及其避免方法

One of the most frequent errors is dereferencing a NULL pointer, which occurs when you try to follow ‘next’ on an empty list or after reaching the end without checking. Always include a check for NULL before accessing a node’s fields. Another pitfall is losing the rest of the list by overwriting the head pointer before linking the new node correctly. In pseudocode, drawing a box‑and‑arrow diagram can help visualise the correct sequence.

最常见的错误之一是解引用 NULL 指针，当你试图在空链表上或在未检查的情况下到达末尾后使用 ‘next’ 时，就会发生这种情况。在访问节点的域之前，始终包含对 NULL 的检查。另一个陷阱是在正确链接新节点之前覆盖了头指针，从而丢失了链表的其余部分。在伪代码中，绘制方块和箭头示意图有助于可视化正确的顺序。

Memory leaks are common when you delete a node but forget to free the allocated memory. In language‑independent contexts, simply state that the node is ‘returned to free storage’. Also watch for off‑by‑one errors when inserting at a specific index; you must stop at the node just before the insertion point. In doubly linked lists, forgetting to update the ‘prev’ pointer of the node that follows the inserted or deleted node can corrupt the structure.

当删除节点却忘记释放已分配的内存时，常常会发生内存泄漏。在语言无关的上下文中，只需说明该节点被 ‘返回给可用存储空间’。还要留意在特定索引处插入时的差一错误；必须停在插入点之前的那个节点。在双向链表中，忘记更新被插入或被删除节点的后续节点的 ‘prev’ 指针，会破坏链表结构。

12. Exam Tips and Summary | 考试技巧与总结

CCEA questions on linked lists often mix theoretical understanding with practical algorithm writing. You may be presented with a diagram and asked to show the state after a series of operations, or to write pseudocode and identify its time complexity. Master the core operations—traversal, insertion, deletion—and their edge cases. For comparison questions, use the table of array vs linked list characteristics to structure your answer logically.

CCEA 有关链表的考题经常将理论理解与实际算法编写结合在一起。你可能会看到一幅示意图，并被要求展示一系列操作之后的状态，或者编写伪代码并指出其时间复杂度。掌握核心操作——遍历、插入、删除——及其边界情况。对于比较题，利用数组与链表特性对照表，有逻辑地组织你的答案。

Always read the question carefully to determine whether a singly, doubly, or circular implementation is required. Pay attention to whether a tail pointer is mentioned, as this often simplifies tail insertion. If asked to comment on efficiency, relate your answer to the number of nodes and the operations involved. Finally, remember that linked lists are a fundamental building block for more complex data structures such as stacks, queues, and graphs, so a deep understanding will benefit many other areas of the syllabus.

始终仔细阅读题目，确定需要单向、双向还是循环链表的实现。注意是否提到了 tail 指针，因为这通常会简化尾部插入。如果被要求评论效率，请将答案与节点数量及所涉及的操作相关联。最后，请记住，链表是更复杂数据结构（如栈、队列和图）的基本构建块，因此深入理解将对考纲中许多其他领域有所帮助。

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

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

Linked Lists for IB CCEA Computer Science | IB CCEA 计算机：链表 考点精讲