📚 GCSE Computer Science: Linked Lists Revision Guide | GCSE 计算机：链表考点精讲
A linked list is a fundamental dynamic data structure widely examined in GCSE Computer Science. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element — called a node — is stored separately and linked to the next via a pointer. This unique arrangement brings both advantages and trade-offs, particularly when it comes to inserting, deleting, and traversing data. Understanding how linked lists work, how they differ from arrays, and how to manipulate them is essential for top marks in your exam. In this revision guide, we will walk through every key concept, from node structure to traversal algorithms, from singly linked to doubly linked and circular lists, and we will compare them with arrays using clear tables and examples.
链表是 GCSE 计算机科学考试中重点考查的基础动态数据结构。与数组不同，链表不会将元素存储在连续的内存空间中，而是将每个元素（称为节点）分开存放，并通过指针连接到下一个节点。这种独特的结构在数据的插入、删除和遍历方面带来了明显的优势和取舍。掌握链表的工作原理、它与数组的区别以及如何操作链表，是取得高分的关键。在本考点精讲中，我们将梳理每一个核心概念，涵盖节点结构、遍历算法、单向链表、双向链表、循环链表，并使用清晰的表格和示例将它们与数组进行比较。
1. What is a Linked List? | 什么是链表？
A linked list is a sequence of nodes where each node contains a piece of data and a link (or pointer) to the next node in the sequence. The list itself is accessed through a head pointer, which points to the first node. Because the nodes are not stored next to each other in memory, the list can grow or shrink dynamically without needing to shift elements — a key advantage over arrays. The last node in a standard singly linked list stores a null reference (often written as NULL or None) to indicate the end of the list.
链表是由一系列节点组成的序列，每个节点包含一个数据部分和一个指向序列中下一个节点的链接（即指针）。整个链表通过一个头指针访问，该指针指向第一个节点。由于节点在内存中并非相邻存放，链表可以动态增长或收缩，无需像数组那样移动元素——这是它的一大优势。在标准的单向链表中，最后一个节点存放空引用（通常写成 NULL 或 None）以表明链表的结束。
2. Node Structure | 节点结构
Every node in a linked list consists of at least two fields: a data field, which stores the actual value (an integer, string, or any object), and a next field, which stores the memory address of the following node. In a doubly linked list, an additional prev field stores the address of the previous node. Think of a node as a container with one or two arrows pointing to its neighbours. The pointer fields are what make the list ‘linked’ — they hold the data structure together. When a node is created, its pointer is usually initialised to null before being connected.
链表中的每个节点至少包含两个域：数据域，用于存放实际的值（整数、字符串或任何对象），以及 下一个 域，用于存放下一个节点的内存地址。在双向链表中，还会有一个额外的 前一个 域存放上一个节点的地址。可以把节点想象成一个带有单箭头或双箭头指向邻居的容器。正是这些指针域使链表“链接”了起来，它们把整个数据结构维系在一起。创建节点时，其指针通常先被初始化为空，再与其他节点建立连接。
3. Singly Linked Lists | 单向链表
A singly linked list is the simplest form. Each node only stores a reference to the next node. The head of the list is the entry point; from the head you can follow the next pointers to visit every node in order. The final node’s next pointer equals null. Insertion and deletion require updating the next pointer of the preceding node. Because there is no backward link, traversing in reverse is impossible without extra data structures, which makes certain operations slightly more complex. For the GCSE, you need to be comfortable drawing diagram-style representations of singly linked lists and stepping through node modifications.
单向链表是最简单的形式。每个节点只存储指向下一个节点的引用。链表的头是访问的入口；从头部开始，可以沿着 下一个 指针依次访问每一个节点。末尾节点的 下一个 指针为 null。插入和删除操作需要更新前驱节点的 下一个 指针。由于没有反向链接，若无额外数据结构就无法反向遍历，这使某些操作略显复杂。在 GCSE 考试中，你应能熟练绘制单向链表的示意图，并逐步推演节点的修改过程。
4. Doubly Linked Lists | 双向链表
A doubly linked list extends the singly linked list by giving each node both a prev reference and a next reference. This allows traversal in both directions, from head to tail and from tail to head. The head node’s prev pointer is null, and the tail node’s next pointer is null. Inserting or deleting a node now requires updating two pointers in the neighbouring nodes, which adds a bit of work but makes operations like deleting a node when only given a pointer to it much easier — you can immediately access its predecessor. Exam questions often ask you to compare the memory overhead and complexity of operations between singly and doubly linked lists.
双向链表在单向链表的基础上为每个节点同时提供了一个 前一个 引用和一个 下一个 引用。这样就能从前后两个方向遍历链表，既可以从头到尾，也可以从尾到头。头节点的 前一个 指针为空，尾节点的 下一个 指针为空。此时插入或删除节点需要更新相邻节点的两个指针，工作量稍微增加，但使得“仅给出某个节点指针时删除该节点”这类操作变得十分简单——你可以立即访问到它的前驱。考试题常常要求你比较单向链表与双向链表在内存开销和操作复杂度上的差异。
5. Circular Linked Lists | 循环链表
In a circular linked list, the last node’s next pointer points back to the first node, forming a ring. A circular singly linked list has no node with a null next pointer; a circular doubly linked list additionally makes the head’s prev point to the tail. Circular lists are particularly useful in applications that repeat a cycle, such as round-robin scheduling or looping playlists. To detect the end when traversing, you must store the starting node address and stop when you encounter it again. When implementing queues or buffers, a circular structure can be very memory-efficient because you never need to reset pointers to null when removing the last element.
在循环链表中，最后一个节点的 下一个 指针指回头节点，形成一个环。单向循环链表中不存在 下一个 指针为空的节点；双向循环链表还会让头节点的 前一个 指向尾节点。循环链表特别适合需要反复循环的应用场景，例如循环调度算法或循环播放列表。遍历时为了探测结束，必须保存起始节点的地址，当再次遇到该地址时停止。在实现队列或缓冲区时，循环结构可以非常节省内存，因为删除最后一个元素后也无需将指针重设为 null。
6. Traversing a Linked List | 遍历链表
Traversal is the process of visiting each node in the linked list, typically starting from the head. In a singly linked list, you follow a simple loop: initialise a current pointer to head, then while current is not null, process the data at current, and move current to current.next. This algorithm runs in O(n) time because each node is visited once. Random access is not supported — you cannot jump to the fifth element without stepping through the first four. Traversal forms the basis of all other operations, including searching, counting, and printing the list contents. You may be asked to write pseudocode for traversal in your GCSE exam, so be comfortable using while loops and null checks.
遍历是指访问链表中的每一个节点，通常从头节点开始。在单向链表中，遵循一个简单的循环：将当前指针初始化为指向头部，然后当 当前 不为空时，处理当前节点的数据，再将 当前 移动到 当前.下一个。该算法的时间复杂度为 O(n)，因为每个节点只被访问一次。链表不支持随机访问——如果不经过前四个节点，就无法直接跳到第五个节点。遍历是所有其他操作的基础，包括搜索、计数和打印链表内容。GCSE 考试可能会要求你写出遍历的伪代码，因此请熟练掌握 while 循环和空判断的写法。
7. Inserting a Node | 插入节点
Insertion in a linked list involves changing the next (and possibly prev) pointers of surrounding nodes so that the new node fits into the sequence. There are three main cases: inserting at the head, inserting at the tail, and inserting in the middle.
在链表中插入节点需要修改周围节点的 下一个（可能还有 前一个）指针，使新节点融入序列。主要有三种情况：在头部插入、在尾部插入以及在中间插入。
To insert at the head of a singly linked list: set the new node’s next to the current head, then update the head pointer to point to the new node. This is an O(1) operation. Inserting at the tail requires traversing the entire list to find the last node, then setting its next to the new node and leaving the new node’s next as null. For doubly linked lists, you must also set the new node’s prev pointer and update the prev pointer of the original node (if it exists).
在单向链表头部插入时：将新节点的 下一个 设为当前头节点，然后把头指针更新为指向新节点。这是一个 O(1) 操作。在尾部插入则需要遍历整个链表找到最后一个节点，然后将其 下一个 设为新节点，同时新节点的 下一个 保持为空。对于双向链表，还必须设置新节点的 前一个 指针，并更新原节点的 前一个 指针（如果存在）。
Inserting in the middle after a given node: set the new node’s next to the given node’s next, then update the given node’s next to point to the new node. For doubly linked lists, you then need to adjust the prev pointer of the node that now follows the new node. Always ensure you do not lose the link to the rest of the list; the order of pointer updates matters — if you change the predecessor’s next too early, you might lose the reference to the rest of the chain.
在给定节点之后插入：将新节点的 下一个 设为给定节点的 下一个，然后将给定节点的 下一个 更新为指向新节点。对于双向链表，随后还需调整新节点之后节点的 前一个 指针。务必注意不要丢失指向链表其余部分的链接；指针更新的顺序至关重要——如果过早修改前驱节点的 下一个，就可能丢失对链表中后续部分的引用。
8. Deleting a Node | 删除节点
Deletion also has three common scenarios: removing the head, removing the tail, and removing a node from the middle. In a singly linked list, to remove a node after a known predecessor, simply set the predecessor’s next to the node to be deleted’s next. The removed node is then typically freed from memory (in languages that require manual memory management). If you need to delete the head, just update the head pointer to head.next. Deleting the tail requires traversing to the second-last node and setting its next to null. For doubly linked lists, you must also update the prev pointer of the node that follows the deleted node, and if deleting the head, ensure the new head’s prev is set to null. Exam questions often test whether you correctly set pointers to avoid dangling references or memory leaks.
删除操作同样有三种常见情形：删除头部、删除尾部以及从中间删除某个节点。在单向链表中，如果要删除已知前驱节点之后的那个节点，只需将前驱节点的 下一个 设为被删除节点的 下一个。通常随后会将被删除节点从内存中释放（对于需要手动内存管理的语言）。如果需要删除头部，只需将头指针更新为 头部.下一个。删除尾部则需要遍历至倒数第二个节点，并将其 下一个 设为 null。对于双向链表，还必须更新被删除节点之后节点的 前一个 指针；如果删除的是头部，需确保新头节点的 前一个 设为 null。考试题目经常考查你是否正确设置了指针，以避免出现悬空引用或内存泄漏。
9. Linked Lists vs Arrays | 链表与数组的比较
Understanding the trade-offs between linked lists and arrays is a core GCSE topic. Below is a summary table that directly compares key properties. Use this to answer compare-and-contrast questions confidently.
理解链表和数组之间的权衡是 GCSE 的核心考点。下面的总结表格直接比较关键特性，帮助你自信地回答对比分析类题目。
| Property 属性 | Linked List 链表 | Array 数组 |
|---|---|---|
| Memory allocation 内存分配 |
Dynamic, nodes scattered in memory 动态，节点分散在内存中 |
Static or dynamic, but contiguous block 静态或动态，但为连续内存块 |
| Size flexibility 大小弹性 |
Can grow and shrink easily at runtime 可在运行时轻松增长和缩小 |
Size fixed at creation (static) or resizing is costly 创建时固定大小（静态）或扩容代价高 |
| Random access 随机访问 |
Not supported; O(n) to access an element 不支持；访问元素为 O(n) |
Direct access via index; O(1) 通过索引直接访问；O(1) |
| Insert/delete at head 头部插入/删除 |
O(1) – only pointer updates needed O(1) – 只需更新指针 |
O(n) – must shift all elements O(n) – 必须移动所有元素 |
| Insert/delete in middle 中间插入/删除 |
O(n) to find position + O(1) to change pointers 查找位置 O(n) + 修改指针 O(1) |
O(n) – shifting required O(n) – 需要移动元素 |
| Extra memory overhead 额外内存开销 |
Yes – stores pointer(s) per node 有 – 每个节点存储指针 |
No pointers, but may waste pre-allocated space 无指针，但可能浪费预分配空间 |
| Cache performance 缓存性能 |
Poor – nodes not contiguous, cache misses 较差 – 节点不连续，缓存不命中 |
Good – spatial locality, cache-friendly 较好 – 空间局部性好，缓存友好 |
When answering exam questions, always relate these properties to the specific scenario. If an application needs many insertions and deletions, linked lists shine. If it requires fast index-based lookup, arrays are the better choice.
在回答考试问题时，务必将这些特性与具体场景结合起来。如果应用需要大量插入和删除操作，链表表现出色；如果需要快速的索引查询，数组则是更好的选择。
10. Applications of Linked Lists | 链表的应用
Linked lists are not just theoretical; they underpin many real-world data structures. They are used to implement stacks and queues dynamically, where push and pop operations work on the head of a singly linked list. A music playlist that allows moving to the next or previous track is a classic example of a doubly linked list. Web browser history (back and forward navigation) frequently uses a doubly linked list structure. Operating systems use circular linked lists to manage process scheduling. Even memory management systems sometimes use free lists built on linked nodes to track available blocks. Understanding these applications helps you see why the dynamic nature and easy insertion/deletion of linked lists are so valuable.
链表并非只存在于理论中，它们是许多现实世界数据结构的基础。链表可用于动态实现栈和队列，此时压入和弹出操作作用于单向链表的头部。允许切换到上一首或下一首的音乐播放列表就是双向链表的典型例子。网页浏览器的历史记录（后退和前进导航）通常也采用双向链表结构。操作系统使用循环链表管理进程调度。甚至内存管理系统有时也会利用基于链表节点的空闲列表来跟踪可用块。理解这些应用能帮助你明白为什么链表的动态性和便捷的插入/删除功能如此宝贵。
11. Key Terms Summary | 关键术语总结
Here is a quick glossary of essential linked-list vocabulary you must know for the GCSE examination.
以下是 GCSE 考试中必须掌握的链表核心术语速查表。
| Term 术语 | Definition 定义 |
|---|---|
| Node 节点 | A container holding data and one or more pointers to other nodes 包含数据和一个或多个指向其他节点的指针的容器 |
| Head pointer 头指针 | A reference that points to the first node of the list; loss of it loses the entire list 指向链表第一个节点的引用；丢失它会导致整个链表丢失 |
| Next pointer 下一个指针 |
A pointer in each node that stores the address of the following node 每个节点中存储后续节点地址的指针 |
| Prev pointer 前一个指针 |
A pointer in doubly linked nodes that stores the address of the previous node 双向链表节点中存储前一个节点地址的指针 |
| Null / NULL 空值 |
A special value indicating the end of the list (no more nodes) 表示链表结尾的特殊值（不再有后续节点） |
| Singly linked 单向链接 |
A list where each node points only to the next node 每个节点只指向下一个节点的链表 |
| Doubly linked 双向链接 |
A list where each node points both to the next and the previous node 每个节点同时指向下一个和前一个节点的链表 |
| Circular linked 循环链接 |
A list where the last node points back to the first node, forming a loop 最后一个节点指回第一个节点、形成环的链表 |
12. Exam Tips | 考试技巧
When tackling linked-list questions in your GCSE, always draw a simple diagram before writing code or pseudocode. Use boxes for nodes and arrows for pointers — this visual aid prevents most pointer-related mistakes. Remember to handle special cases such as an empty list (head is null) or a single-node list, because pointer updates in these situations are often different. Practice writing pseudocode for traversing, inserting, and deleting using a consistent variable naming style (e.g., current, previous, newNode). In comparison questions, always support your arguments with concrete advantages and disadvantages backed by Big O notation or memory reasoning. Finally, double-check that you haven’t inadvertently lost the head pointer after an operation — losing the head makes the entire list unreachable, which is a common exam pitfall.
在 GCSE 考试中处理链表题目时，务必在编写代码或伪代码之前先画出简单的示意图。用方框表示节点、用箭头表示指针——这种直观辅助可以避免大多数与指针有关的错误。记住要处理特殊情况，例如空链表（头指针为空）或单节点链表，因为这些情况下指针更新往往与常规情况不同。练习使用统一的变量命名风格（如 current、previous、newNode）来编写遍历、插入和删除的伪代码。在比较类题目中，始终用具体的优点和缺点支撑你的论点，并辅以 Big O 表示法或内存层面的推理。最后，反复检查是否在操作后无意中丢失了头指针——丢失头指针会导致整个链表无法访问，这是常见的考试失分点。
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