📚 IGCSE CIE Computer Science Linked Lists Explained | IGCSE CIE 计算机：链表 考点精讲
A linked list is a dynamic data structure that stores a collection of nodes, each containing data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory allocation, making them highly flexible for insertion and deletion operations. For IGCSE CIE Computer Science, mastering the structure, manipulation, and comparison of linked lists with arrays is essential. This article breaks down every key concept, from node anatomy to traversal algorithms, to help you achieve top marks in both theory and paper‑based coding questions.
链表是一种动态数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表不需要连续的内存空间，因此在插入和删除操作上非常灵活。在 IGCSE CIE 计算机科学考试中，掌握链表的结构、操作方法以及链表与数组的对比至关重要。本文逐一解析节点结构、遍历算法等核心考点，帮助你在理论和代码题中斩获高分。
1. What Is a Linked List? | 什么是链表？
A linked list is a linear data structure where each element (called a node) is stored separately and connected via pointers. The list starts with a head pointer pointing to the first node. The last node points to null (or None) indicating the end. This dynamic nature allows the list to grow or shrink without wasting memory or needing shifts.
链表是一种线性数据结构，其中的每个元素（称为节点）独立存储，并通过指针连接。链表由一个指向第一个节点的头指针起始，最后一个节点的指针为空（或 None）表示结束。这种动态特性使链表可以按需增长或收缩，不会造成内存浪费或元素移动。
- Nodes are not stored contiguously – they can be scattered in memory.
- 节点不连续存放——它们在内存中可分散存在。
- Each node contains at least two fields: data and a pointer to the next node.
- 每个节点至少包含两个字段：数据域和指向下一节点的指针。
- The list can only be accessed sequentially, starting from the head.
- 链表只能从头指针开始顺序访问。
2. Node Structure and Pointer Fields | 节点结构与指针字段
A typical node in a singly linked list has two components: a data field holding the actual value and a link field storing the address (reference) to the next node. In programming, we often represent this as a record or class with attributes ‘data’ and ‘next’. Some implementations also include a previous pointer for doubly linked lists.
单链表中典型的节点包含两部分：存放实际数据的数据域，以及存储指向下一节点地址（引用）的指针域。在编程中，我们常用具有 ‘data’ 和 ‘next’ 属性的记录或类来表示。对于双向链表，还会额外包含指向前一个节点的指针。
| Field | Description |
|---|---|
| data | Holds the value (integer, string, etc.) |
| next | Pointer/reference to the next node, or null |
| previous (optional) | Only in doubly linked lists; points to the preceding node |
| 字段 | 描述 |
|---|---|
| data | 存放数据值（整数、字符串等） |
| next | 指向下一节点的指针/引用，或为空 |
| previous（可选） | 仅双向链表；指向前一个节点 |
3. Types of Linked Lists | 链表的类型
Three main variants appear in the IGCSE syllabus: singly linked list (each node points to the next), doubly linked list (each node points to both next and previous), and circular linked list (last node points back to the head). Each type offers different traversal directions and use cases.
IGCSE 考纲中主要涉及三种变体：单向链表（每个节点指向下一节点）、双向链表（每个节点同时指向下一节点和上一节点）和循环链表（尾节点指回头节点）。不同类型的链表在遍历方向和适用场景上有所差异。
- Singly linked: efficient forward traversal, less memory overhead.
- 单向链表：高效前向遍历，内存开销较小。
- Doubly linked: supports backward and forward traversal, easier deletion but needs more memory.
- 双向链表：支持向前和向后遍历，删除操作更便捷，但需要更多内存。
- Circular: either singly or doubly, where the last node points to the first, forming a loop; useful for round‑robin scheduling.
- 循环链表：可为单向或双向，尾节点指向头节点形成环；常用于轮转调度。
4. Creating and Representing a Linked List | 创建与表示链表
We need a head pointer (usually called ‘start’ or ‘head’) that points to the first node. If the list is empty, the head pointer is null. Nodes are created dynamically; you might see diagrams with boxes representing nodes and arrows for pointers. In pseudocode, a node is declared as a record type with fields defined.
我们需要一个头指针（通常命名为 ‘start’ 或 ‘head’）指向第一个节点。若链表为空，则头指针为 null。节点是动态创建的；考试中常见用方框表示节点、箭头表示指针的示意图。在伪代码中，节点被声明为带有定义字段的记录类型。
For example, a singly linked list containing 5, 12, 8 would be visualised as: [5|next] → [12|next] → [8|null].
例如，一个包含 5, 12, 8 的单向链表可表示为：[5|next] → [12|next] → [8|null]。
5. Traversing a Linked List | 遍历链表
Traversal is the process of visiting each node in order. Starting from the head, we follow the next pointers until we reach null. A typical loop structure uses a current pointer that moves through the list. Traversal is necessary for searching, displaying, or counting elements.
遍历是指按顺序访问每一个节点的过程。从头指针开始，沿着 next 指针移动，直到遇到 null。典型的循环结构会使用一个 current 指针在链表中移动。遍历是搜索、显示或统计元素个数的基础操作。
Algorithm: set a pointer ptr to head; while ptr ≠ null, process ptr.data, then ptr ← ptr.next.
算法：将指针 ptr 指向头节点；当 ptr ≠ null 时，处理 ptr.data，然后 ptr ← ptr.next。
Time complexity: O(n) – equivalent to the number of nodes.
时间复杂度：O(n)——与节点数量成正比。
6. Inserting a Node into a Linked List | 在链表中插入节点
Insertion can occur at the beginning, end, or a specific position. Because nodes are not indexed by position, we must manipulate pointers carefully to maintain the chain. The three common cases are:
插入可以在链表头、链表尾或指定位置进行。由于链表节点没有位置索引，我们必须小心操作指针以保持链的完整性。常见的三种情况为：
- Insert at head: new node’s next ← head; head ← new node.
- 在头部插入：新节点的 next ← head；head ← 新节点。
- Insert at tail: traverse to last node; set its next ← new node; new node.next ← null.
- 在尾部插入：遍历到最后一个节点；将其 next ← 新节点；新节点.next ← null。
- Insert after a given node: new node.next ← target node.next; target node.next ← new node.
- 在指定节点后插入：新节点.next ← 目标节点.next；目标节点.next ← 新节点。
All insertions have O(1) time for the actual pointer changes once the position is located; locating the position may require O(n).
一旦确定位置，插入操作本身的指针修改时间为 O(1)；但定位可能需要 O(n)。
7. Deleting a Node from a Linked List | 从链表中删除节点
Deletion requires updating the pointer of the previous node so that it skips the node to be removed. The deleted node should be freed from memory. Three scenarios:
删除操作需要更新前一个节点的指针，使其绕过待删除节点。被删除的节点应从内存中释放。三种场景：
- Delete head: head ← head.next (and discard old head).
- 删除头节点：head ← head.next（并丢弃旧的头节点）。
- Delete tail: traverse to the second‑last node and set its next to null.
- 删除尾节点：遍历至倒数第二个节点，将其 next 设为 null。
- Delete a middle node: find the node before the target; set its next ← target.next.
- 删除中间节点：找到目标节点的前一个节点；将其 next ← target.next。
Again, pointer changes are O(1) after finding the node; locating it is O(n).
同样，找到节点后指针修改为 O(1)；定位节点为 O(n)。
8. Linked Lists vs Arrays | 链表与数组的对比
This comparison is a favourite in CIE exams. The key differences lie in memory allocation, access speed, insertion/deletion efficiency, and flexibility.
链表与数组的对比是 CIE 考试中的常见考点。它们的核心区别体现在内存分配、访问速度、插入/删除效率以及灵活性上。
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous, fixed size (static) or dynamic | Non‑contiguous, dynamic size |
| Access | Random, O(1) via index | Sequential, O(n) |
| Insert/Delete | O(n) due to shifting elements | O(1) once position is found |
| Memory overhead | No extra pointers | Extra pointer(s) per node |
| Cache performance | Better (locality) | Poorer (scattered) |
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续，固定大小（静态）或动态 | 非连续，动态大小 |
| 访问方式 | 随机访问，通过索引 O(1) | 顺序访问，O(n) |
| 插入/删除 | 需移动元素，O(n) | 找到位置后 O(1) |
| 内存开销 | 无额外指针 | 每个节点需存指针 |
| 缓存性能 | 更好（局部性） | 较差（不连续） |
Choose arrays when you need fast random access and memory is not a constraint; choose linked lists when frequent insertions/deletions occur and size changes dynamically.
需要快速随机访问且内存不成问题时，选择数组；需要频繁插入/删除且大小动态变化时，选择链表。
9. Implementing a Linked List in Pseudocode | 伪代码实现链表
CIE exams often ask you to write pseudocode for linked list operations. You must declare node types, initialise head pointer, and write procedures for insert, delete, and traverse. Pay attention to pointer updates and null checks.
CIE 考试经常要求考生写出链表操作的伪代码。你需要声明节点类型，初始化头指针，并编写插入、删除、遍历等过程的伪代码。注意指针更新和 null 检查。
Example node declaration:
示例节点声明：
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // pointer reference
ENDTYPE
Then for insertion at head:
然后头部插入：
PROCEDURE InsertAtHead(BYREF head : INTEGER, newData : INTEGER)
DECLARE newNode : INTEGER
newNode ← AllocateNode()
newNode.Data ← newData
newNode.Next ← head
head ← newNode
ENDPROCEDURE
Ensure you demonstrate thorough understanding of parameter passing (BYREF/BYVAL).
确保你充分理解参数传递（BYREF/BYVAL）的用法。
10. Doubly Linked Lists and Their Advantages | 双向链表及其优势
A doubly linked list includes an extra pointer ‘prev’ (previous) in each node. This allows traversal in both directions and simplifies deletion of a node when only a reference to that node is given (no need to find the previous node separately). However, it consumes more memory and requires more pointer updates during insertion/deletion.
双向链表在每节点中增加一个指向前一个节点的 ‘prev’ 指针。这使得可以双向遍历，并且在给定节点引用时可直接删除（无需单独寻找前驱节点）。但它会消耗更多内存，且在插入/删除时需要更新更多指针。
Example insertion for a doubly linked list after a given node ‘p’:
双向链表中在指定节点 p 之后插入的示例：
newNode.Next ← p.Next
IF p.Next ≠ null THEN
p.Next.Prev ← newNode
ENDIF
p.Next ← newNode
newNode.Prev ← p
Recognise that CIE may present diagrams and ask for code or explanation of such updates.
请留意，CIE 考试可能给出示意图，要求你写出相应的代码或解释指针更新。
11. Common Exam Pitfalls and Tips | 常见考试陷阱与高分技巧
Students often lose marks by missing null pointer checks, forgetting to update head/tail pointers in edge cases, or confusing the order of pointer assignments. Always handle empty list, single‑node list, and end‑of‑list cases explicitly. When writing pseudocode, use clear variable names and consistent indentation.
考生常因遗漏空指针检查、忘记在边界情况更新头/尾指针、或混淆指针赋值顺序而丢分。务必显式处理空链表、单节点链表以及链表末尾的情况。编写伪代码时，要使用清晰的变量名并保持一致的缩进。
- Edge cases: empty list (head is null), list with exactly one node, inserting/deleting at head or tail.
- 边界情况：空链表（head 为 null）、仅有一个节点的链表、在头或尾的插入/删除。
- Pointer order: when inserting, always set the new node’s next pointer before modifying the previous node’s next, otherwise you may lose the rest of the list.
- 指针顺序：插入时，务必先设置新节点的 next 指针，再修改前驱节点的 next，否则可能丢失剩余部分。
- Memory management: mention that deleted nodes should be ‘freed’ or returned to available storage.
- 内存管理：应提及被删除的节点需要“释放”或归还到可用存储区。
12. Practice Questions and Concept Checks | 练习题与概念检测
To solidify your understanding, attempt the following typical CIE‑style questions:
为巩固理解，请尝试以下典型的 CIE 风格问题：
- Draw a diagram for a singly linked list storing [23, 17, 9] and show the result after inserting 15 at the head.
- 画出存储 [23, 17, 9] 的单链表示意图，并展示在头部插入 15 后的结果。
- Write pseudocode to delete the first occurrence of a given value from a singly linked list.
- 编写伪代码，从单链表中删除第一个值为给定值的节点。
- Explain why a doubly linked list is preferred for implementing an undo feature in a text editor.
- 解释为什么在文本编辑器中实现撤销功能时，双向链表更受青睐。
- Compare the performance of accessing the 50th element in an array vs a linked list, justifying your answer with Big O notation.
- 比较访问数组和链表中第 50 个元素的性能，并用大 O 记号说明理由。
Working through these will expose any gaps in your pointer logic or conceptual understanding, so you can address them before the exam.
通过练习这些问题，你将暴露在指针逻辑或概念理解上的任何漏洞，从而在考前及时弥补。
Published by TutorHao | IGCSE CIE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导