IB Computer Science: Linked Lists - Key Concepts | IB 计算机：链表考点精讲

📚 IB Computer Science: Linked Lists – Key Concepts | IB 计算机：链表考点精讲

A linked list is a fundamental dynamic data structure that frequently appears in IB Computer Science exams. Understanding how nodes are connected via references (or pointers), how insertion and deletion work, and how linked lists compare to arrays is crucial for both Paper 1 and Paper 2 questions. This article covers all essential concepts, operations, time complexity, and common exam pitfalls.

链表是一种基础的动态数据结构，在 IB 计算机科学考试中频繁出现。理解节点如何通过引用（或指针）相连、插入和删除操作的原理，以及链表与数组的比较，对 Paper 1 和 Paper 2 的答题至关重要。本文涵盖所有核心概念、基本操作、时间复杂度分析及常见考试陷阱。

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. Instead, each node contains a data field and a reference (or pointer) to the next node in the sequence. This allows the list to grow or shrink dynamically during program execution.

链表是数据元素（称为节点）的线性集合，其顺序并非由它们在内存中的物理位置决定。每个节点包含一个数据域和一个指向序列中下一个节点的引用（或指针）。这使得链表能够在程序执行期间动态地增长或收缩。

The first node is called the head. If the list is empty, the head is typically set to null or a special sentinel value. The last node points to null, indicating the end of the list. In IB pseudocode, linked lists are often represented using objects with data and next attributes.

第一个节点称为头节点。如果链表为空，头节点通常设为 null 或某个特殊的哨兵值。最后一个节点指向 null，表示链表的末尾。在 IB 伪代码中，链表常以拥有 data 和 next 属性的对象来表示。

2. Node Structure | 节点结构

A typical node in a singly linked list contains two components: the data item and a link (reference) to the next node. In object-oriented programming, a class is defined with fields such as data and next. For a doubly linked list, an additional prev field points to the previous node.

单链表中典型的节点包含两个部分：数据项和指向下一个节点的链接（引用）。在面向对象编程中，会定义一个包含 data 和 next 字段的类。对于双向链表，会额外的 prev 字段指向前一个节点。

For example, a node class in IB notation might look like:

例如，IB 表示法中的节点类可能如下所示：

NODE.data – stores the value
NODE.next – references the next node (or null)

NODE.data – 存储值
NODE.next – 引用下一个节点（或 null）

Understanding this structure is fundamental because all operations rely on manipulating these references correctly to maintain the integrity of the list.

理解这一结构是基础，因为所有操作都依赖于正确操纵这些引用来保持链表的完整性。

3. Types of Linked Lists | 链表的类型

There are three primary types of linked lists relevant to the IB syllabus:

IB 大纲中相关的链表主要有三种：

Singly Linked List – Each node has a single pointer to the next node. Traversal is possible in only one direction (forward).

单链表 – 每个节点只有一个指向下一个节点的指针。只能沿一个方向（前进）遍历。

Doubly Linked List – Each node has two pointers: next and prev. This allows traversal in both directions, making insertions and deletions more flexible but requiring more memory and careful pointer updates.

双向链表 – 每个节点有两个指针：next 和 prev。这允许双向遍历，使得插入和删除更灵活，但需要更多内存以及更谨慎的指针更新。

Circular Linked List – The last node points back to the head instead of null. This can be singly or doubly linked. It is useful for applications that cycle continuously, such as a round-robin scheduler.

循环链表 – 最后一个节点指向头节点而不是 null。它可以是单向或双向循环。对于需要连续循环的应用（如轮询调度器）很有用。

4. Traversing a Linked List | 遍历链表

Traversal is the process of visiting each node in the list, usually starting from the head. A temporary pointer (often called current) is set to the head, and a loop advances current = current.next until current becomes null.

遍历是访问链表中每个节点的过程，通常从头节点开始。一个临时指针（常命名为 current）指向头节点，然后循环执行 current = current.next 直到 current 变为 null。

When counting elements or printing values, traversal is essential. In IB exams, you might be asked to write an algorithm that traverses a linked list to compute the sum of all data fields or to locate a specific item.

在统计元素个数或输出值时，遍历是必不可少的。IB 考试中可能要求你编写遍历链表的算法，用以计算所有数据域的总和或定位特定元素。

Pseudocode pattern:

伪代码模式：

current = head
while current ≠ null
output current.data
current = current.next
end while

5. Inserting a Node | 插入节点

Insertion can occur at the beginning, in the middle, or at the end of the list. The key steps involve creating a new node and adjusting the next references so the list remains connected.

插入可以在链表的头部、中间或尾部进行。关键步骤包括创建新节点并调整 next 引用以保持链表的连接性。

Insert at head: Set the new node’s next to the current head, then update the head to point to the new node.

在头部插入：将新节点的 next 设为当前头节点，然后更新头指针指向新节点。

Insert after a given node (middle or end): Set the new node’s next to the given node’s next, then set the given node’s next to the new node. The order of pointer assignment is critical—if reversed, you may lose the rest of the list.

在给定节点后插入（中部或尾部）：将新节点的 next 设为给定节点的 next，然后将给定节点的 next 指向新节点。指针赋值的顺序至关重要——如果颠倒，可能会丢失链表的后半部分。

IB exam questions often test the correct sequence of pointer updates. In a doubly linked list, you must also update the prev references of the neighbouring nodes.

IB 考试题目常考察正确的指针更新顺序。在双向链表中，还必须更新相邻节点的 prev 引用。

6. Deleting a Node | 删除节点

Deleting a node requires modifying the pointer of the preceding node to bypass the node being removed. In a singly linked list, you must find the node before the target so that its next can be set to target’s next.

删除节点需要修改前驱节点的指针，使其绕过要删除的节点。在单链表中，必须找到目标节点的前一个节点，以便将其 next 设置为目标节点的 next。

For the head node, deletion is even simpler: just move the head pointer to the second node. In languages without automatic garbage collection, the removed node should be explicitly freed; in IB pseudocode, it is often sufficient to simply disconnect it.

对于头节点，删除更简单：只需将头指针移动到第二个节点即可。在没有自动垃圾回收的语言中，被删除的节点应显式释放；在 IB 伪代码中，通常只需断开连接即可。

For a doubly linked list, you must update both the prev of the next node and the next of the previous node. Always check for boundary conditions, such as deleting the only node in the list.

对于双向链表，必须同时更新下一个节点的 prev 和前一个节点的 next。务必检查边界条件，例如删除链表中唯一一个节点的情况。

7. Searching in a Linked List | 查找元素

Searching involves traversing the list while comparing each node’s data with the target value. Since there is no index-based random access, searching is a linear operation. As soon as the target is found, the algorithm returns the node or its position; otherwise, it continues until the end of the list.

查找操作需要遍历链表，并将每个节点的数据与目标值进行比较。由于没有基于索引的随机访问，查找是线性操作。一旦找到目标，算法会返回该节点或其位置；否则继续直至链表末尾。

In exam questions, you may be asked to implement a search that returns a Boolean or the node itself. Remember to handle the case where the list is empty to avoid null-reference errors.

在考试题目中，你可能会被要求实现返回布尔值或节点本身的查找操作。记得处理链表为空的情况，避免空引用错误。

8. Time Complexity Analysis | 时间复杂度分析

Understanding Big O notation for linked list operations is a core IB objective. A well-designed table can clarify the differences between singly and doubly linked lists.

理解链表操作的大 O 表示法是 IB 的核心目标之一。设计良好的表格可以清晰展示单链表与双向链表的区别。

Operation	Singly Linked	Doubly Linked
Access by index	O(n)	O(n)
Insert at head	O(1)	O(1)
Insert at tail (with tail pointer)	O(1)	O(1)
Insert in middle	O(n) search + O(1) update	O(n) search + O(1) update
Delete head	O(1)	O(1)
Delete given node (reference known)	O(n) to find predecessor	O(1)

The above assumes a reference to the node to be deleted is given. In a singly linked list, you must traverse from the head to find the predecessor, making it O(n). In a doubly linked list, the prev pointer allows immediate access to the predecessor, giving O(1) deletion.

上表假设已知要删除节点的引用。在单链表中，必须从头遍历寻找前驱节点，因此为 O(n)；在双向链表中，prev 指针可直接访问前驱，从而实现 O(1) 删除。

9. Linked Lists vs. Arrays | 链表与数组对比

IB exams frequently ask students to compare linked lists with arrays. The choice depends on the nature of the operations and memory constraints.

IB 考试常要求学生对比链表和数组。选择取决于操作特性和内存限制。

Memory allocation: Arrays use contiguous memory and have fixed size (static arrays) or need resizing (dynamic arrays). Linked lists use non-contiguous memory and grow dynamically without resizing overhead.
内存分配：数组使用连续内存，大小固定（静态数组）或需要调整大小（动态数组）。链表使用非连续内存，可动态增长，无需调整大小的开销。
Insertion/Deletion: Arrays require shifting elements (O(n)). Linked lists need only pointer updates (O(1) after position is located), but reaching the position may take O(n).
插入/删除：数组需要移动元素（O(n)）。链表只需更新指针（定位后为 O(1)），但定位本身可能需 O(n)。
Direct access: Arrays offer O(1) access by index. Linked lists must traverse from the head, giving O(n).
直接访问：数组支持 O(1) 索引访问。链表必须从头遍历，为 O(n)。
Memory overhead: Arrays have minimal overhead. Linked list nodes store additional pointers, increasing memory usage.
内存开销：数组开销极小。链表节点存储额外指针，增加内存使用。

Thus, use arrays when random access and memory efficiency are priorities; use linked lists when frequent insertions/deletions at the beginning or middle are expected and dynamic sizing is needed.

因此，当随机访问和内存效率是优先考虑时，使用数组；当频繁在头部或中部插入/删除且需要动态调整大小时，使用链表。

10. Memory Management and Pointers | 内存管理与指针

Linked lists rely heavily on dynamic memory allocation. In IB pseudocode, objects are typically created using a constructor or a built-in method like new Node(). When nodes are removed, they become inaccessible and, in languages with garbage collection, are automatically reclaimed. In other contexts, explicit deallocation is required to prevent memory leaks.

链表严重依赖动态内存分配。在 IB 伪代码中，对象通常通过构造函数或内建方法（如 new Node()）创建。当节点被移除后，它们变得不可访问，在具有垃圾回收的语言中会被自动回收。在其他环境中，需要显式释放内存以防止内存泄漏。

Understanding pointers (or references) is essential for tracing linked list algorithms. A common exam question presents a series of pointer diagrams and asks you to determine the resulting list after executing a code segment.

理解指针（或引用）对追踪链表算法至关重要。常见的考题会给出一系列指针图示，要求你确定执行某代码段后的链表状态。

11. Applications of Linked Lists | 链表的应用

Knowing where linked lists are used helps in answering design questions and justifying data structure choices:

了解链表的应用场景有助于回答设计题并论证数据结构的选择：

Implementation of stacks and queues (where push/pop or enqueue/dequeue are O(1) when using a linked list with a head/tail pointer).
实现栈和队列（使用带有头/尾指针的链表时，压栈/弹栈或入队/出队都是 O(1)）。
Dynamic memory allocation tables in operating systems maintain free memory blocks as linked lists.
操作系统中的动态内存分配表将空闲内存块维护为链表。
Polynomial representation where each term (coefficient, exponent) is a node, making addition and multiplication cleaner.
多项式表示，每一项（系数、指数）作为一个节点，使得加法和乘法更简洁。
Music playlists and web browser history (back/forward) often use doubly linked lists.
音乐播放列表和网页浏览器历史记录（前进/后退）常使用双向链表。
Separate chaining in hash tables uses linked lists to handle collisions.
哈希表中的拉链法使用链表处理冲突。

12. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧

Null pointer exceptions: Always check if the list or a node reference is null before accessing its fields. Failing to do so is a frequent error in IB code traces.

空指针异常：在访问节点的字段前，务必检查链表或节点引用是否为 null。遗漏该检查是 IB 代码追踪中的常见错误。

Losing the rest of the list: When inserting or deleting, update pointers in the correct order. Draw a diagram if allowed; it clarifies the sequence.

丢失链表其余部分：插入或删除时，按正确顺序更新指针。如果允许，画出示意图可理清顺序。

Boundary cases: Test your algorithm on empty lists, single-node lists, and operations at the head and tail. IB mark schemes often reward consideration of edge cases.

边界情况：在空链表、单节点链表以及在头部、尾部操作上测试你的算法。IB 评分方案通常奖励对边界情况的考虑。

Confusing indexes with pointers: Arrays use indexes; linked lists use nodes and references. Never mix these in pseudocode. Use appropriate notation like node.next, not list[ i ].

混淆索引与指针：数组使用索引；链表使用节点和引用。在伪代码中切勿混用。使用合适的符号，如 node.next，而非 list[ i ]。

Time complexity precision: Remember that accessing the k-th element is O(n) because you traverse from the head. In a doubly linked list with a tail pointer, accessing the last element is O(1) if you start from the tail; but this is not the same as random access by index.

时间复杂度精确表述：记住访问第 k 个元素是 O(n)，因为要从头遍历。在具有尾指针的双向链表中，如果从尾部开始，访问最后一个元素是 O(1)；但这与按索引随机访问不同。

IB pseudocode style: Use clear variable names, proper indentation, and the key control structures found in the IB guide (while loops, if statements). Practise writing insertion and deletion methods until they become second nature.

IB 伪代码风格：使用清晰的变量名、适当的缩进以及 IB 指南中的关键控制结构（while 循环、if 语句）。反复练习编写插入和删除方法，直到信手拈来。

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

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

IB Computer Science: Linked Lists – Key Concepts | IB 计算机：链表 考点精讲