IGCSE WJEC Computer Science: Linked Lists Exam Focus | IGCSE WJEC 计算机：链表考点精讲

📚 IGCSE WJEC Computer Science: Linked Lists Exam Focus | IGCSE WJEC 计算机：链表考点精讲

Linked lists are a fundamental dynamic data structure in computer science, and they feature prominently in the IGCSE WJEC Computer Science specification. Unlike static arrays, linked lists consist of nodes that can be stored anywhere in memory, connected by pointers. This article provides a thorough breakdown of linked list concepts, operations, and exam-focused insights to help you master this topic for your IGCSE WJEC examination.

链表是计算机科学中一种基本的动态数据结构，在 IGCSE WJEC 计算机科学考试大纲中占有重要地位。与静态数组不同，链表由可以存储在内存任意位置的节点组成，通过指针相互连接。本文将深入剖析链表的概念、操作方法以及考试重点，帮助你完全掌握这一主题，以应对 IGCSE WJEC 考试。

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

A linked list is a collection of elements called nodes, arranged in a linear order. Each node contains two parts: the data value and a pointer (or link) to the next node in the sequence. The first node is called the head, and the last node points to null (or none), indicating the end of the list. Linked lists are dynamic, meaning they can grow or shrink during program execution without the need to pre-allocate memory, unlike arrays.

链表是一组被称为节点的元素，按线性顺序排列。每个节点包含两部分：数据值以及指向序列中下一个节点的指针（或称链接）。第一个节点称为头节点，最后一个节点指向 null（或空），表示链表结束。链表是动态的，这意味着它们可以在程序执行过程中动态增长或收缩，而无需像数组那样预先分配内存。

2. Anatomy of a Node and Pointers | 节点的结构与指针

A node is the building block of any linked list. In a singly linked list, a typical node stores two fields: data (the actual value, such as an integer or string) and next (a pointer holding the memory address of the following node). If we imagine each node as a box, the arrow connecting boxes is the pointer. In programming pseudocode used in WJEC, nodes are often represented as objects with attributes like data and nextPtr.

节点是任何链表的构建块。在单向链表中，典型的节点存储两个字段：data（实际值，如整数或字符串）和 next（一个指针，保存下一个节点的内存地址）。如果把每个节点想象成一个盒子，连接盒子的箭头就是指针。在 WJEC 使用的伪代码中，节点通常被表示为具有 data 和 nextPtr 等属性的对象。

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

Understanding when to use a linked list over an array is a common exam requirement. Arrays are static, fixed-size structures that allow constant-time access to any element via indexing, but inserting or deleting elements (especially at the beginning) can be costly because all subsequent elements must be shifted. Linked lists, on the other hand, allocate memory dynamically for each node, making insertion and deletion efficient (O(1) time complexity if the position is known), but do not support direct indexing – you must traverse from the head to reach a particular position (O(n) search time). The table below summarises the key differences.

理解何时使用链表而非数组是常见的考试要求。数组是静态的、大小固定的结构，允许通过索引以常数时间访问任意元素，但插入或删除元素（特别是在开头处）代价很高，因为所有后续元素都必须移动。另一方面，链表为每个节点动态分配内存，从而使得插入和删除操作高效（若已知位置，时间复杂度为 O(1)），但不支持直接索引——你必须从头遍历才能到达特定位置（搜索时间为 O(n)）。下表总结了主要区别。

Feature	Array	Linked List
Memory allocation	Static (fixed size)	Dynamic (grows/shrinks at runtime)
Element access	Direct (indexing O(1))	Sequential (traversal O(n))
Insertion/Deletion	Inefficient (shifting required O(n))	Efficient (pointer update O(1) at known position)
Memory usage	May waste space if oversized	Extra memory for pointers

特征： 内存分配：数组静态（固定大小）；链表动态（运行时增长/收缩）。元素访问：数组直接访问（索引 O(1)）；链表顺序访问（遍历 O(n)）。插入/删除：数组效率低（需移动元素 O(n)）；链表效率高（在已知位置更新指针 O(1)）。内存使用：数组若过大可能浪费空间；链表需要额外的指针内存。

4. Singly Linked Lists | 单向链表

A singly linked list is the simplest form. Each node has exactly one link pointing to the next node. Traversal can only be performed in a forward direction, from head to tail. This makes operations like printing all elements straightforward: start at head, follow the next pointers until null is reached. The lack of a backward link means that deleting a node requires keeping track of the previous node during traversal.

单向链表是最简单的形式。每个节点只有一个指向下一个节点的链接。遍历只能向前进行，从头到尾。这使得像打印所有元素这样的操作很直接：从头节点开始，沿着 next 指针移动直到遇到 null。由于缺少反向链接，删除节点时需要在遍历过程中跟踪前一个节点。

5. Doubly Linked Lists | 双向链表

A doubly linked list expands the node structure by adding a second pointer, prev (or left), which points to the previous node. This allows traversal in both directions – forward and backward. The extra pointer makes reverse traversal trivial and simplifies deletion operations because you can access the predecessor directly without traversing from the start. However, it consumes more memory per node. In WJEC questions, you might be asked to compare singly and doubly linked lists or to trace operations in a doubly linked list.

双向链表通过增加第二个指针 prev（或 left）来扩展节点结构，该指针指向前一个节点。这使得可以在两个方向上遍历——向前和向后。额外的指针使反向遍历变得简单，并简化了删除操作，因为你可以直接访问前驱节点而无需从头遍历。然而，每个节点消耗的内存更多。在 WJEC 考试题中，你可能会被要求比较单向和双向链表，或者在双向链表中追踪操作。

6. Circular Linked Lists | 循环链表

In a circular linked list, the last node’s pointer does not point to null; instead, it points back to the head, forming a loop. Circular lists can be singly or doubly linked. This structure is useful for applications that require continuous cycling through a list, such as a round-robin scheduler or a multiplayer game turn system. Traversal must be carefully handled to avoid infinite loops: stop when you return to the starting node.

在循环链表中，最后一个节点的指针并不指向 null，而是指回头节点，形成一个环。循环链表可以是单向或双向的。这种结构对于需要连续循环遍历列表的应用非常有用，例如轮转调度器或多人游戏中的回合系统。遍历时必须小心处理，以避免无限循环：当返回到起始节点时停止。

7. Traversing a Linked List | 遍历链表

Traversal is the process of visiting each node in sequence. A typical traversal algorithm uses a temporary pointer (often called current) initialised to the head. While current is not null, the data of the current node is processed, and then current is updated to current.next. For doubly linked lists, traversal can also move backwards starting from the tail. Traversal is a linear (O(n)) operation and is the basis for searching, counting, and outputting all elements.

遍历是按顺序访问每个节点的过程。典型的遍历算法使用一个临时指针（通常称为 current），初始化为头节点。当 current 不为空时，处理当前节点的数据，然后将 current 更新为 current.next。对于双向链表，遍历也可以从尾节点开始向后移动。遍历是一种线性（O(n)）操作，是搜索、计数和输出所有元素的基础。

procedure traverse(head)
   current ← head
   while current != null
      output current.data
      current ← current.next
   endwhile
endprocedure

伪代码示例：从 head 开始，循环输出数据并移动到下一个节点。

8. Insertion Operations | 插入操作

Insertion is where linked lists shine. Adding a node at the beginning requires creating a new node, setting its next pointer to the current head, and updating the head reference to the new node. Insertion at the end involves traversing to the last node (whose next is null) and pointing its next to the new node. Inserting in the middle requires locating the node after which the insertion is to occur, then reassigning pointers: new node’s next becomes current node’s next, and current node’s next becomes the new node. The order of pointer reassignment is critical to avoid breaking links.

插入操作是链表大显身手的地方。在开头添加节点需要创建一个新节点，将其 next 指针设置为当前头节点，然后将 head 引用更新为新节点。在末尾插入需要遍历到最后一个节点（其 next 为 null），然后将其 next 指向新节点。在中间插入需要定位要在其后插入的节点，然后重新分配指针：新节点的 next 成为当前节点的 next，当前节点的 next 变为新节点。指针重新赋值的顺序至关重要，以避免断开链接。

procedure insertAtStart(head, data)
   newNode ← createNode(data)
   newNode.next ← head
   head ← newNode
   return head
endprocedure

在开头插入的伪代码：创建节点，连接新节点到旧头，更新头。

9. Deletion Operations | 删除操作

Deletion also benefits from the linked structure. To delete the first node, simply set head to head.next (and free the old head in languages with manual memory management). Deleting a node from the middle or end requires access to the node immediately preceding the target. In a singly linked list, you must traverse to find that previous node, then set its next to bypass the node being deleted. In a doubly linked list, the previous node is directly accessible via the prev pointer, making deletion simpler and faster. After updating pointers, the removed node can be discarded.

删除操作也受益于链表结构。要删除第一个节点，只需将 head 设置为 head.next（并在需要进行手动内存管理的语言中释放旧头）。从中间或末尾删除节点需要访问紧邻目标节点之前的节点。在单向链表中，你必须遍历找到前一个节点，然后将其 next 设置为绕过要删除的节点。在双向链表中，前一个节点可以通过 prev 指针直接访问，从而使删除操作更简单、更快速。更新指针后，移除的节点即可被丢弃。

procedure deleteTarget(head, target)
   if head.data == target then
      return head.next
   endif
   current ← head
   while current.next != null
      if current.next.data == target then
         current.next ← current.next.next
         break
      endif
      current ← current.next
   endwhile
   return head
endprocedure

删除指定值的伪代码：处理头节点匹配的情况，否则遍历寻找目标节点的前驱，然后更新指针。

10. Memory Management and Implementation Considerations | 内存管理与实现注意事项

When implementing linked lists in languages like Python, memory management is handled automatically by the garbage collector; in languages like C++, you must manually deallocate nodes using delete. In pseudocode for IGCSE WJEC, you are expected to show pointer assignments and occasionally indicate ‘free memory’ after deletion. Another consideration is the ’empty list’ case: if head is null, most operations must be handled separately to avoid errors. Always draw diagrams in exams to visualise pointer changes – this helps prevent mistakes.

在像 Python 这样的语言中实现链表时，内存管理由垃圾回收器自动处理；而在像 C++ 这样的语言中，你必须使用 delete 手动释放节点。在 IGCSE WJEC 的伪代码中，你应该展示指针赋值，并偶尔指出删除后的“释放内存”。另一个考虑因素是“空链表”情况：如果 head 为 null，大多数操作必须单独处理以避免错误。在考试中始终绘制示意图以可视化指针变化——这有助于避免错误。

11. Common Applications of Linked Lists | 链表的常见应用

Linked lists are used to implement other dynamic data structures such as stacks and queues, where efficient insertion and deletion at ends are critical. They are also the backbone of hash tables with chaining, adjacency lists in graph representations, and undo functionality in editors. The WJEC syllabus may ask you to identify suitable use cases for linked lists over arrays, such as situations where the number of elements is unknown at compile time or where frequent insertions/deletions occur at arbitrary positions.

链表用于实现其他动态数据结构，如栈和队列，在这些结构中，在两端进行高效的插入和删除至关重要。它们还是链式哈希表、图表示中的邻接表以及编辑器中的撤销功能的基础。WJEC 大纲可能会要求你识别适合使用链表而非数组的场景，例如在编译时元素数量未知，或经常在任意位置进行插入/删除操作的情况。

12. Exam Tips and Pitfalls | 考试技巧与常见错误

When answering WJEC exam questions on linked lists, always clearly label your nodes, data fields, and pointers (use arrows). Pay close attention to the order of operations when inserting or deleting – a classic mistake is losing the rest of the list by overwriting the head or next pointer too early. Be comfortable tracing given pseudocode and drawing the resulting list. Also, understand the difference between a list and an array well enough to justify your choice in design scenarios. Revision of time complexity (Big O notation) for basic operations can gain you easy marks in comparison questions.

在回答 WJEC 关于链表的考题时，务必要清晰地标出节点、数据字段和指针（使用箭头）。插入或删除时，要特别注意操作顺序——一个典型的错误是由于过早覆写头节点或 next 指针而导致丢失列表的剩余部分。要习惯于追踪给定的伪代码并绘制结果列表。此外，要充分理解列表与数组的区别，以便在设计场景中为你的选择辩护。复习基本操作的时间复杂度（大 O 表示法）可以在对比题中轻松得分。

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

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

IGCSE WJEC Computer Science: Linked Lists Exam Focus | IGCSE WJEC 计算机：链表 考点精讲