Mastering Linked Lists for IGCSE Computer Science | IGCSE 计算机：链表考点精讲

📚 Mastering Linked Lists for IGCSE Computer Science | IGCSE 计算机：链表考点精讲

Linked lists are one of the fundamental data structures you will encounter in IGCSE Computer Science. Unlike arrays, which store data in contiguous memory locations, linked lists use nodes that are connected by pointers. Understanding how linked lists work, their advantages, and their limitations is essential for solving algorithmic problems and writing efficient programs. This article provides a comprehensive exam-focused guide to linked lists, covering core concepts, operations, comparisons with arrays, and typical IGCSE-style questions.

链表是IGCSE计算机科学中会遇到的基础数据结构之一。与将数据存储在连续内存位置的数组不同，链表使用由指针连接的节点。理解链表的工作原理、优点和局限性对于解决算法问题及编写高效程序至关重要。本文提供一份全面的、以考试为导向的链表指南，涵盖核心概念、操作、与数组的对比以及典型的IGCSE风格问题。

1. What is a Linked List? | 什么是链表？

A linked list is a dynamic data structure that consists of a sequence of nodes. Each node contains data and a pointer (or reference) to the next node in the sequence. The first node is called the head, and the last node points to null (or a special terminator), marking the end of the list. Because nodes are not stored in adjacent memory locations, linked lists can grow and shrink during program execution without the need to pre-allocate a fixed amount of memory.

链表是一种动态数据结构，由一系列节点组成。每个节点包含数据和一个指向序列中下一个节点的指针（或引用）。第一个节点称为头节点，最后一个节点指向空（或特殊终止符），标记列表的结束。由于节点不是存储在相邻的内存位置，链表可以在程序执行期间增长和收缩，无需预先分配固定数量的内存。

2. Structure of a Node | 节点的结构

A node typically contains two parts: a data field (which stores the actual value) and a next pointer (which stores the address of the following node). In a singly linked list, each node has a single pointer. For example, if a node stores the integer 17, its data field would be 17, and its next field would contain the memory address of the node holding 42 (or null if it is the last node). This arrangement allows sequential access from the head to any node.

节点通常包含两个部分：数据域（存储实际值）和下一个指针（存储后续节点的地址）。在单向链表中，每个节点只有一个指针。例如，如果一个节点存储整数17，其数据域就是17，其next域将包含存储42节点的内存地址（如果是最后一个节点则为空）。这种安排允许从头节点顺序访问任何节点。

3. Types of Linked Lists: Singly, Doubly, Circular | 链表的类型：单向、双向、循环

There are three main types of linked lists. A singly linked list has nodes with only one pointer, pointing forward. A doubly linked list has two pointers per node: one pointing to the next node and one to the previous node, allowing traversal in both directions. A circular linked list is a variation where the last node points back to the first node, forming a loop. IGCSE exams mainly focus on singly linked lists, but you should be aware of the others.

链表主要有三种类型。单向链表中的节点只有一个指针，指向前方。双向链表每个节点有两个指针：一个指向下一个节点，一个指向前一个节点，允许双向遍历。循环链表是一种变体，最后一个节点指回第一个节点，形成闭环。IGCSE考试主要关注单向链表，但你也应该了解其他类型。

4. Traversing a Linked List | 遍历链表

Traversal means visiting each node in the linked list one by one, starting from the head. You use a temporary pointer (often called current) to move through the list. At each step, you process the data, and then update current = current.next. The traversal stops when current becomes null. This process is used to search for an element, count nodes, or display the list. Time complexity for traversal is O(n), where n is the number of nodes.

遍历是指从头节点开始，逐个访问链表中的每个节点。使用一个临时指针（通常称为current）在列表中移动。每一步处理数据，然后更新current = current.next。当current变为空时遍历停止。此过程用于搜索元素、计数节点或显示列表。遍历的时间复杂度为O(n)，其中n是节点数。

5. Insertion Operations | 插入操作

Inserting a node into a linked list is efficient because it only requires updating a few pointers, without shifting elements. To insert at the beginning: set the new node’s next pointer to the current head, then update the head to point to the new node. To insert at the end: traverse to the last node and set its next pointer to the new node. Inserting in the middle requires finding the node after which you want to insert, then adjusting pointers accordingly. In all cases, the complexity is O(1) if the position is known, though finding the position takes O(n).

在链表中插入节点非常高效，因为只需更新少量指针，无需移动元素。在开头插入：将新节点的next指针指向当前头节点，然后更新头节点指向新节点。在末尾插入：遍历到最后一个节点，将其next指针指向新节点。在中间插入需要找到要插入位置的前一个节点，然后相应地调整指针。在所有情况下，如果位置已知，复杂度为O(1)，尽管查找位置需要O(n)。

6. Deletion Operations | 删除操作

Deleting a node also requires pointer adjustments. To delete the first node: simply move the head pointer to the second node. To delete the last node: traverse to the second-last node and set its next pointer to null. To delete a node in the middle: locate the node before the one to be deleted, and change its next pointer to skip the target node and point to the node after it. In languages with automatic garbage collection, the deleted node is freed; otherwise, you must explicitly free the memory.

删除节点同样需要指针调整。删除第一个节点：只需将头指针移动到第二个节点。删除最后一个节点：遍历到倒数第二个节点，将其next指针设为空。删除中间节点：找到待删除节点的前一个节点，修改其next指针跳过目标节点，指向其后一个节点。在有自动垃圾回收的语言中，被删节点会被释放；否则必须显式释放内存。

7. Linked Lists vs Arrays | 链表与数组对比

Arrays offer random access (O(1)) via indices, while linked lists only allow sequential access. However, inserting or deleting an element in an array requires shifting all subsequent elements (O(n)), whereas linked lists can perform these operations in O(1) once the position is found. Arrays have a fixed size (static) or require resizing (dynamic), while linked lists use memory only when needed. Memory overhead: arrays store only data, linked lists store data plus pointer(s). Choose arrays for frequent read operations; choose linked lists for frequent insertions/deletions.

数组通过索引提供随机访问（O(1)），而链表只允许顺序访问。然而，在数组中插入或删除元素需要移动所有后续元素（O(n)），而链表一旦找到位置可以在O(1)内完成这些操作。数组大小固定（静态）或需要调整大小（动态），而链表仅在需要时使用内存。内存开销：数组只存储数据，链表存储数据加指针。频繁读操作选择数组；频繁插入/删除选择链表。

8. Implementing a Singly Linked List in Pseudocode | 单向链表的伪代码实现

IGCSE exams often ask you to write pseudocode for basic linked list operations. Below is a typical structure for adding a node at the start:

IGCSE考试经常要求你为基本链表操作编写伪代码。下面是一个在开头添加节点的典型结构：

PROCEDURE InsertAtHead(BYREF head, data)
CREATE newNode
newNode.data ← data
newNode.next ← head
head ← newNode
ENDPROCEDURE

You should also be able to write traversal and search routines, managing the head pointer carefully. Avoid losing references to the rest of the list when updating pointers—always store the next node before breaking a link.

你还应该能够编写遍历和搜索例程，谨慎管理头指针。在更新指针时，避免丢失列表其余部分的引用——总是在断开链接之前存储下一个节点。

9. Common IGCSE Exam Traps | 常见IGCSE考试陷阱

One common mistake is confusing the order of pointer updates. For example, when inserting at the head, if you set head to newNode before linking newNode.next to the old head, you lose the old list. Another trap is forgetting that the last node’s next pointer should be null; not setting null leads to undefined behavior. Also, when deleting a node, ensure you don’t leave a ‘dangling’ pointer. Pay attention to edge cases: empty list, single-node list, inserting/deleting at the beginning or end.

一个常见错误是混淆指针更新的顺序。例如，在头部插入时，如果在将newNode.next链接到旧头节点之前就将head设置为newNode，会丢失旧列表。另一个陷阱是忘记最后一个节点的next指针应为空；不设为空会导致未定义行为。此外，删除节点时，确保不要留下“悬空”指针。注意边界情况：空链表、单节点链表、在开头或末尾插入/删除。

10. Applications of Linked Lists | 链表的应用

Linked lists are used in implementing stacks, queues, and graphs. They form the basis of dynamic memory allocation and are useful in music playlist management (next/previous song), undo functionality in software, and representing sparse matrices. In operating systems, linked lists help manage process queues. Knowing real-world applications helps you understand why these structures matter in computer science.

链表用于实现栈、队列和图。它们是动态内存分配的基础，也用于音乐播放列表管理（上一首/下一首）、软件中的撤销功能以及稀疏矩阵的表示。在操作系统中，链表帮助管理进程队列。了解实际应用有助于你理解这些结构在计算机科学中的重要性。

11. IGCSE-Style Questions and Answers | IGCSE风格问答

Question: “State one advantage of a linked list over an array.” Answer: A linked list can grow or shrink dynamically; inserting or deleting elements does not require shifting data. Question: “Explain why accessing the 5th element is slower in a linked list.” Answer: Because you must start from the head and follow the pointers sequentially; there is no direct index access. Practice drawing diagrams of pointer changes during insertion and deletion to visualize the steps.

问题：“说明链表相对于数组的一个优点。”答案：链表可以动态增长或收缩；插入或删除元素不需要移动数据。问题：“解释为什么访问链表中第5个元素更慢。”答案：因为必须从头开始顺序跟随指针；没有直接的索引访问。练习绘制插入和删除过程中指针变化的示意图，以可视化步骤。

12. Summary of Key Exam Points | 考试要点总结

For IGCSE success, remember these core concepts: a linked list node contains data and a next pointer; the head points to the first node; traversal is O(n); insertion and deletion at the head are O(1); arrays are better for random access, linked lists for dynamic changes. Be able to write simple pseudocode, trace pointer updates, and compare linked lists with arrays in terms of memory, speed, and flexibility.

要在IGCSE中取得成功，请记住这些核心概念：链表节点包含数据和next指针；head指向第一个节点；遍历为O(n)；在头部插入和删除为O(1)；数组更适合随机访问，链表更适合动态变化。能够编写简单的伪代码，追踪指针更新，并从内存、速度和灵活性方面比较链表与数组。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Mastering Linked Lists for IGCSE Computer Science | IGCSE 计算机：链表 考点精讲