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

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

Linked lists are a fundamental data structure in computer science and a key topic in the CIE GCSE Computer Science syllabus. Understanding how linked lists work, their advantages, and their operations is essential for both the theory and programming components of the exam. This article provides a thorough revision of linked lists, including node structure, traversal, insertion, deletion, and comparison with arrays.

链表是计算机科学中的基础数据结构，也是 CIE GCSE 计算机科学教学大纲中的重点内容。理解链表的工作原理、优点及操作对考试的理论和编程部分都至关重要。本文将全面复习链表，涵盖节点结构、遍历、插入、删除以及与数组的比较。

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

A linked list is a dynamic data structure consisting of a sequence of nodes. Each node stores a piece of data and a pointer to the next node in the list. The start of the list is marked by a special pointer called the ‘start’ or ‘head’ pointer. The last node points to a null value (often represented as NULL or None), indicating the end of the list.

链表是一种动态数据结构，由一系列节点组成。每个节点存储一个数据项和一个指向列表中下一个节点的指针。列表的开头由一个特殊的指针（称为“起始”或“头”指针）标记。最后一个节点指向空值（通常表示为 NULL 或 None），指示列表的结尾。

Because nodes can be stored anywhere in memory and linked together by pointers, linked lists can easily grow or shrink during program execution without the need to pre-allocate a fixed amount of memory.

由于节点可以存储在内存中的任何位置并通过指针链接在一起，链表在程序执行期间可以轻松增长或收缩，无需预先分配固定大小的内存。

2. Nodes and Pointers | 节点与指针

A typical node in a singly linked list has two fields: a data field (which holds the actual value, e.g., an integer or string) and a next field (which holds a reference to the next node). The diagram below represents a simple linked list storing the numbers 5, 12, 9:

单链表中的典型节点有两个字段：数据字段（保存实际值，例如整数或字符串）和 next 字段（保存对下一个节点的引用）。下图展示了一个简单的链表，存储数字 5、12、9：

[start] -> [5|next] -> [12|next] -> [9|NULL]

In this notation, each [data|next] is a node. The start pointer points to the first node with data 5. The node with 5 points to the node with 12, and so on. The last node has NULL in its next field, meaning there is no further node.

在此表示中，每个 [数据|next] 是一个节点。起始指针指向数据为 5 的第一个节点。数据为 5 的节点指向数据为 12 的节点，依此类推。最后一个节点的 next 字段为 NULL，表示没有后续节点。

The pointer itself is simply the memory address of the next node. In an exam, you may be asked to draw such diagrams to illustrate insertions or deletions.

指针本身就是下一个节点的内存地址。在考试中，你可能需要绘制此类图来说明插入或删除操作。

3. Types of Linked Lists | 链表的类型

The most basic type examined at GCSE is the singly linked list, where each node has one pointer to the next node. However, it is useful to be aware of variations: doubly linked lists (each node has a pointer to both the next and the previous node) and circular linked lists (the last node points back to the first node). For CIE GCSE, focus on singly linked lists.

GCSE 考试中最基本的类型是单链表，其中每个节点有一个指向下一个节点的指针。但了解变体也有帮助：双链表（每个节点有指向下一个和前一个节点的指针）和循环链表（最后一个节点指回第一个节点）。对于 CIE GCSE，重点应放在单链表上。

Singly linked lists can only be traversed in one direction, from the head to the tail. This limitation affects operations like deletion and searching.

单链表只能沿一个方向（从头到尾）遍历。这一限制影响了删除和搜索等操作。

4. Linked Lists vs Arrays | 链表与数组的比较

Comparing linked lists and arrays is a common exam requirement. Both are used to store collections of data, but they differ significantly in memory usage, access speed, and insertion/deletion efficiency.

链表与数组的比较是常见的考题。两者都用于存储数据集合，但在内存使用、访问速度和插入/删除效率方面存在显著差异。