📚 Linked List Exam Points Refined | 链表考点精讲
A linked list is a dynamic data structure used extensively in IB and Edexcel Computer Science to store collections of data. Unlike arrays, elements are not stored contiguously in memory; instead, each node holds a data value and a reference (pointer) to the next node. This design allows efficient insertion and deletion but at the cost of direct access. Understanding linked lists is vital for paper-based algorithm tracing, coding questions, and comparing data structures.
链表是 IB 和 Edexcel 计算机科学中广泛使用的一种动态数据结构。与数组不同，它的元素并不是连续存储在内存中；每个节点包含一个数据值和一个指向下一个节点的引用(指针)。这种设计使得插入和删除操作效率很高，但牺牲了直接访问的能力。理解链表对于卷面算法追踪、编程题以及数据结构比较至关重要。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of nodes where each node contains a data field and a pointer to the next node. The list is accessed through a head pointer; the last node points to null. Linked lists use dynamic memory allocation, so their size can grow or shrink at runtime, avoiding the fixed-size limitation of static arrays.
链表是一种线性节点集合，每个节点包含一个数据域和一个指向下一个节点的指针。链表通过头指针访问；最后一个节点指向 null。链表使用动态内存分配，因此其大小可以在运行时增长或缩小，避免了静态数组的固定大小限制。
2. Node Structure and Pointers | 节点结构与指针
A typical singly linked list node is a record (or object) with two attributes: data (the stored value) and next (a pointer to the successor). In pseudocode or Python, it can be represented as a class with __init__(self, data) and self.next = None. The head pointer stores the memory address of the first node; if the list is empty, head = null.
典型的单向链表节点是一个包含两个属性的记录(或对象):data(存储的值)和next(指向后继者的指针)。在伪代码或 Python 中，可以用一个类表示，并在 __init__(self, data) 中设置 self.next = None。头指针存储第一个节点的内存地址；若链表为空，head = null。
3. Singly Linked List Operations | 单向链表操作
The core operations include: traversal (visiting each node sequentially), insertion (at head, tail, or middle), deletion (by value or position), and searching (returning a node or a Boolean). All modifications require careful manipulation of pointers to avoid breaking the chain. For example, inserting at the head means creating a new node, setting its next to the old head, and updating head to the new node.
核心操作包括：遍历(按顺序访问每个节点)、插入(在头部、尾部或中间)、删除(按值或位置)以及搜索(返回节点或布尔值)。所有修改都需要小心处理指针，避免断开链表。例如，在头部插入意味着创建一个新节点，将其 next 指向旧的头节点，然后将 head 更新为这个新节点。
4. Doubly Linked List Features | 双向链表特性
In a doubly linked list, each node has three fields: data, a pointer to the next node, and a pointer to the previous node. This bi-directional linking allows traversal in both directions and simplifies deletion because you can reach the predecessor directly. However, it consumes more memory per node and requires updating two pointers during insertions and deletions.
在双向链表中，每个节点有三个域：数据、指向下一个节点的指针和指向前一个节点的指针。这种双向链接允许在两个方向上遍历，并且由于可以直接访问前驱节点，删除操作变得更简单。然而，每个节点消耗更多内存，并且在插入和删除时需要更新两个指针。
5. Circular Linked List | 循环链表
A circular linked list is a variation where the last node points back to the head, forming a loop. In a singly circular list, traversal must be carefully controlled to avoid infinite loops. This structure is useful for applications that repeatedly cycle through a set of elements, such as round-robin scheduling. An empty circular list is typically represented by a head set to null.
循环链表是一种变体，它的最后一个节点回指到头节点，形成一个环路。在单向循环链表中，遍历时必须小心控制，避免无限循环。这种结构对于需要反复循环访问一组元素的应用非常有用，例如轮询调度。空的循环链表通常用设置为 null 的头指针表示。
6. Insertion Algorithms | 插入算法
Inserting a node requires the creation of a new node, then rewiring pointers. For a singly linked list, to insert after a given node, set newNode.next = current.next, then current.next = newNode. If inserting before a node without a previous pointer, you need to traverse from the head or maintain a trailing pointer. Special cases include insertion into an empty list or at the head.
插入一个节点需要创建一个新节点，然后重新连接指针。对于单向链表，在给定节点后插入，先设 newNode.next = current.next，然后 current.next = newNode。如果没有前驱指针，要在节点前插入，则需从头遍历或维持一个尾随指针。特殊情况包括向空链表插入或在头部插入。
7. Deletion Algorithms | 删除算法
To delete a node, you must update the pointer that references it. For a singly linked list, deletion by value often requires keeping the previous node; set prev.next = current.next to bypass the node to be deleted. In a doubly linked list, deleting node p involves updating p.prev.next = p.next and, if p.next exists, p.next.prev = p.prev. Always handle edge cases: deleting the head, deleting the only node, or when the value is not found.
要删除一个节点，必须更新引用它的指针。对于单向链表，按值删除通常需要保留前一个节点；执行 prev.next = current.next 以绕过待删除节点。在双向链表中，删除节点 p 需要更新 p.prev.next = p.next，并且如果 p.next 存在，则 p.next.prev = p.prev。务必处理边界情况：删除头节点、删除唯一节点或未找到该值。
8. Traversal and Searching | 遍历与搜索
Traversal involves starting from the head and following next pointers until null is reached. A counter can track the index, or a condition can check for a target value. Searching returns true if the value is found; otherwise, it returns false. The algorithm must handle an empty list and avoid null-pointer errors. A typical while loop (current != null) is used.
遍历从 head 开始，沿着 next 指针移动，直到 null。可以用计数器跟踪索引，也可以用条件检查目标值。如果找到值，搜索返回 true；否则返回 false。算法必须处理空链表并避免空指针错误。通常使用 while 循环(current != null)来实现。
9. Time Complexity Analysis | 时间复杂度分析
| Operation | 操作 | Singly Linked List | 单向链表 | Doubly Linked List | 双向链表 |
|---|---|---|
| Access by index | 按索引访问 | O(n) | O(n) |
| Insert at head | 头部插入 | O(1) | O(1) |
| Insert at tail (with tail ptr) | 尾部插入 (有尾指针) | O(1) | O(1) |
| Insert in middle | 中间插入 | O(n) to find position + O(1) to insert | O(n) + O(1) |
| Delete head | 删除头部 | O(1) | O(1) |
| Delete given node (with pointer) | 删除给定节点（有指针） | O(n) if singly without prev | O(1) |
| Search | 搜索 | O(n) | O(n) |
These differences are key to choosing between array and linked list for a given scenario. O(1) head/tail operations make linked lists ideal for stacks and queues.
这些差异是给定场景下选择数组还是链表的关键。O(1) 的头部/尾部操作使链表非常适合实现栈和队列。
10. Linked List vs Array | 链表与数组比较
- Memory | 内存: Arrays use contiguous memory; linked lists use scattered memory with pointer overhead. Arrays may waste space due to pre-allocation; linked lists only use what is needed, but each node stores a pointer.
- 数组使用连续内存；链表使用分散内存并有指针开销。数组可能因预分配而浪费空间；链表只使用所需空间，但每个节点存储一个指针。
- Access | 访问: Arrays give O(1) random access; linked lists require O(n) sequential access.
- 数组提供 O(1) 随机访问；链表需要 O(n) 顺序访问。
- Insert/Delete | 插入/删除: Arrays need shifting elements O(n); linked lists can achieve O(1) at known positions.
- 数组需要移动元素 O(n)；链表在已知位置可实现 O(1)。
- Cache performance | 缓存性能: Arrays benefit from locality of reference; linked lists suffer from poor cache utilization.
- 数组受益于引用的局部性；链表的缓存利用率较差。
11. Applications of Linked Lists | 链表的应用
Linked lists underpin many higher-level data structures. They are used to implement stacks and queues (especially when size is unknown), adjacency lists in graphs, polynomial representation (each node stores coefficient and exponent), and in operating systems for process queues and free space management. Music players use circular doubly linked lists to loop through tracks.
链表支持许多高级数据结构。它们用于实现栈和队列(特别是当大小未知时)、图中的邻接表、多项式表示(每个节点存储系数和指数)，以及操作系统中的进程队列和空闲空间管理。音乐播放器使用循环双向链表来循环播放曲目。
12. Implementation Pitfalls | 实现中的常见陷阱
Common mistakes include forgetting to update the head pointer after deletion, losing references when re-linking nodes, failing to check for null before dereferencing, and infinite loops in circular lists when termination conditions are incorrect. In an exam, always trace your code with a simple diagram, marking pointer assignments step by step. Test edge cases: empty list, single node, head changes, tail changes.
常见错误包括：删除后忘记更新头指针；重新链接节点时丢失引用；解引用前未检查 null；循环链表中终止条件不正确导致无限循环。考试时，务必用简单图形追踪代码，逐步标记指针赋值。测试边界情况：空链表、单节点、头节点变化、尾节点变化。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply