📚 IGCSE Edexcel Computer Science: Linked Lists Revision | IGCSE Edexcel 计算机：链表 考点精讲
A linked list is a dynamic data structure used to store an ordered sequence of items. Unlike arrays, the elements in a linked list are not stored contiguously in memory; instead, each element (called a node) points to the next one. This fundamental concept appears frequently in IGCSE Edexcel Computer Science, and a strong grasp of it is essential for both the written paper and the programming project. In this revision guide, we will break down the structure, types, operations, and exam relevance of linked lists step by step.
链表是一种动态数据结构，用于存储有序的元素序列。与数组不同，链表中的元素并不是连续存储在内存中的；每个元素（称为节点）都指向下一个元素。这一基本概念在 IGCSE Edexcel 计算机科学考试中频繁出现，无论是在书面试卷还是编程项目中，透彻掌握链表都至关重要。在本复习指南中，我们将逐步拆解链表的结构、类型、操作及其考试相关性。
1. Introduction to Linked Lists | 链表简介
A linked list is a collection of nodes where each node contains data and a reference (or pointer) to the next node in the sequence. The entry point is the 'head' pointer, which holds the address of the first node. The last node points to a null value (often represented as NULL, None, or 0), indicating the end of the list. This structure allows the list to grow and shrink during program execution by allocating memory for new nodes as needed.
链表是一个节点集合，每个节点包含数据和一个指向序列中下一个节点的引用（即指针）。整个链表的入口是 'head' 指针，它保存着第一个节点的地址。最后一个节点指向空值（通常用 NULL、None 或 0 表示），标志着链表的结束。这种结构允许在程序运行时根据需要为新节点分配内存，从而动态地增加或缩减列表长度。
2. Nodes and Pointers | 节点与指针
Each node is typically a record or object consisting of at least two fields: a data field, which stores the actual value, and a pointer field, which stores the memory address of the next node. In a diagram, a node is often drawn as a box divided into two parts: one labelled 'Data' and the other labelled 'Next'. The pointer is represented by an arrow leading to the next node. Understanding this abstract representation is critical for answering diagram-based questions on the IGCSE exam.
每个节点通常是一个记录或对象，至少包含两个域：数据域存储实际的值，指针域存储下一个节点的内存地址。在示意图中，节点常被画成一个分成两部分的方框：一部分标记为 'Data'，另一部分标记为 'Next'。指针用一个指向下一个节点的箭头来表示。理解这种抽象表示对于回答 IGCSE 考试中的图示题至关重要。
3. Singly Linked Lists | 单向链表
The simplest form is the singly linked list, where each node holds a single pointer to the next node. Traversal can only proceed in one direction — from the head to the tail. To insert or delete a node, we must modify the pointer of the preceding node. Because there is no backward link, you cannot easily go back to the previous node without restarting from the head. Singly linked lists are memory efficient but limited in flexibility.
最简单的形式是单向链表，其中每个节点只持有一个指向下一个节点的指针。遍历只能沿一个方向进行——从头节点到尾节点。要插入或删除节点，我们必须修改前驱节点的指针。由于没有反向链接，如果不从头重新开始，就无法轻松地回到上一个节点。单向链表内存效率高，但灵活性有限。
4. Doubly Linked Lists | 双向链表
A doubly linked list adds a second pointer field to each node: one points to the next node, and the other points to the previous node. This allows bidirectional traversal and easier deletion of a node, because you can access the predecessor directly. However, each node requires extra memory to store the additional pointer. In the exam, you may be asked to compare the memory overhead and traversal efficiency of singly and doubly linked lists.
双向链表为每个节点增加了第二个指针域：一个指向后一个节点，另一个指向前一个节点。这样就可以进行双向遍历，并且更容易删除节点，因为可以直接访问前驱节点。但是，每个节点需要额外的内存来存储额外的指针。考试中可能会要求你比较单向链表和双向链表的内存开销与遍历效率。
5. Circular Linked Lists | 循环链表
In a circular linked list, the last node's pointer does not point to null; instead, it points back to the first node (the head), forming a loop. Both singly and doubly linked lists can be made circular. Circular linked lists are useful in applications that repeatedly cycle through a set of data, such as round‑robin scheduling or a playlist that loops. The IGCSE specification often expects you to recognise the benefit of not needing a special case for the last node when traversing.
在循环链表中，最后一个节点的指针不指向空，而是指回第一个节点（头节点），形成一个环。单向和双向链表都可以做成循环链表。循环链表在需要反复循环处理一组数据的应用中很有用，例如轮转调度或循环播放的播放列表。IGCSE 大纲通常希望你能认识到，在遍历时不需要为最后一个节点做特殊处理的好处。
6. Inserting a Node | 插入节点
Inserting a node into a linked list involves three main steps: creating the new node, updating pointers to include the node, and adjusting the head pointer if necessary. The exact procedure depends on the position — at the beginning, in the middle, or at the end. The pointer of the node that will precede the new node must be redirected to the new node, and the new node's pointer must point to the node that followed the preceding node originally. If no pointer is lost before reassignment, the list remains intact.
在链表中插入节点主要包括三个步骤：创建新节点，更新指针以纳入该节点，并在必要时调整头指针。具体过程取决于插入位置 — 在开头、在中间或在末尾。必须将要作为新节点前驱的节点的指针重定向到新节点，同时新节点的指针必须指向原本紧跟前驱的那个节点。如果在重新赋值前没有丢失任何指针，链表就能保持完整。
7. Deleting a Node | 删除节点
Deleting a node requires finding the node to be removed and its predecessor. In a singly linked list, we must traverse from the head to locate the predecessor. Once found, the predecessor's 'next' pointer is updated to bypass the target node and point directly to the node after it. The memory occupied by the deleted node may then be freed. Exam questions frequently ask you to describe this pointer update or to spot errors in a given deletion algorithm.
删除节点需要找到要移除的节点及其前驱节点。在单向链表中，我们必须从头开始遍历以定位前驱节点。找到后，前驱节点的 'next' 指针会被更新以绕过目标节点，直接指向目标节点后面的节点。然后可以释放被删除节点占用的内存。考试题经常要求你描述这种指针更新，或在给定的删除算法中找出错误。
8. Traversing a Linked List | 遍历链表
Traversal is the process of visiting each node in sequence, usually starting from the head. A typical algorithm uses a temporary pointer variable set to the head. Inside a loop, the current node's data is processed, and then the pointer is moved to the next node by following the 'next' pointer. The loop continues until the pointer becomes null. Traversal is used for displaying all elements, summing values, or searching for a specific item.
遍历是按顺序访问每个节点的过程，通常从头节点开始。典型算法使用一个临时指针变量，将其设为头节点。在循环内，处理当前节点的数据，然后沿着 'next' 指针将指针移动到下一个节点。循环持续进行，直到指针变为空值。遍历可用于显示所有元素、求和或查找特定项。
9. Searching in a Linked List | 链表的查找
Searching is a special case of traversal where we look for a node containing a target value. We start at the head and compare each node's data with the target. If a match is found, the search can stop and return the node or its position. If the end of the list is reached without finding the target, the search returns a 'not found' indication. Because linked lists do not support random access, searching has a time complexity of O(n) in the worst case.
查找是遍历的一种特殊情况，我们要寻找包含目标值的节点。从头节点开始，依次比较每个节点的数据与目标值。如果找到匹配项，查找就可以停止并返回该节点或其位置。如果到达链表末尾仍未找到目标值，则返回 '未找到' 的指示。由于链表不支持随机访问，最坏情况下的查找时间复杂度为 O(n)。
10. Advantages and Disadvantages | 优缺点
Linked lists offer dynamic memory allocation, so they can grow without a predefined size limit, and insertion/deletion operations are efficient as they only require pointer updates, without shifting elements. However, they use extra memory for pointers, cannot perform binary search efficiently, and accessing an element by index requires sequential traversal. The exam expects you to discuss these trade-offs in context, such as when choosing between an array and a linked list for a particular scenario.
链表提供动态内存分配，因此可以在没有预定义大小限制的情况下增长，而且插入/删除操作只需要更新指针，无需移动元素，因而效率很高。然而，链表需要额外的内存来存储指针，无法高效地执行二分查找，并且按索引访问元素需要顺序遍历。考试要求你在具体情境中讨论这些权衡，比如在为特定场景选择数组还是链表时。
11. Linked Lists vs Arrays | 链表与数组的比较
The IGCSE Edexcel syllabus often asks you to contrast linked lists and arrays. Key points include:
- Memory: Arrays use contiguous memory; linked lists do not.
- Size: Arrays are usually fixed (static) or require resizing; linked lists are dynamic.
- Access: Arrays provide direct (random) access via index; linked lists require sequential access.
- Insertion/Deletion: Faster in linked lists if the position is known; arrays may need to shift elements.
- Overhead: Linked lists need extra storage for pointers.
IGCSE Edexcel 大纲常要求对比链表和数组。关键点包括：
- 内存：数组使用连续内存；链表不使用。
- 大小：数组通常是固定（静态）的，或需要调整大小；链表是动态的。
- 访问：数组通过索引提供直接（随机）访问；链表需要顺序访问。
- 插入/删除：如果已知位置，链表中的操作更快；数组可能需要移动元素。
- 开销：链表需要额外的存储空间来存放指针。
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
When drawing linked list diagrams, label the head pointer clearly, use arrows to show pointers, and mark the null pointer for the last node. In trace table questions, carefully follow pointer updates one step at a time to avoid losing track of which node is referenced. A common mistake is forgetting to update the head pointer when inserting or deleting at the beginning, or allowing a 'dangling pointer' — a pointer that references a node that has been removed. Practice writing pseudocode for traversal and node insertion, as Edexcel often includes algorithm questions that require you to understand pointer manipulation without a specific programming language.
在绘制链表示意图时，要清楚地标记头指针，用箭头表示指针，并标记末尾节点的空指针。在跟踪表题目中，一步一步仔细跟踪指针的更新，以避免搞不清当前引用的是哪个节点。一个常见错误是，在开头插入或删除时忘记更新头指针，或者留下 '悬空指针' — 一个指向已移除节点的指针。多练习遍历和节点插入的伪代码，因为 Edexcel 经常出算法题，要求你理解指针操作，而不依赖于特定的编程语言。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图