📚 Data Structures Revision for A-Level Edexcel Computer Science | A-Level Edexcel 计算机：数据结构 考点精讲
Data structures are fundamental building blocks in computer science, defining how data is organised, stored, and manipulated. For Edexcel A-Level Computer Science, a solid understanding of static and dynamic structures, abstract data types, and their time and space complexity is essential for both the written paper and the programming project. This revision guide presents the core data structures you need to master, explaining their behaviour, typical operations, and practical applications with clarity.
数据结构是计算机科学的基本构建块，定义了数据的组织、存储和操作方式。对于Edexcel A-Level计算机科学考试，牢固掌握静态与动态结构、抽象数据类型及其时间与空间复杂度，对笔试和编程项目都至关重要。本复习指南将为你梳理必须掌握的核心数据结构，清晰地解释它们的行为、典型操作和实际应用。
1. Overview of Data Structures | 数据结构概述
A data structure is a specialised format for organising and storing data so that it can be accessed and modified efficiently. They are broadly classified into linear structures (arrays, linked lists, stacks, queues) and non-linear structures (trees, graphs, hash tables). An Abstract Data Type (ADT) defines a data type purely by its behaviour from the point of view of a user, specifically the operations that can be performed on it and the properties of those operations, without any reference to how it is implemented.
数据结构是一种用于组织和存储数据的专用格式，以便能够高效地访问和修改数据。它们大致分为线性结构（数组、链表、栈、队列）和非线性结构（树、图、哈希表）。抽象数据类型 (ADT) 纯粹从用户的角度，根据其行为（尤其是可对其执行的操作及其属性）来定义数据类型，而不涉及任何实现细节。
2. Arrays and Records | 数组与记录
An array is a static, contiguous block of memory that stores elements of the same data type. Each element is accessed directly by its index, giving O(1) random access. However, inserting or deleting an element in the middle requires shifting subsequent elements, which takes O(n) time. Arrays are typically zero-indexed and their size must be declared in advance, making them a static structure.
数组是一块静态、连续的内存块，用于存储相同数据类型的元素。每个元素可通过索引直接访问，提供 O(1) 的随机访问。但在中间插入或删除元素需要移动后续元素，这需要 O(n) 时间。数组通常从零索引开始，其大小必须预先声明，因此它是一种静态结构。
Multi-dimensional arrays, such as 2D arrays, extend this concept into rows and columns, representing tables or matrices. Accessing an element at row r, column c in a zero-indexed 2D array of C columns uses the formula: address = base + (r × C + c) × element_size. This direct address calculation is possible because the structure is stored contiguously.
多维数组（例如二维数组）将这一概念扩展到行和列，表示表格或矩阵。在零索引的二维数组（有 C 列）中访问第 r 行、第 c 列的元素，使用公式：地址 = 基址 + (r × C + c) × 元素大小。这种直接地址计算之所以可能，是因为该结构是连续存储的。
A record (or struct) is a composite data type that groups together related variables of possibly different types under a single name. Unlike arrays, records are heterogeneous and can store mixed data types. Each variable within a record is called a field. Records are the foundation of object-oriented programming and databases.
记录（或结构体）是一种复合数据类型，将可能不同类型的相关变量组合在一个名称下。与数组不同，记录是异构的，可以存储混合的数据类型。记录中的每个变量称为字段。记录是面向对象编程和数据库的基础。
3. Linked Lists | 链表
A linked list is a dynamic data structure in which each element (node) contains data and a pointer to the next node. It does not require contiguous memory, so it can grow or shrink during execution. The typical operations include inserting a node at the head (O(1)), appending (O(n) if no tail pointer), deleting a node (O(n) to find the predecessor), and traversing (O(n)).
链表是一种动态数据结构，其中每个元素（节点）包含数据和指向下一个节点的指针。它不需要连续的内存，因此可以在执行期间增长或收缩。典型操作包括在头部插入节点 (O(1))、追加（如果没有尾指针则为 O(n)）、删除节点（查找前驱需 O(n)） 和遍历 (O(n))。
In a singly linked list, nodes only point forward. A doubly linked list adds a pointer to the previous node, enabling efficient backward traversal and deletion of a node given only the node itself. However, this consumes extra memory per node. A circular linked list makes the last node point back to the head. When implemented with sentinel nodes, boundary conditions become simpler.
在单向链表中，节点只向前指向。双向链表添加了一个指向前一个节点的指针，从而能够高效地反向遍历，并只需给定节点本身即可删除该节点。但这会消耗每个节点更多的内存。循环链表使最后一个节点指向头节点。使用哨兵节点实现时，边界条件会变得更简单。
4. Stacks | 栈
A stack is a Last-In-First-Out (LIFO) abstract data type. The main operations are push (add an item to the top), pop (remove and return the top item), and peek/top (inspect the top without removal). Underflow occurs when trying to pop from an empty stack, while overflow can happen in a fixed-size array implementation.
栈是一种后进先出 (LIFO) 的抽象数据类型。主要操作包括 push（将一个项添加到栈顶）、pop（移除并返回栈顶项）和 peek/top（不移除地查看栈顶）。当试图从空栈中弹出时，会发生下溢；而在固定大小的数组实现中，则可能发生上溢。
Stacks can be implemented using arrays, where a top pointer tracks the index of the topmost element. Alternatively, a linked list can be used, where pushing corresponds to inserting at the head, and popping corresponds to removing the head. This dynamic implementation avoids overflow. Stacks are used in function call management (call stack), expression evaluation (postfix notation), and undo mechanisms.
栈可以用数组实现，其中栈顶指针跟踪最顶层元素的索引。或者可以使用链表，其中压入对应于在头部插入，弹出对应于移除头部。这种动态实现避免了上溢。栈用于函数调用管理（调用栈）、表达式求值（后缀表示法）和撤销机制。
5. Queues | 队列
A queue is a First-In-First-Out (FIFO) abstract data type. Essential operations are enqueue (add to the rear) and dequeue (remove from the front). A linear queue implemented with an array suffers from the problem of unused space as items are dequeued, which can be solved by a circular queue where the front and rear pointers wrap around.
队列是一种先进先出 (FIFO) 的抽象数据类型。基本操作是 enqueue（添加到队尾）和 dequeue（从队头移除）。用数组实现的线性队列会随着项目出队而出现未使用空间的问题，这可以通过循环队列来解决，其中队头指针和队尾指针会绕回。
In a circular queue, both the front and rear indices move. The queue is full when (rear + 1) % size == front, which wastes one slot to distinguish between full and empty conditions. A linked list implementation uses a head and tail pointer, allowing O(1) enqueue (append to tail) and O(1) dequeue (remove from head). Priority queues are a variation where each element has a priority and the highest-priority element is dequeued first; they are usually implemented with a heap.
在循环队列中，队头和队尾索引都会移动。当 (rear + 1) % 大小 == 队头时，队列为满，这浪费一个空位以区分满和空的状态。链表实现使用头指针和尾指针，允许 O(1) 入队（追加到尾部）和 O(1) 出队（从头部移除）。优先级队列是一种变体，其中每个元素都有优先级，优先级最高的元素最先出队；它们通常用堆来实现。
6. Trees | 树
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges. The topmost node is the root. Each node (except the root) has exactly one parent and can have zero or more children. Connections are directed from parent to child. Nodes with no children are leaf nodes. The depth of a node is the number of edges from the root, while the height is the maximum depth of any node in the tree.
树是一种非线性层次数据结构，由节点通过边连接而成。最顶层的节点是根。每个节点（根除外）恰好有一个父节点，可以有零个或多个子节点。连接从父节点指向子节点。没有子节点的节点是叶节点。节点的深度是从根到该节点的边数，而树的高度是树中任何节点的最大深度。
A binary tree is a tree in which each node has at most two children, referred to as the left child and right child. A full binary tree has every node with either 0 or 2 children. A complete binary tree is filled at all levels except possibly the last, which is filled from left to right. Trees can be represented using nodes with left and right pointers, or in an array for a complete binary tree where the left child of index i is at 2i+1 and right child at 2i+2.
二叉树是一种每个节点最多有两个子节点的树，分别称为左子节点和右子节点。满二叉树中每个节点要么有 0 个子节点，要么有 2 个子节点。完全二叉树除了最后一层外，所有层都是满的，且最后一层从左到右填充。树可以用带有左右指针的节点来表示，对于完全二叉树也可以用数组表示，其中索引 i 的左子节点在 2i+1，右子节点在 2i+2。
7. Binary Search Trees | 二叉搜索树
A Binary Search Tree (BST) is a binary tree with the ordering property: for any node, all values in its left subtree are less than or equal to the node’s value, and all values in its right subtree are greater. This property enables efficient searching, insertion, and deletion, all with average-case time complexity O(log n) if the tree is balanced. In the worst case (a degenerate tree, essentially a linked list), these operations degrade to O(n).
二叉搜索树 (BST) 是一种具有排序性质的二叉树：对于任意节点，其左子树中的所有值都小于或等于该节点的值，而其右子树中的所有值都大于该节点。这一性质使得搜索、插入和删除操作高效，如果树是平衡的，平均时间复杂度为 O(log n)。在最坏情况下（退化树，即基本上是链表），这些操作会降级为 O(n)。
To search for a target value, you compare it with the current node’s value, going left if smaller and right if larger until you find the target or reach a null pointer. Insertion follows a similar path and attaches the new node as a leaf. Deletion is more complex, especially when the node to be deleted has two children: you must find the in-order successor (the smallest node in the right subtree) to replace it and maintain the BST property.
要搜索目标值，将其与当前节点的值进行比较，如果较小则向左走，如果较大则向右走，直到找到目标或到达空指针。插入沿着类似的路径进行，将新节点作为叶子附加。删除更复杂，尤其是要删除的节点有两个子节点时：必须找到中序后继（右子树中的最小节点）来替换它，并维持 BST 的性质。
8. Tree Traversal | 树的遍历
Traversing a tree means visiting each node in a systematic order. The three classic depth-first traversals for a binary tree are pre-order (root, left, right), in-order (left, root, right), and post-order (left, right, root). In-order traversal of a BST yields the nodes in sorted ascending order. Recursive implementations are concise, but these can also be implemented using a stack to avoid recursion depth limits.
遍历一棵树意味着按系统顺序访问每个节点。二叉树的三种经典深度优先遍历是：前序（根、左、右）、中序（左、根、右）和后序（左、右、根）。对 BST 的中序遍历会按升序生成节点。递归实现很简洁，但也可以使用栈来实现，以避免递归深度限制。
Pre-order traversal is useful for creating a copy of a tree or prefix expression notation. Post-order is used for deleting a tree or evaluating postfix expressions in expression trees. Breadth-first traversal (level order) visits nodes level by level from top to bottom, left to right, and is implemented using a queue. Each traversal has O(n) time complexity.
前序遍历对于创建树的副本或前缀表达式表示法很有用。后序遍历用于删除树或在表达式树中计算后缀表达式。广度优先遍历（层序遍历）从上到下、从左到右逐层访问节点，并使用队列实现。每种遍历的时间复杂度都是 O(n)。
9. Hash Tables | 哈希表
A hash table (hash map) stores key-value pairs and provides extremely fast O(1) average-case lookup, insertion, and deletion. It uses a hash function to compute an index (slot) from the key. A good hash function distributes keys uniformly across the available slots to minimise collisions, where two distinct keys map to the same index.
哈希表（散列表）存储键值对，并提供极快的 O(1) 平均情况查找、插入和删除。它使用哈希函数根据键计算索引（槽位）。一个好的哈希函数会将键均匀分布到可用的槽位上，以尽量减少冲突，即两个不同的键映射到同一个索引的情况。
Collision resolution can be handled by separate chaining, where each slot contains a linked list of entries that hash to that index. Alternatively, open addressing uses probing: linear probing (step size 1) or quadratic probing to find the next available slot. When the load factor (number of items / table size) exceeds a threshold, the table is resized and all entries are rehashed into a larger table, an O(n) operation that is amortised over multiple insertions.
冲突解决可以通过分离链接法来处理，其中每个槽位包含一个链表，存放散列到该索引的所有条目。另一种方法是开放寻址法，使用探测：线性探测（步长为 1）或二次探测来寻找下一个可用的槽位。当负载因子（项目数 / 表大小）超过阈值时，表会被重新调整大小，所有条目被重新散列到一个更大的表中，这是一个 O(n) 操作，但通过多次插入可以摊销成本。
10. Graphs | 图
A graph is a set of vertices (or nodes) connected by edges. Edges can be directed (digraph) or undirected, and can have weights (weighted graph). Graphs are used to model networks, social relationships, and routing problems. The degree of a vertex is the number of edges connected to it, with in-degree and out-degree for directed graphs.
图是由边连接的一组顶点（或节点）。边可以是有向的（有向图）或无向的，并且可以具有权重（加权图）。图用于建模网络、社交关系和路由问题。顶点的度是指与其相连的边数，有向图则分为入度和出度。
Two common representations are the adjacency matrix and adjacency list. An adjacency matrix is a 2D array of size V×V, where matrix[i][j] is 1 (or the weight) if an edge exists, and 0 otherwise. This gives O(1) edge existence check but consumes O(V²) memory. An adjacency list stores for each vertex a list of its neighbours; it is more memory-efficient for sparse graphs and allows faster iteration over neighbours. Graph traversal algorithms like breadth-first search (BFS) and depth-first search (DFS) are foundational.
两种常见的表示法是邻接矩阵和邻接表。邻接矩阵是一个大小为 V×V 的二维数组，如果存在边，则 matrix[i][j] 为 1（或权重），否则为 0。这使得边存在性检查为 O(1)，但会消耗 O(V²) 内存。邻接表为每个顶点存储其邻居列表；对于稀疏图更节省内存，并允许更快地遍历邻居。广度优先搜索 (BFS) 和深度优先搜索 (DFS) 等图遍历算法是基础。
11. Choosing the Right Data Structure | 选择合适的数据结构
Selecting the appropriate data structure depends on the operations you need to perform most frequently. The following table summarises the time complexity of common operations for fundamental structures so you can make an informed decision. Keep in mind that these are worst-case times unless noted as average-case.
选择合适的数据结构取决于你最常执行的操作。下表总结了基本结构常见操作的时间复杂度，以便你做出明智的决定。请记住，除非注明为平均情况，否则这些都是最坏情况下的时间。
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Singly Linked List | O(n) | O(n) | O(1) (head) | O(n) |
| Stack (array) | O(1) (top) | O(n) | O(1) | O(1) |
| Queue (circular) | O(1) (front) | O(n) | O(1) | O(1) |
| Binary Search Tree | O(log n) avg | O(log n) avg | O(log n) avg | O(log n) avg |
| Hash Table | N/A | O(1) avg | O(1) avg | O(1) avg |
For example, if you need frequent random access and the size is fixed, an array is best. If you have many insertions and deletions in the middle, a linked list may be preferable. Stacks suit LIFO behaviour, queues for FIFO. Hash tables are ideal for fast key-based lookups, and trees support range queries and ordered traversal.
例如，如果你需要频繁的随机访问且大小固定，数组是最好的选择。如果你有许多在中间进行的插入和删除操作，链表可能更可取。栈适用于 LIFO 行为，队列则适用于 FIFO。哈希表非常适合快速的基于键的查找，而树则支持范围查询和有序遍历。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply