📚 Linked Lists | 链表考点精讲
A linked list is a dynamic data structure used to store an ordered sequence of items. Unlike arrays, elements in a linked list are not stored in contiguous memory locations; each element, called a node, contains a data field and a reference (or pointer) to the next node in the sequence. This structure allows efficient insertion and deletion of nodes without the need to shift other elements, making it a fundamental topic in the Edexcel A-Level Computer Science syllabus. Understanding linked lists is essential for grasping dynamic memory allocation, pointer manipulation, and the trade-offs between different data structures.
链表是一种动态数据结构，用于存储有序的数据序列。与数组不同，链表中的元素并不存储在连续的内存位置中；每个元素称为节点，包含一个数据域和一个指向序列中下一个节点的引用（或指针）。这种结构允许高效地插入和删除节点，而不需要移动其他元素，这使得它成为 Edexcel A-Level 计算机科学大纲中的基础主题。理解链表对于掌握动态内存分配、指针操作以及不同数据结构之间的权衡至关重要。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of nodes, where each node contains some data and a link to the next node. The start of the list is indicated by a special pointer called the head. The last node points to a null value, which signals the end of the list. There is no need for a predefined size; the list grows and shrinks dynamically at runtime by allocating and deallocating nodes in the heap memory.
链表是节点的线性集合，每个节点包含一些数据和一个指向下一个节点的链接。链表的开头由一个称为头指针的特殊指针指示。最后一个节点指向空值，表示链表的结束。链表不需要预定义大小；它在运行时通过在堆内存中分配和释放节点来动态增长和收缩。
2. Nodes and Pointers | 节点与指针
Each node in a linked list is typically defined as a record or an object containing two components: a data field (which may hold an integer, string, or any other data type) and a pointer (often called 'next') that stores the address of the subsequent node. In pseudocode, a node can be represented as:
链表中的每个节点通常定义为一个记录或对象，包含两个部分：数据域（可以存放整数、字符串或任何其他数据类型）和一个指针（常被命名为 'next'），该指针存储后续节点的地址。在伪代码中，节点可以表示为：
TYPE Node
DECLARE data : STRING
DECLARE next : INTEGER ← pointer to next node index
节点类型
声明 data : 字符串
声明 next : 整数 ← 指向下一节点索引的指针
Pointers are essentially memory addresses. When a linked list is implemented using arrays and indexes, the pointer is an integer representing the array index of the next node. This is called a 'static linked list' or 'array-based list'. When dynamic memory allocation is used (e.g., using objects or records with pointers), it is a 'dynamic linked list'.
指针本质上是内存地址。当链表使用数组和索引实现时，指针是一个整数，表示下一个节点的数组索引，这称为“静态链表”或“基于数组的链表”。当使用动态内存分配（例如，使用带有指针的对象或记录）时，则为“动态链表”。
3. Static vs Dynamic Implementation | 静态实现与动态实现
The Edexcel specification distinguishes between two approaches to implement a linked list: static (using arrays) and dynamic (using objects with references). In a static implementation, an array of nodes is declared; each row represents a node with a data column and a next column. The head is stored as an integer pointer to the first node's index. Null is typically represented by -1 or 0 where indexes start at 1. This method is useful when you have no direct pointer data type in pseudocode.
Edexcel 大纲区分了链表的两种实现方式：静态（使用数组）和动态（使用带有引用的对象）。在静态实现中，声明一个节点数组；每一行代表一个节点，包含数据列和下一节点索引列。头指针存储为一个整数，指向第一个节点的索引。空值通常用 -1 或 0 表示（索引从 1 开始的情况）。当伪代码中没有直接的指针数据类型时，这种方法很实用。
A dynamic implementation uses a linked structure where each node is an object created from a class. New nodes are created with a constructor, and pointers are references to objects. For example:
动态实现使用一种链接结构，其中每个节点都是一个由类创建的对象。新节点使用构造函数创建，指针是对象的引用。例如：
node = Node(data, nextPointer)
节点 = 创建节点(数据, 下一指针)
Static lists have a fixed maximum size, while dynamic lists can grow until heap memory is exhausted. Both approaches require careful management of the head pointer and updating of links during operations.
静态链表有固定的最大大小，而动态链表可以增长直到堆内存耗尽。两种方法都需要小心管理头指针，并在操作期间更新链接。
4. Traversing a Linked List | 链表的遍历
To visit each node in a linked list, you start from the head and follow the next pointers until you encounter a null value. This process is called traversal. You cannot directly access an index; instead, you must walk through the links sequentially. A typical traversal loop in pseudocode is:
要访问链表中的每个节点，需要从头指针开始，沿着下一指针前进，直到遇到空值。这个过程称为遍历。你不能直接通过索引访问；必须依次沿着链接步进。典型的遍历循环伪代码如下：
current ← head
WHILE current ≠ NULL DO
OUTPUT current.data
current ← current.next
ENDWHILE
current ← 头指针
当 current ≠ 空值 执行
输出 current.数据
current ← current.下一节点
结束循环
This sequential access is a key difference from arrays, where elements can be accessed in constant time O(1). Traversal takes O(n) time, where n is the number of nodes.
这种顺序访问是与数组的关键区别，数组可以在常数时间 O(1) 内访问元素。遍历需要 O(n) 时间，其中 n 是节点数。
In a static array-based implementation, traversal uses the next column as the index of the next node. The condition to stop is often when next equals -1.
在基于数组的静态实现中，遍历使用下一列作为下一个节点的索引。停止条件通常是当下一列等于 -1 时。
5. Inserting a Node | 插入节点
Inserting a node into a linked list can be done at the beginning, in the middle, or at the end. The key advantage is that it does not require shifting subsequent elements. Let's consider inserting a new node with value 'X' after a given node 'P'.
将节点插入链表可以在开头、中间或末尾进行。关键的优点是它不需要移动后续元素。考虑将值为 'X' 的新节点插入到给定节点 'P' 之后。
Steps for insertion after node P:
在节点 P 之后插入的步骤：
- Allocate a new node with data 'X'.
- 分配一个包含数据 'X' 的新节点。
- Set the new node's next pointer to the node following P (i.e., P.next).
- 将新节点的下一指针设置为 P 之后的节点（即 P.next）。
- Update P's next pointer to point to the new node.
- 更新 P 的下一指针，使其指向新节点。
This requires finding node P first (via traversal if not already known), which takes O(n), but the insertion itself is O(1). Inserting at the front is a special case: the new node's next is the old head, and then the head pointer is updated to the new node.
这需要先找到节点 P（如果未知，则通过遍历），这需要 O(n) 时间，但插入本身是 O(1)。在链表前端插入是一种特殊情况：新节点的下一指针指向旧的头节点，然后头指针更新为新节点。
6. Deleting a Node | 删除节点
Deleting a node also requires pointer manipulation. To delete the node after a known node P, we directly bypass it by setting P's next pointer to the node after the one being deleted. If the node to be deleted is the first node (head), we simply move the head pointer to the second node. Memory must be freed if using dynamic implementation to avoid memory leaks.
删除节点也需要指针操作。要删除已知节点 P 之后的节点，我们直接绕过它，将 P 的下一指针设置为被删除节点之后的节点。如果要删除的节点是第一个节点（头节点），我们只需将头指针移动到第二个节点。如果使用动态实现，必须释放内存以避免内存泄漏。
In pseudocode for deleting a node with data value X from the list (assuming unique values):
伪代码中从链表中删除数据值为 X 的节点（假设值唯一）：
IF head = NULL THEN RETURN
IF head.data = X THEN
head ← head.next
RETURN
ENDIF
current ← head
WHILE current.next ≠ NULL DO
IF current.next.data = X THEN
current.next ← current.next.next
RETURN
ENDIF
current ← current.next
ENDWHILE
如果 头指针 = 空值 则 返回
如果 头节点.数据 = X 则
头指针 ← 头指针.下一节点
返回
结束如果
current ← 头指针
当 current.下一节点 ≠ 空值 执行
如果 current.下一节点.数据 = X 则
current.下一节点 ← current.下一节点.下一节点
返回
结束如果
current ← current.下一节点
结束循环
Deletion also requires finding the predecessor node, which in the worst case involves traversing the entire list.
删除也需要找到前驱节点，最坏情况下需要遍历整个链表。
7. Searching a Linked List | 搜索链表
Searching for a specific value in a linked list requires a linear search, starting from the head and comparing each node's data until a match is found or the end is reached. There is no advantage of binary search because there is no random access. The time complexity is O(n) in the worst and average cases.
在链表中搜索特定值需要进行线性搜索，从头节点开始，比较每个节点的数据，直到找到匹配或到达末尾。因为无法随机访问，所以不能使用二分搜索的优势。最坏和平均情况下的时间复杂度为 O(n)。
If the list is unsorted, we must check every node. If sorted, we can stop early if we pass the point where the value could be, but it still remains O(n). Edexcel questions often ask for pseudocode to search and return a pointer to the node or a Boolean indicating presence.
如果链表是无序的，我们必须检查每个节点。如果有序，一旦超过值可能出现的位置就可以提前停止，但这仍然是 O(n)。Edexcel 考题常常要求写出搜索并返回节点指针或指示是否存在的布尔值的伪代码。
8. Circular and Doubly Linked Lists | 循环链表与双向链表
The syllabus may refer to variations of linked lists. A circular linked list is one where the last node points back to the head instead of to null. This allows continuous traversal from any node. A doubly linked list has two pointers per node: one to the next node and one to the previous node. This allows traversal in both directions and simplifies deletion because you can access the predecessor directly from the node being deleted.
大纲可能会提到链表的变体。循环链表是指最后一个节点指回头节点而不是空值。这样可以从任意节点开始连续遍历。双向链表每个节点有两个指针：一个指向下一个节点，另一个指向前一个节点。这允许双向遍历，并简化了删除操作，因为可以直接从被删除的节点访问其前驱节点。
Understanding how pointers are updated during insertion and deletion in doubly linked lists is an extension of single linked list ideas. However, Edexcel focuses primarily on the singly linked list and its static/dynamic implementations.
理解双向链表中插入和删除时指针的更新是对单链表概念的延伸。然而，Edexcel 主要关注单向链表及其静态/动态实现。
9. Linked Lists vs Arrays | 链表与数组的比较
A classic exam question asks you to compare linked lists with arrays. Here are the key points:
经典的考题会要求比较链表与数组。以下是关键要点：
| Feature | 特性 | Array | 数组 | Linked List | 链表 |
|---|---|---|
| Memory allocation | 内存分配 | Static, contiguous | 静态、连续 | Dynamic, non-contiguous | 动态、非连续 |
| Size flexibility | 大小灵活性 | Fixed (or resized expensively) | 固定（或代价高昂地调整） | Grows/shrinks easily | 容易增长/收缩 |
| Access time | 访问时间 | O(1) random access | O(1) 随机访问 | O(n) sequential access | O(n) 顺序访问 |
| Insertion/Deletion | 插入/删除 | O(n) due to shifting | O(n) 因移动元素 | O(1) after position found | 找到位置后 O(1) |
| Memory overhead | 内存开销 | None (just data) | 无（仅数据） | Extra pointer per node | 每个节点额外指针 |
Choose an array when frequent random access is required and size is known. Choose a linked list when insertions and deletions are frequent and memory is scarce in terms of fragmentation.
当需要频繁随机访问且大小已知时选择数组。当插入和删除频繁且内存分片方面稀缺时选择链表。
10. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧
NULL). Forgetting to update pointers correctly can lead to losing the list. Always draw a diagram of nodes and pointers before coding. In static implementation, be careful with index values and ensure you treat -1 as null. In dynamic implementation, remember to allocate new nodes (e.g., using NEW Node) and dispose of deleted nodes if required by the question.
在编写链表操作的伪代码时，要确保处理空链表（head = NULL）这种特殊情况。忘记正确更新指针可能导致链表丢失。在编码前务必画出节点和指针的示意图。在静态实现中，要注意索引值，并确保将 -1 视为空值。在动态实现中，记得分配新节点（例如使用 NEW Node），如果题目要求则释放已删除节点。
Time complexity questions often ask about the efficiency of operations. Clearly state O(1) for insertion at front, O(n) for searching or inserting at a given position (because you must first traverse to that position).
时间复杂度问题常问操作的效率。要清楚说明在头部插入是 O(1)，搜索或插入到给定位置是 O(n)（因为必须先遍历到该位置）。
The concept of a 'pointer' in Edexcel pseudocode often uses array indices in static lists or object references in dynamic lists. Do not confuse low-level memory addresses with high-level pseudocode pointers.
Edexcel 伪代码中的“指针”概念通常在静态链表中使用数组索引，在动态链表中使用对象引用。不要将低级内存地址与高级伪代码指针混淆。
11. Exam-Style Question Walkthrough | 考试风格题目演练
Let us consider a typical Edexcel question: 'A static linked list of strings stores names in alphabetical order. Write pseudocode to insert a new name while maintaining the sorted order.' Approach:
让我们看一道典型的 Edexcel 题目：“一个存储名字的静态字符串链表按字母顺序排列。写出插入一个新名字并保持排序顺序的伪代码。” 解题思路：
- If the list is empty or the new name is alphabetically before the head, insert at the front.
- 如果链表为空，或者新名字按字母顺序在头节点之前，则插入到最前面。
- Otherwise, traverse to find the correct position. Look at current.next.data. When you find a name greater than the new one, insert the new node between current and current.next.
- 否则，遍历以找到正确位置。查看 current.next.data。当找到一个比新名字大的名字时，将新节点插入到 current 和 current.next 之间。
- Be careful to update next pointers correctly.
- 注意正确更新下一指针。
This type of question tests your understanding of traversal combined with insertion. Always check boundary conditions: insertion before head, insertion at tail, and insertion into an empty list.
这类题目考察你对遍历和插入结合的理解。始终检查边界条件：在头部之前插入、在尾部插入以及插入空链表。
12. Summary and Key Takeaways | 总结与关键要点
Linked lists are a dynamic, node-based structure offering efficient insertions and deletions at the cost of sequential access. Master the static and dynamic implementations, pointer update sequences for insertion/deletion, and the ability to trace and write pseudocode for common operations. Remember that while arrays provide O(1) indexing, linked lists excel when the collection frequently changes size. This fundamental understanding will serve you well in algorithm design and in answering both short and extended response questions in the Edexcel A-Level Computer Science exam.
链表是一种基于节点的动态结构，以顺序访问为代价提供了高效的插入和删除。掌握静态和动态实现、插入/删除的指针更新序列，以及追踪和编写常见操作伪代码的能力。记住，数组提供 O(1) 索引，但链表在集合频繁改变大小时表现出色。这种基础理解将在算法设计以及 Edexcel A-Level 计算机科学考试的简答题和扩展回答题中对你有很大帮助。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图