📚 A-Level OCR Computer Science: Linked Lists Key Points | A-Level OCR 计算机：链表 考点精讲
Linked lists are dynamic data structures that store elements in nodes, with each node containing data and a reference (or pointer) to the next node. For A-Level OCR Computer Science, understanding linked lists is crucial for mastering data structures, memory management, and algorithm efficiency.
链表是一种动态数据结构，以节点形式存储元素，每个节点包含数据以及指向下一个节点的引用（或指针）。在A-Level OCR计算机科学中，理解链表对于掌握数据结构、内存管理和算法效率至关重要。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of nodes that are not stored contiguously in memory. Each node points to the next, forming a chain-like structure.
链表是节点的一种线性集合，这些节点在内存中并非连续存储。每个节点都指向下一个节点，形成链状结构。
Unlike arrays, linked lists can easily grow or shrink in size during program execution without costly reallocation.
与数组不同，链表可以在程序执行期间轻松地增大或缩小，而无需昂贵的重新分配。
There is no predetermined capacity; nodes are allocated individually on the heap (in high-level languages) or in free store, providing true dynamic sizing.
没有预先确定的容量；节点在高阶语言的堆中或在空闲存储区中单独分配，提供了真正的动态大小调整。
2. Structure of a Node | 节点的结构
A node typically contains two fields: the data field (holding the value) and a pointer field (holding the address of the next node).
节点通常包含两个字段：数据字段（保存值）和指针字段（保存下一个节点的地址）。
In singly linked lists, the node has a single link; the data can be of any type (integer, string, or even another object).
在单向链表中，节点只有一个链接；数据可以是任何类型（整数、字符串乃至另一个对象）。
In doubly linked lists, a node also contains a pointer to the previous node, enabling two-way traversal.
在双向链表中，节点还包含指向前一个节点的指针，从而支持双向遍历。
The last node’s pointer field typically holds a null value (∅, None, or NULL), marking the end of the list.
最后一个节点的指针字段通常保存空值（∅、None或NULL），标志着链表结束。
3. Singly Linked Lists | 单向链表
A singly linked list has a head pointer to the first node. The only navigation direction is forward.
单向链表有一个指向第一个节点的头指针。唯一的导航方向是向前。
Insertion and deletion at the head are O(1) operations because only the head pointer needs updating.
在头部插入和删除是O(1)操作，因为只需要更新头指针。
Accessing an element by index requires O(n) time as you must traverse node by node from the head.
通过索引访问元素需要O(n)时间，因为必须从头开始逐个遍历节点。
The end of the list is detected when a node’s next pointer is null. Always check for null to avoid runtime errors.
当节点的next指针为null时，即检测到链表末尾。务必检查null以避免运行时错误。
4. Doubly Linked Lists | 双向链表
Each node has both a ‘previous’ and a ‘next’ pointer, allowing forward and backward traversal.
每个节点同时拥有’previous’和’next’指针，可向前和向后遍历。
This doubles the per-node memory overhead but makes deletion more efficient, as you can directly access the predecessor in O(1) without searching.
这让每个节点的内存开销加倍，但删除操作更高效，因为可以在O(1)内直接访问前驱，无需搜索。
A typical doubly linked list maintains both head and tail pointers, enabling O(1) insertions/removals at both ends.
典型的双向链表同时维护头指针和尾指针，可在两端实现O(1)的插入/删除。
When deleting a node, you must carefully update the previous node’s next and the next node’s previous to keep the chain intact.
删除节点时，必须仔细更新前一个节点的next和后一个节点的previous，以保持链的完整性。
5. Circular Linked Lists | 循环链表
In a circular linked list, the last node points back to the first node instead of null, forming a ring.
在循环链表中，最后一个节点指回第一个节点而不是空值，形成一个环。
This can be singly or doubly circular. A singly circular list uses only next pointers; a doubly circular list also links backward.
这可以是单向或双向循环。单向循环链表只使用next指针；双向循环链表还向后链接。
Circular lists are useful for applications that repeatedly cycle through elements, such as round-robin scheduling or a lobby system for multiplayer games.
循环链表适用于需要重复遍历元素的应用，例如轮转调度或多玩家游戏的大厅系统。
Traversal must avoid infinite loops; you usually stop when you return to the head (or use a sentinel node).
遍历时必须避免无限循环；通常当返回头节点时停止（或使用哨兵节点）。
6. Traversing a Linked List | 遍历链表
Traversal starts at the head and follows each next pointer. You must check for null (or reach the head again in circular lists) to know when to stop.
遍历从头节点开始，沿着每个next指针前进。必须检查null（或在循环链表中再次到达头节点）以知道何时停止。
A typical pseudocode for traversing a singly linked list:
典型的单向链表遍历伪代码：
current = head
while current != null
output current.data
current = current.next
endwhileThis algorithm outputs all elements sequentially. It is an O(n) operation where n is the number of nodes.
该算法按顺序输出所有元素。这是一个O(n)操作，其中n是节点数量。
For a doubly linked list, you can equally traverse backward using the tail and previous pointers.
对于双向链表，可以同样使用尾指针和previous指针向后遍历。
7. Inserting a Node | 插入结点
To insert at the beginning: create new node, set new_node.next = head, then head = new_node.
在开头插入：创建新节点，设置new_node.next = head，然后head = new_node。
Inserting in the middle requires finding the node before the insertion point (prev). Then: new_node.next = prev.next; prev.next = new_node.
在中间插入需要找到插入点之前的节点(prev)。然后：new_node.next = prev.next; prev.next = new_node。
When inserting into an empty list, simply set head = new_node and new_node.next = null.
插入空链表时，只需设置head = new_node且new_node.next = null。
Be careful to update pointers in the correct order; if you change prev.next before linking the new node to the rest of the list, you lose the tail.
注意按正确顺序更新指针；如果在将新节点链接到列表其余部分之前更改prev.next，会丢失尾部。
8. Deleting a Node | 删除结点
To delete the head node: if list not empty, head = head.next. The old head becomes unreachable and is garbage collected.
删除头节点：若链表非空，head = head.next。旧头节点变为不可达并被垃圾回收。
Deleting a middle node: locate the previous node (prev). Set prev.next = prev.next.next, effectively bypassing the deleted node.
删除中间节点：定位前一个节点(prev)。设置prev.next = prev.next.next，从而绕过被删除节点。
In a doubly linked list, you must also update the previous pointer of the node after the deleted one.
在双向链表中，还必须更新被删除节点之后节点的previous指针。
Always handle edge cases: empty list, single-node list, and node not found. Failing to check leads to runtime errors in exams.
务必处理边界情况：空链表、单节点链表和节点未找到。考试中若未检查将导致运行时错误。
9. Comparing Linked Lists and Arrays | 链表与数组的比较
Linked lists and arrays each have distinct strengths. The table below summarises key differences relevant to OCR exams.
链表和数组各有其独特优势。下表总结了与OCR考试相关的关键差异。
| Feature | 特性 | Linked List | 链表 | Array | 数组 |
|---|---|---|
| Memory allocation | 内存分配 | Dynamic, non-contiguous | 动态、不连续 | Static/dynamic, contiguous | 静态/动态、连续 |
| Size flexibility | 大小灵活性 | Grows/shrinks easily | 轻松增减 | Fixed size (or resizing costly) | 固定大小（或调整代价高） |
| Random access | 随机访问 | O(n) traversal needed | 需要O(n)遍历 | O(1) via index | 通过索引O(1) |
| Insert/delete at start | 开头插入/删除 | O(1) | O(1) | O(n) (shifting required) | O(n)（需移动） |
| Memory overhead | 内存开销 | Extra pointer per node | 每个节点额外指针 | No pointers, but may have unused slots | 无指针，但可能有未用槽 |
| Cache performance | 缓存性能 | Poor (scattered) | 较差（分散） | Better (contiguous) | 更好（连续） |
In OCR exam questions, you are often asked to justify the choice of linked list versus array based on these factors.
在OCR考题中，经常会要求你根据这些因素说明选择链表还是数组的理由。
10. Applications and Pros/Cons | 应用与优缺点
Common applications include implementing stacks and queues (especially when frequent resizing is needed), managing playlists in media players, and supporting undo/redo in editors.
常见应用包括实现栈和队列（特别是需要频繁调整大小时）、管理媒体播放器的播放列表，以及在编辑器中支持撤销/重做。
Undo functionality often uses a doubly linked list: each state points to the previous and next state, allowing forward and backward navigation through history.
撤销功能常使用双向链表：每个状态指向前后状态，可在历史记录中前后导航。
Pros: dynamic size, no memory waste from unused slots, efficient O(1) insertion/deletion at known positions, no large contiguous memory required.
优点：动态大小，无未用槽造成的内存浪费，在已知位置O(1)高效插入/删除，无需大量连续内存。
Cons: extra memory for pointers, O(n) search and indexed access, poor cache locality leading to slower performance in practice, and more complex pointer management.
缺点：额外的指针内存，O(n)搜索和索引访问，缓存局部性差导致实际性能较慢，以及更复杂的指针管理。
11. Implementation and Pseudocode (OCR Exam Focus) | 实现与伪代码（OCR考试重点）
OCR pseudocode uses pointer-like variables and defined records. A node record typically contains a data field and a ‘next’ pointer.
OCR伪代码使用类似指针的变量和定义的记录。节点记录通常包含一个数据字段和一个’next’指针。
Defining a node and creating an empty list:
定义节点并创建空链表：
RECORD Node
data : STRING
next : ^Node
ENDRECORD
DECLARE head : ^Node
head ← NULLThe caret (^) denotes a pointer to a Node. Setting head to NULL initialises an empty list.
尖帽号(^)表示指向Node的指针。将head设为NULL初始化空链表。
Inserting a node at the start (adding “Alice”):
在开头插入节点（添加”Alice”）：
DECLARE newNode : ^Node
newNode ← NEW Node
newNode.data ← "Alice"
newNode.next ← head
head ← newNodeThis demonstrates the pointer update sequence. NEW Node dynamically allocates memory for a node.
这演示了指针更新顺序。NEW Node为节点动态分配内存。
Traversal to output all data can be written as shown earlier; always check for NULL. The exam may ask you to write or trace such pseudocode.
遍历输出所有数据可按前文所示编写；务必检查NULL。考试可能要求你编写或追踪此类伪代码。
12. Common Mistakes in Exams | 考试中的常见错误
Forgetting to update the head pointer after front insertion or deletion leads to a dangling reference or lost data.
在前端插入或删除后忘记更新头指针，会导致悬空引用或丢失数据。
Losing the link to the rest of the list when changing pointers. Always save the old next before overwriting, e.g., temp = prev.next; prev.next = newNode; newNode.next = temp.
更改指针时丢失与列表其余部分的链接。在覆盖前务必保存旧的next，例如：temp = prev.next; prev.next = newNode; newNode.next = temp。
Treating NULL as 0 or an empty string; in OCR pseudocode, NULL is a distinct pointer value meaning ‘no node’.
将NULL当作0或空字符串；在OCR伪代码中，NULL是一个独特的指针值，意为’无节点’。
Not handling the empty-list scenario, causing a null pointer dereference if you try to access head.data or head.next.
未处理空链表场景，若尝试访问head.data或head.next会导致空指针解引用。
Confusing singly and doubly linked list operations, especially when questions ask about backtracking or tail optimisation.
混淆单向和双向链表的操作，尤其是当问题涉及回溯或尾部优化时。
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