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

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

A linked list is a fundamental dynamic data structure, where each element (node) stores data and a reference to the next node. This structure is examined thoroughly in both IB and OCR A-Level Computer Science, requiring you to understand how nodes are linked, how operations are performed, and how memory is managed. Mastery of linked lists is essential for grasping more advanced topics like trees, graphs, and dynamic memory allocation.

链表是一种基础动态数据结构，其中每个元素（节点）存储数据以及指向下一个节点的引用。IB 和 OCR A-Level 计算机科学课程均深入考查这一结构，要求你理解节点如何链接、操作如何执行以及内存如何管理。掌握链表对于理解树、图等更高级主题及动态内存分配至关重要。

1. Node Structure and Self-Referencing Objects | 节点结构与自引用对象

A node in a linked list is typically implemented as an object or record containing at least two fields: a data field to hold the value and a pointer (or reference) to another node of the same type. This self-referencing property allows nodes to be chained together dynamically.

链表中的节点通常实现为一个对象或记录，至少包含两个字段：用于存储值的数据字段，以及指向另一个同类型节点的指针（或引用）。这种自引用特性使得节点能够动态地链接起来。

In IB pseudocode or Java, a basic node class looks like:

在 IB 伪代码或 Java 中，基本节点类如下：

class Node
    data : integer
    next : Node
end class

The next reference holds the memory address of the following node, or null/nil if it is the last node. The head pointer stores the starting address of the list; losing the head means losing access to the whole list.

next 引用保存了后续节点的内存地址，若为最后一个节点则为 null（或 nil）。头指针存储链表的起始地址；丢失头指针意味着失去对整个链表的访问。

2. Singly Linked List: Traversal and Sequential Access | 单链表：遍历与顺序访问

A singly linked list allows movement in one direction only—from head to tail. Traversal requires following the next pointers step by step, because direct random access is impossible. The time complexity for accessing an element by index is O(n).

单链表只允许单向移动——从头到尾。遍历需要一步步跟随 next 指针，因为无法实现直接随机访问。按索引访问元素的时间复杂度为 O(n)。

The standard traversal pseudocode:

标准遍历伪代码：

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

This sequential access is efficient for scanning the whole list but inefficient for repeated index-based retrieval. You must be careful not to dereference a null pointer to avoid runtime errors.

这种顺序访问在扫描整个列表时高效，但在基于索引的重复检索时效率低下。你务必小心，不要解引用空指针，以免引发运行时错误。

3. Insertion Operations in a Singly Linked List | 单链表中的插入操作

Insertion at the head is a constant-time operation O(1): create a new node, set its next to the current head, then update head to the new node. This does not require any shifting of existing elements, unlike an array.

在头部插入是常数时间操作 O(1)：创建新节点，将其 next 设为当前头节点，然后将 head 更新为新节点。与数组不同，这不需要移动任何现有元素。

Insertion at a given position or after a target node requires traversing to the node just before the insertion point, then updating pointers: new_node.next = current.next; current.next = new_node. The traversal dominates the cost, making it O(n) in the worst case.

在指定位置或在目标节点后插入，需要遍历至插入点之前的一个节点，然后更新指针：new_node.next = current.next; current.next = new_node。遍历主导了开销，使得最坏情况下时间复杂度为 O(n)。

Special care is needed when inserting into an empty list; you simply set head to the new node and its next to null.

在向空链表插入时需要特别处理；只需将 head 设为新节点，并将其 next 设为 null 即可。

4. Deletion Operations in a Singly Linked List | 单链表中的删除操作

Deleting the head node is O(1): simply advance head to head.next. The old head becomes unreachable and will be garbage collected in languages like Java. In languages without automatic garbage collection, you must explicitly free the memory.

删除头节点是 O(1)：只需将 head 前移至 head.next。旧头变得不可达，会在 Java 等语言中被垃圾回收。在没有自动垃圾回收的语言中，你必须显式释放内存。

Deleting a node by value or at a given index again requires traversal to locate the node before the target: set previous.next = del_node.next. The target node is then bypassed. Traversal gives O(n) time complexity.

按值或按给定索引删除节点同样需要遍历，以定位目标节点的前驱：设置 previous.next = del_node.next。目标节点随后被绕过。遍历导致 O(n) 的时间复杂度。

Remember to handle deletion of the last node: simply set the preceding node’s next to null. Always check for edge cases such as deleting from an empty list or deleting a node not present.

记得处理删除最后一个节点的情况：只需将前一个节点的 next 设为 null。始终检查边界情况，例如从空链表删除，或删除不存在的节点。

5. Doubly Linked List: Bidirectional Navigation | 双向链表：双向导航

A doubly linked list adds a prev pointer to each node, enabling traversal in both forward and backward directions. This makes insertion and deletion slightly more complex but provides greater flexibility for algorithms that need reverse traversal.

双向链表为每个节点增加了 prev 指针，可同时向前和向后遍历。这使得插入和删除稍显复杂，但为需要反向遍历的算法提供了更大的灵活性。

Node definition:

节点定义：

class Node
    data : integer
    next : Node
    prev : Node
end class

Insertion requires updating both next and prev links of the new node and the adjacent nodes. For example, after inserting X between A and B: X.prev = A; X.next = B; A.next = X; B.prev = X. Deletion also involves updating prev and next of the surrounding nodes.

插入需要同时更新新节点以及相邻节点的 next 和 prev 链接。例如，在 A 和 B 之间插入 X 后：X.prev = A; X.next = B; A.next = X; B.prev = X。删除同样需要更新周围节点的 prev 和 next。

Doubly linked lists require more memory per node (extra pointer) but make operations like deletion of a given node itself O(1) if you already have a reference to that node; this is because you can access its predecessor directly via prev.

双向链表每个节点需要更多内存（额外的指针），但如果你已持有目标节点的引用，删除该节点本身的操作可达到 O(1)；因为可以通过 prev 直接访问其前驱。

6. Circular Linked Lists and Their Variants | 循环链表及其变体

A circular singly linked list is one where the last node’s next points back to the head, forming a ring. This is useful in applications that require continuous looping, such as round-robin scheduling or repeatedly traversing a playlist.

循环单链表中，最后一个节点的 next 指向头节点，形成一个环。这在需要持续循环的应用中非常有用，例如轮转调度或反复遍历播放列表。

Circular doubly linked lists connect both ends via next and prev. The head’s prev points to the tail, and the tail’s next points to the head. This enables symmetrical traversal from any point.

循环双向链表通过 next 和 prev 将两端连接起来。head 的 prev 指向尾节点，tail 的 next 指向头节点。这使得可以从任意点进行对称遍历。

When implementing circular lists, be cautious about infinite loops during traversal. You must check whether you have returned to the starting node to terminate iterating.

在实现循环链表时，遍历过程中要警惕无限循环，必须检查是否已回到起始节点以终止迭代。

7. Comparison with Arrays: When to Use Which | 与数组的对比：何时使用哪个

One of the most examined topics is the trade-off between linked lists and arrays. The key differences are summarized below:

最常考查的主题之一是链表与数组之间的权衡。关键区别总结如下：

Aspect / 方面	Array / 数组	Linked List / 链表
Memory allocation / 内存分配	Static/contiguous / 静态连续	Dynamic/non-contiguous / 动态非连续
Access time / 访问时间	O(1) random access / O(1) 随机访问	O(n) sequential / O(n) 顺序访问
Insertion/deletion at head / 头部插入/删除	O(n) shift required / 需要移动 O(n)	O(1) / O(1)
Insertion/deletion at middle / 中间插入/删除	O(n) / O(n)	O(n) search + O(1) update / O(n) 搜索 + O(1) 更新
Memory overhead / 内存开销	None (just data) / 无（仅数据）	Extra pointer per node / 每节点额外指针
Cache performance / 缓存性能	Friendly / 友好	Poor due to reference hopping / 因引用跳转较差

Choose arrays when you need fast indexed access and the size is relatively fixed. Linked lists excel when frequent insertions/deletions at the front occur or when the maximum size cannot be predetermined.

当需要快速索引访问且大小相对固定时选择数组。当频繁在头部进行插入/删除，或最大规模无法预知时，链表表现更优。

8. Dynamic Memory Allocation and Pointer Manipulation | 动态内存分配与指针操作

Nodes in a linked list are created at run-time using dynamic memory allocation (e.g. ‘new’ in Java/C++, or objects instantiated on the heap). This is a vital concept: memory for each node is allocated separately and linked via references, meaning nodes need not be stored adjacently.

链表中的节点在运行时使用动态内存分配创建（如 Java/C++ 中的 ‘new’，或在堆上实例化的对象）。这是一个至关重要的概念：每个节点的内存是单独分配并通过引用连接的，这意味着节点不必相邻存储。

In pseudocode, you often see new Node(data) which returns a pointer to the newly allocated memory. The programmer must ensure that all allocated memory is eventually freed or disengaged to avoid memory leaks, although Java’s garbage collector handles this automatically when objects become unreachable.

在伪代码中，你常会看到 new Node(data)，它返回指向新分配内存的指针。程序员必须确保所有分配的内存最终被释放或切断引用以避免内存泄漏，尽管 Java 的垃圾收集器在对象变得不可达时会自动处理。

Pointer manipulation is the core skill: swapping pointers must follow the correct sequence to prevent orphaned nodes. Drawing diagrams of nodes and arrows is strongly recommended during exams.

指针操作是核心技能：交换指针必须遵循正确顺序，以防出现孤立节点。考试时强烈建议绘制节点与箭头的图示。

9. Implementing Stacks and Queues with Linked Lists | 使用链表实现栈与队列

Due to their dynamic nature, linked lists provide an excellent underlying structure for implementing stacks and queues, often more flexibly than array-based implementations because they avoid size limitations.

由于链表的动态特性，它为栈和队列的实现提供了出色的底层结构，通常比基于数组的实现更灵活，因为它避免了大小限制。

For a stack, a singly linked list with operations at the head acts as a LIFO structure. Push corresponds to insert at head; pop to delete from head. Both are O(1). No tail pointer is needed.

对于栈来说，在头部操作的单链表可作为 LIFO 结构。Push 对应于头部插入；Pop 对应于删除头部。两者都是 O(1)。无需 tail 指针。

For a queue, we need efficient enqueue at the tail and dequeue from the head. A singly linked list with both head and tail pointers achieves O(1) for both operations. Enqueue appends a new node at tail and updates tail; dequeue removes and advances head.

对于队列，我们需要在尾部高效地入队，并从头部出队。一个同时维护头指针和尾指针的单链表可实现两种操作的 O(1) 时间复杂度。入队在尾部追加新节点并更新 tail；出队则移除并前移 head。

These implementations exemplify how linked lists adapt to abstract data types. Make sure you can write the pseudocode for push, pop, enqueue, and dequeue, paying attention to empty-structure conditions.

这些实现体现了链表如何适配抽象数据类型。确保你能编写 push、pop、enqueue 和 dequeue 的伪代码，并注意空结构的情况。

10. Traversal Algorithms and Recursive Approaches | 遍历算法与递推方法

Iterative traversal using a loop is the standard method, but singly linked lists can also be traversed recursively. A recursive function processes the current node and then calls itself with the next node until null.

使用循环的迭代遍历是标准方法，但单链表也可以递推遍历。递推函数处理当前节点，然后用下一个节点调用自身，直到 null。

Example recursive print:

递推打印示例：

procedure printList(node)
    if node == null then return
    output node.data
    printList(node.next)
end procedure

Recursion can lead to stack overflow for very long lists, but it elegantly solves problems like reversing a linked list or detecting palindromes in the exam. Always identify the base case clearly.

递推在极长链表时可能导致栈溢出，但它可以优雅地解决考试中如反转链表或检测回文等问题。务必明确界定基线条件。

Reverse traversal of a singly linked list is naturally expressed via recursion: print the rest of the list first, then the current node’s data, to output in reverse order. This is impossible with a simple iterative loop unless you use an explicit stack.

单链表的反向遍历可自然地用递推表达：先打印链表剩余部分，再打印当前节点的数据，从而以逆序输出。除非使用显式栈，否则简单的迭代循环无法实现这一点。

11. Common Pitfalls and Exam Traps | 常见误区与考题陷阱

Many students lose marks by mishandling null references, especially when deleting the only node in a list or operations on an empty list. Always test head == null first.

许多学生因错误处理空引用而失分，尤其在删除链表中唯一节点或对空链表操作时。务必首先检查 head == null。

Pointer update order is critical. When inserting, updating the new node’s next first is often safer before altering the predecessor’s next. Reversing the order can break the chain. Drawing step-by-step diagrams in the exam helps avoid these errors.

指针更新顺序至关重要。插入时，通常先更新新节点的 next 再改变前驱的 next 更安全。颠倒顺序会破坏链条。在考试中逐步绘制图示有助于避免这些错误。

Another tricky area: losing reference to the head. If you inadvertently move head or fail to return a new head from a function, the whole list may be lost. Many pseudocode solutions return the head pointer for this reason.

另一个棘手之处：丢失对头节点的引用。如果你不小心移动了 head，或未能从函数返回新的 head，整个链表可能丢失。许多伪代码解法因此返回头指针。

When using doubly linked lists, forgetting to update both prev and next can lead to corrupted lists. Also, in circular lists, incomplete termination conditions cause infinite loops. Always walk through your logic with a small test case mentally.

使用双向链表时，忘记同时更新 prev 和 next 会导致链表损坏。此外，在循环链表中，不完整的终止条件会导致无限循环。始终在脑海中使用小型测试用例走查逻辑。

12. Summary and Key Revision Points | 总结与关键复习要点

Linked lists are a core data structure that assesses your understanding of dynamic memory, pointers, and algorithmic complexity. Master the following for the exam:

链表是一个核心数据结构，考查你对动态内存、指针以及算法复杂性的理解。为考试掌握以下几点：

• Define a node with data and next (and prev) fields; explain self-referential nature.
• 能用数据字段和 next（及 prev）字段定义节点；解释自引用特性。
• Draw and trace insertion and deletion in singly, doubly, and circular lists.
• 绘制并追踪单链表、双向链表和循环链表中的插入与删除。
• State time complexities: O(1) for head insert/delete, O(n) for access/search/middle insertion due to traversal.
• 陈述时间复杂度：头部插入/删除为 O(1)，访问/搜索/中间插入因遍历为 O(n)。
• Explain trade-offs vs arrays, especially memory overhead and cache locality.
• 解释与数组的权衡，尤其是内存开销和缓存局部性。
• Apply linked lists to implement stacks and queues, giving O(1) operations.
• 应用链表实现栈和队列，实现 O(1) 操作。
• Avoid null pointer exceptions by checking for empty list and end-of-list conditions.
• 通过检查空链表和链表末尾条件，避免空指针异常。
• Use diagrams to illustrate pointer manipulation step by step.
• 用图示逐步说明指针操作。

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

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