Linked Lists: Key Concepts and Exam Essentials | 链表考点精讲

📚 Linked Lists: Key Concepts and Exam Essentials | 链表考点精讲

A linked list is a dynamic data structure consisting of a sequence of nodes, where each node contains data and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing efficient insertions and deletions without shifting elements. For IB and WJEC Computer Science, mastering linked lists means understanding node composition, the fundamental operations (traversal, insertion, deletion), and the comparative strengths and limitations relative to arrays. This article consolidates key concepts, common pitfalls, and exam-relevant details to help you secure top marks.

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向序列中下一个节点的指针（或引用）。与数组不同，链表不需要连续的内存分配，因此能够在不移动其他元素的情况下高效地插入和删除。对于 IB 和 WJEC 计算机科学考试，掌握链表意味着理解节点的构成、基本操作（遍历、插入、删除）以及与数组相比的优势和局限。本文整合了核心概念、常见易错点和考试要点，助你取得高分。

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

A linked list is a linear collection of nodes where the order of elements is determined by pointers, not by their physical positions in memory. Each node knows only about its immediate neighbour(s), making the structure inherently sequential. The start of the list is marked by a special pointer called the ‘head’. If the list is empty, the head is NULL (or None). The last node’s pointer points to NULL, indicating the end of the list.

链表是一种线性的节点集合，元素的顺序由指针决定，而不是由它们在内存中的物理位置决定。每个节点只知道它的直接邻居，这使得结构本质上就是顺序的。链表的起点由一个称为“头指针”的特殊指针标记。如果链表为空，头指针为 NULL（或 None）。最后一个节点的指针指向 NULL，表示链表的结束。

Dynamic memory allocation is a key feature: nodes can be added or removed at runtime without pre-allocating a fixed-size block. This makes linked lists particularly useful when the number of elements is unknown or changes frequently.

动态内存分配是一个关键特性：节点可以在运行时添加或移除，无需预先分配固定大小的内存块。这使得链表在元素数量未知或频繁变动时特别有用。

2. Node Structure | 节点结构

A node in a singly linked list consists of two parts: the data field (storing the actual value) and a next field (storing the memory address of the next node). In pseudocode, this is typically represented as a record or class with two attributes: data and next. For example, in Python-like pseudocode: NODE = [data, next].

单向链表中的节点由两部分组成：数据域（存储实际值）和 next 域（存储下一个节点的内存地址）。在伪代码中，这通常表示为一个具有两个属性的记录或类：data 和 next。例如，在类似 Python 的伪代码中：NODE = [data, next]。

In a doubly linked list, each node also contains a prev pointer for backward traversal. A typical doubly linked node is defined as NODE = [data, prev, next]. Understanding this structure is fundamental because every operation — insertion, deletion, or search — depends on correctly manipulating these pointers.

在双向链表中，每个节点还包含一个 prev 指针用于向后遍历。典型的双向链节点定义为 NODE = [data, prev, next]。理解这一结构是基础，因为每种操作（插入、删除或搜索）都依赖于正确操作这些指针。

3. Types of Linked Lists: Singly, Doubly, Circular | 链表的类型：单向、双向、循环

Singly linked lists: nodes only point to the next node. Traversal is one-directional. They use less memory per node but cannot be navigated backwards without recursion or an external stack.

单向链表：节点只指向下一个节点。遍历是单向的。每个节点使用的内存较少，但如果不使用递归或外部栈，则无法向后导航。

Doubly linked lists: each node has both next and prev pointers. This allows bidirectional traversal and makes deletion of a given node easier (since you can access its predecessor directly). The trade-off is extra memory for the additional pointer.

双向链表：每个节点同时有 next 和 prev 指针。这允许双向遍历，并使删除给定节点更简单（因为可以直接访问其前驱）。代价是额外的指针占用更多内存。

Circular linked lists: the last node points back to the head (or to the first node) instead of NULL. In a circular doubly linked list, the head’s prev points to the last node. This structure is useful for applications that cycle through items repeatedly, such as round-robin scheduling.

循环链表：最后一个节点指向头节点（或第一个节点），而不是 NULL。在循环双向链表中，头节点的 prev 指向最后一个节点。这种结构适用于需要反复遍历元素的应用，例如轮询调度。

4. Traversing a Linked List | 遍历链表

Traversal is the process of visiting each node sequentially, starting from the head. A temporary pointer (often called current or ptr) moves through the list until it becomes NULL. In a loop, you process the data at the current node and then advance by assigning current = current.next.

遍历是从头节点开始依次访问每个节点的过程。使用一个临时指针（通常称为 current 或 ptr）在链表中移动，直到到达 NULL。在循环中，处理当前节点的数据，然后通过 current = current.next 向前移动。

The traversal pattern is crucial for searching, counting nodes, and printing the list. Its time complexity is O(n) because every node must be visited once. A common exam question asks you to write pseudocode for traversing a linked list and computing the sum of data, finding a maximum value, or outputting elements in reverse order (which in a singly linked list may require recursion or building a secondary stack).

遍历模式对于搜索、计数节点和打印链表至关重要。其时间复杂度为 O(n)，因为每个节点都必须被访问一次。常见的考题要求编写伪代码来遍历链表，并计算数据之和、查找最大值或逆序输出元素（在单向链表中可能需要递归或借助辅助栈）。

5. Insertion Operations | 插入操作

Insertion in a linked list can happen at the beginning, at the end, or at a specific position. All insertion algorithms require updating pointers carefully to avoid breaking the chain.

Insertion at the head: create a new node, set its next to the current head, then update head to point to the new node. Time complexity O(1).
Insertion at the tail: traverse to the last node (whose next is NULL), set its next to the new node. Time complexity O(n) unless a tail pointer is maintained.
Insertion at a given position (sorted insert): traverse to the node before the insertion point, set the new node’s next to the current node’s next, then update the current node’s next to the new node. Time complexity O(n) for the traversal.

在链表中插入操作可以在开头、结尾或特定位置进行。所有插入算法都需要小心地更新指针，避免破坏链表结构。

在头部插入：创建新节点，将其 next 设为当前头节点，然后更新头指针指向新节点。时间复杂度 O(1)。
在尾部插入：遍历到最后一个节点（其 next 为 NULL），将其 next 指向新节点。时间复杂度 O(n)，除非维护了尾指针。
在指定位置插入（有序插入）：遍历到插入点之前的节点，将新节点的 next 设为当前节点的 next，然后将当前节点的 next 更新为新节点。遍历导致时间复杂度 O(n)。

For doubly linked lists, insertion also requires updating the prev pointer of the new node and the affected neighbour(s). Always remember the correct order of updates: first link the new node to its neighbours, then redirect the neighbours’ pointers to the new node. Reversing the order can cause the list to lose track of subsequent nodes.

对于双向链表，插入还需要更新新节点的 prev 指针和受影响的邻居的指针。务必记住正确的更新顺序：先将新节点链接到它的邻居，再将邻居的指针重定向到新节点。颠倒顺序可能导致链表丢失后续节点。

6. Deletion Operations | 删除操作

Deletion involves removing a node by its value or its position and freeing its memory (in languages with manual memory management). The critical step is adjusting the predecessor’s pointer to bypass the deleted node.

Deleting the head node: simply advance the head pointer to head.next. O(1).
Deleting a tail node: traverse to the second-to-last node and set its next to NULL. O(n).
Deleting a specific node: traverse to the node before the target, then set its next to target.next. For a doubly linked list, you can delete a node given a direct reference to it by linking its predecessor and successor together.

删除操作通过值或位置移除节点，并释放其内存（在需要手动管理内存的语言中）。关键步骤是调整前驱节点的指针，使其绕过被删除的节点。

删除头节点：只需将头指针移动到 head.next。时间复杂度 O(1)。
删除尾节点：遍历到倒数第二个节点，将其 next 设为 NULL。时间复杂度 O(n)。
删除特定节点：遍历到目标节点之前的节点，然后将其 next 设为 目标节点.next。对于双向链表，如果直接拥有对该节点的引用，则可通过链接其前驱和后继来删除节点。

Exam caution: always handle edge cases — empty list, deleting the only node, or deleting a node not present. In pseudocode, you must explicitly check for these conditions to earn full marks. Memory leak prevention is tested in IB computer science: the deleted node should be marked as available for garbage collection or explicitly freed.

考试注意：始终处理边界情况——空链表、删除唯一的节点或删除不存在的节点。在伪代码中，必须显式检查这些条件才能获得满分。预防内存泄漏也是 IB 计算机科学的考点：被删除的节点应标记为可供垃圾回收或显式释放。

7. Searching in a Linked List | 搜索操作

Linked lists support sequential search only. Starting from the head, each node’s data is compared with the target value. If a match is found, the node (or its position) is returned; otherwise, the search continues until the end of the list. The worst-case time complexity is O(n).

链表仅支持顺序搜索。从头节点开始，将每个节点的数据与目标值进行比较。如果找到匹配，则返回该节点（或其位置）；否则继续搜索直到链表末尾。最坏情况时间复杂度为 O(n)。

Search efficiency cannot match direct-index access of arrays, but for ordered singly linked lists, you can sometimes stop early if the data exceeds the search key. However, even in an ordered list, binary search is not feasible because there is no O(1) random access to the middle element.

搜索效率无法与数组的直接索引访问相媲美，但在有序单向链表中，如果数据超过搜索键值，有时可以提前停止。然而，即使在有序链表中，二分搜索也不可行，因为无法在 O(1) 时间内随机访问中间元素。

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

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 at head	O(n) due to shifting	O(1)
Insertion at tail	O(1) amortised (dynamic array)	O(n) or O(1) with tail pointer
Deletion	O(n) due to shifting	O(n) to find, O(1) to delete (once found)
Memory overhead	None (besides array size)	Extra pointer(s) per node
Cache performance	Good (locality of reference)	Poor (nodes scattered in memory)

Choosing between them often comes down to the dominant operations in the algorithm: frequent random access favours arrays; frequent insertions/deletions of non-tail elements favour linked lists. IB exam questions often ask you to justify your choice of data structure with reference to time complexity and memory usage.

在两者之间选择通常取决于算法中的主要操作：频繁的随机访问适合数组；频繁在非尾部位置插入/删除适合链表。IB 考试常要求你根据时间复杂度和内存使用来证明数据结构选择的合理性。

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

Linked list operations have well-defined time complexities that must be memorised for exam success. For a singly linked list with only a head pointer:

Access/Search: O(n)
Insert at head: O(1)
Insert at tail: O(n)
Delete at head: O(1)
Delete at tail: O(n)
Insert/Delete at given node (with reference to predecessor): O(1) once the predecessor is known; but finding that predecessor is O(n).

链表操作具有明确定义的时间复杂度，必须牢记以应对考试。对于只有头指针的单向链表：

访问/搜索：O(n)
头部插入：O(1)
尾部插入：O(n)
头部删除：O(1)
尾部删除：O(n)
在给定节点处插入/删除（已知前驱引用）：O(1)（一旦找到前驱）；但查找前驱为 O(n)。

If a tail pointer is maintained, tail insertion becomes O(1). Doubly linked lists allow O(1) deletion of a node if the node is given, because you can access its predecessor via node.prev. Always state your assumptions when answering complexity questions.

如果维护了尾指针，尾部插入可优化为 O(1)。双向链表在给定节点的情况下允许 O(1) 删除，因为可以通过 node.prev 访问其前驱。回答复杂度问题时务必说明你的假设。

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

Linked lists are used in many fundamental computing scenarios: implementing stacks and queues (especially when the size is unpredictable), managing free memory spaces (free lists), adjacency list representations in graphs, polynomial addition (each node represents a term with coefficient and exponent), and maintaining ordered sequences where insertions and deletions are frequent. Circular linked lists are applied in CPU scheduling and multiplayer game turn management.

链表在许多基本的计算场景中都有应用：实现栈和队列（特别是当大小不可预测时）、管理空闲内存空间（空闲链表）、图的邻接表表示、多项式加法（每个节点代表一个带有系数和指数的项），以及维护需要频繁插入和删除的有序序列。循环链表应用于 CPU 调度和多人游戏回合管理。

In IB and WJEC papers, you might be asked to describe an application of a linked list, or to write pseudocode for an abstract data type (ADT) such as a stack implemented with a linked list. Always recall that with a linked list, a stack’s push and pop can both be O(1) operations at the head.

在 IB 和 WJEC 试卷中，可能会要求你描述链表的一个应用，或为抽象数据类型（ADT）编写伪代码，例如用链表实现的栈。请始终记住，使用链表实现的栈，其 push 和 pop 均可在头部以 O(1) 时间完成。

11. Common Exam Pitfalls | 常见考试易错点

One frequent mistake is forgetting to handle the empty list case. For instance, when deleting a node from an empty list, the code should simply return without error. Similarly, when inserting a node into a sorted list, a candidate often fails to check if the list is empty or if the insertion is at the head.

一个常见错误是忘记处理空链表的情况。例如，从空链表中删除节点时，代码应直接返回而不抛出错误。类似地，在有序链表中插入节点时，考生常常未检查链表是否为空或插入位置是否为头部。

Pointer update order is another source of lost marks. When inserting a node new_node after a node current, the correct sequence is: new_node.next = current.next then current.next = new_node. Reversing these steps will orphan the rest of the list. Drawing diagrams in the exam can prevent this.

指针更新顺序是另一个失分点。在节点 current 之后插入节点 new_node 时，正确的顺序是：new_node.next = current.next 然后 current.next = new_node。颠倒这些步骤会使链表的其余部分丢失。在考试中绘制图表可避免此错误。

Finally, in complexity analysis, candidates sometimes claim that search in a linked list is O(1) because ‘pointers make it fast’ — this is incorrect. Access is always sequential, O(n). Also, when a tail pointer exists, remember to update it after a tail deletion or insertion to maintain consistency.

最后，在复杂度分析中，考生有时会声称链表的搜索是 O(1)，因为“指针让它变快”——这是不正确的。访问始终是顺序的，O(n)。此外，当存在尾指针时，记得在尾部删除或插入后更新尾指针，以保持一致性。

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

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

Linked Lists: Key Concepts and Exam Essentials | 链表考点精讲