📚 IGCSE AQA Computer Science: Linked Lists – Key Points | IGCSE AQA 计算机：链表 考点精讲
A linked list is a fundamental dynamic data structure that every IGCSE Computer Science student must understand. Unlike arrays, linked lists consist of nodes connected by pointers, allowing flexible memory usage and efficient insertions and deletions. In this revision guide, we cover all essential concepts, operations, and exam tips for the AQA IGCSE specification.
链表是每位 IGCSE 计算机学生必须掌握的基础动态数据结构。与数组不同，链表由通过指针连接的节点组成，能够灵活使用内存并高效地进行插入和删除操作。本复习指南涵盖 AQA IGCSE 考纲中的所有核心概念、操作以及考试技巧。
1. What is a Linked List? | 什么是链表？
A linked list is a linear collection of data elements, called nodes, where the order is not given by their physical placement in memory. Each node points to the next node by storing a reference (or pointer). The list starts with a head pointer and ends with a node whose pointer is null (or nil), indicating the end of the list.
链表是一种线性的数据元素集合，称为节点，其顺序不由它们在内存中的物理位置决定。每个节点通过存储引用（或指针）指向下一个节点。链表以头指针开始，以指针为空（或 nil）的节点结束，表示表尾。
2. Node Structure | 节点结构
Each node in a linked list typically contains two parts: data (the actual value) and a pointer (the address of the next node). For singly linked lists, only one pointer is used. The node can be visualised as [ data | next ] →.
链表中的每个节点通常包含两部分：数据（实际值）和指针（下一个节点的地址）。对于单向链表，只使用一个指针。节点可以可视化为 [ 数据 | 下一个 ] →。
3. Types of Linked Lists | 链表的类型
The three main types of linked lists are: singly linked list (each node has one pointer to the next node), doubly linked list (nodes have pointers to both next and previous nodes), and circular linked list (the last node points back to the first node, forming a circle).
链表的三种主要类型是：单向链表（每个节点有一个指向下一个节点的指针），双向链表（节点同时具有指向前一个和后一个节点的指针），以及循环链表（最后一个节点指回第一个节点，形成一个环）。
4. Singly vs Doubly vs Circular | 单、双、循环链表对比
Singly linked lists are memory efficient but can only be traversed in one direction. Doubly linked lists allow two‑way traversal but use more memory per node. Circular linked lists make operations like round‑robin scheduling easy, as there is no “end” to check.
单向链表内存效率高，但只能单向遍历。双向链表允许双向遍历，但每个节点占用更多内存。循环链表使得循环调度等操作变得简单，因为无需检查“末端”。
- Singly: head → node1 → node2 → null | 单向：头 → 节点1 → 节点2 → 空
- Doubly: head ↔ node1 ↔ node2 ↔ null | 双向：头 ↔ 节点1 ↔ 节点2 ↔ 空
- Circular: head → node1 → node2 → (back to head) | 循环：头 → 节点1 → 节点2 → (回到头)
5. Linked Lists vs Arrays | 链表与数组的对比
Understanding the differences between linked lists and arrays is crucial for choosing the right data structure. Below is a comparison of key aspects.
理解链表与数组之间的差别对于选择合适的数据结构至关重要。以下是对关键方面的比较。
| Aspect | Array | Linked List |
|---|---|---|
| Memory allocation | Static (fixed size) | Dynamic (grows/shrinks) |
| Access to elements | Random access (index) | Sequential access only |
| Insertion/Deletion | Slow (shifting elements) | Fast (change pointers) |
| Memory overhead | None (contiguous block) | Extra pointer per node |
| Cache performance | Better (locality) | Poor (scattered memory) |
6. Traversal of a Linked List | 链表的遍历
Traversal means visiting each node in the list, usually starting from the head and following the next pointers until null is reached. In pseudocode: set a variable current = head, then while current is not null, process the data and move current = current.next.
遍历是指访问链表中的每个节点，通常从头节点开始，沿着 next 指针移动直到空值。伪代码：设变量 current = head，然后当 current 不为空时，处理数据并将 current = current.next。
7. Inserting a Node | 插入节点
To insert a node at the beginning of a singly linked list, set the new node’s next pointer to the current head, then update head to the new node. For insertion at the end or middle, we first traverse to the appropriate position, then adjust pointers accordingly. The time complexity is O(1) at the head and O(n) elsewhere.
要在单向链表的开头插入节点，将新节点的 next 指针设为当前头节点，然后将头指针更新为新节点。对于在尾部或中间插入，首先遍历到合适的位置，然后相应地调整指针。头部插入的时间复杂度为 O(1)，其他位置为 O(n)。
8. Deleting a Node | 删除节点
To delete a node from the beginning, simply move the head pointer to the next node. For a node in the middle, we find the previous node and change its next pointer to skip the node to be deleted. Memory of the deleted node should be freed (in languages without automatic garbage collection). Time complexity: O(1) at head, O(n) for others.
要从开头删除节点，只需将头指针移动到下一个节点。对于中间的节点，找到前驱节点，然后将其 next 指针改为指向要删除节点的下一个，从而跳过该节点。被删除节点的内存应当释放（在没有自动垃圾回收的语言中）。时间复杂度：头部 O(1)，其他位置 O(n)。
9. Advantages and Disadvantages | 优点与缺点
Advantages include dynamic size, efficient insertions/deletions, and easy implementation of stacks and queues. Disadvantages are additional memory for pointers, no direct access, and poorer cache performance due to non‑contiguous memory.
优点包括动态大小、高效的插入和删除，以及易于实现栈和队列。缺点是指针需要额外内存、无法直接存取，以及由于非连续内存导致的缓存性能较差。
10. Applications of Linked Lists | 链表的应用
Linked lists are used in implementing data structures like stacks, queues, graphs (adjacency lists), music playlists, undo options in software, and dynamic memory allocation. They are especially useful when the number of elements changes frequently.
链表用于实现栈、队列、图（邻接表）、音乐播放列表、软件中的撤销选项以及动态内存分配等数据结构。当元素数量频繁变化时，链表特别有用。
11. Exam Tips | 考试技巧
In AQA IGCSE exams, you may be asked to draw diagrams of linked list operations, complete tracing exercises, or compare linked lists with arrays. Always label the head pointer and NULL clearly. When writing pseudocode, use clear variable names like head, current, newNode. Check that you do not lose references when rearranging pointers.
在 AQA IGCSE 考试中，你可能会被要求绘制链表操作的示意图、完成追踪练习，或比较链表与数组。务必清晰地标出 head 指针和 NULL。编写伪代码时，使用清晰的变量名，如 head、current、newNode。重新排列指针时注意不要丢失引用。
12. Summary | 总结
Linked lists are a core dynamic data structure in computer science. They trade direct access for flexibility, allowing efficient modifications. Mastering node structure, traversal, insertion, and deletion will equip you to handle many exam questions confidently.
链表是计算机科学中核心的动态数据结构。它们以牺牲直接访问为代价换来了灵活性，使得修改操作更加高效。掌握节点结构、遍历、插入和删除将使你能够自信地应对许多考试题目。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导