Core Review of Basic Data Structures | 基本数据结构核心梳理

📚 Core Review of Basic Data Structures | 基本数据结构核心梳理

A data structure is a systematic way of organising and storing data in a computer so that it can be accessed and modified efficiently. In A-Level Computer Science, you must be able to describe the characteristics of core data structures, perform operations on them, compare their time complexities, and choose the most appropriate structure for a given problem. This article consolidates the essential knowledge you need for exam success.

数据结构是计算机中系统地组织和存储数据的方式，以便数据能够被高效地访问和修改。在 A-Level 计算机科学中，你不仅需要描述核心数据结构的特点、对它们执行操作、比较时间复杂度，还要能为给定问题选择最合适的结构。本文为你整合了考试所需的核心知识。

1. Classification of Data Structures | 数据结构的分类

Data structures are commonly classified in two ways: linear versus non-linear, and static versus dynamic. Linear structures store elements in a sequence, such as arrays, linked lists, stacks and queues. Non-linear structures organise data hierarchically or in networks, such as trees and graphs. Static structures have a fixed size determined at compile time, while dynamic structures can grow and shrink during program execution.

数据结构通常按两种方式分类：线性与非线性、静态与动态。线性结构按顺序存储元素，例如数组、链表、栈和队列。非线性结构以层次或网络方式组织数据，例如树和图。静态结构的大小在编译时确定，而动态结构可在程序执行期间增长或缩小。

It is also important to distinguish between a data structure and an Abstract Data Type (ADT). A data structure is a concrete implementation in a programming language, whereas an ADT defines the logical behaviour and allowed operations, independent of implementation. For example, a stack is an ADT with the operations push and pop; it can be implemented using either an array or a linked list.

还需要区分数据结构与抽象数据类型（ADT）。数据结构是编程语言中的具体实现，而 ADT 定义逻辑行为和允许的操作，与实现无关。例如，栈是包含 push 和 pop 操作的 ADT，它可以分别用数组或链表实现。

2. Arrays | 数组

An array is a static, linear data structure that stores elements of the same data type in contiguous memory locations. Each element is identified by an index, which typically starts at 0 in most languages. Because the elements are stored contiguously, the address of any element can be calculated directly, giving constant-time random access.

数组是一种静态的线性数据结构，将相同数据类型元素存储在连续的内存单元中。每个元素通过下标标识，大多数语言中下标从 0 开始。由于元素连续存储，任何元素的地址都可以直接计算，因此支持常数时间的随机访问。

The memory address of an array element is calculated using the formula:

address = base_address + index × element_size

For a 2D array stored in row-major order, the address of element arr[i][j] with m columns is given by:

address = base + (i × m + j) × element_size

for a 2D 数组按行优先存储时，arr[i][j] 的地址计算公式为：base + (i × m + j) × element_size。

Advantages: O(1) random access; efficient memory use with no pointer overhead.
优点：O(1) 随机访问；无指针开销，内存利用率高。
Disadvantages: fixed size — cannot be resized at runtime; insertion and deletion require shifting elements, giving O(n) time in the worst case.
缺点：大小固定，运行时无法调整；插入和删除需要移动元素，最坏情况时间复杂度为 O(n)。

3. Linked Lists | 链表

A linked list is a dynamic linear data structure in which each node contains a data field and a pointer to the next node. The first node is referenced by a head pointer, and the last node’s pointer is set to null. Unlike arrays, linked list elements are not stored in contiguous memory, so there is no random access: to reach the k-th node, you must traverse from the head.

链表是一种动态线性数据结构，每个节点包含数据域和指向下一个节点的指针。第一个节点由头指针引用，最后一个节点的指针设为 null。与数组不同，链表元素不存储在连续内存中，因此不支持随机访问：要到达第 k 个节点，必须从头开始遍历。

Insertion at the head: O(1) — only update the head pointer and the new node’s pointer.
在头部插入：O(1)——只需更新头指针和新节点的指针。
Search for a value: O(n) — linear traversal is required.
搜索某个值：O(n)——需要线性遍历。
Memory: each node stores data plus a pointer, so it uses more memory than an array of the same length.
内存：每个节点存储数据和一个指针，因此比同长度的数组占用更多内存。

A doubly linked list adds a second pointer to each node, pointing to the previous node. This allows traversal in both directions and makes deletion of a given node easier, at the cost of an extra pointer per node. In a circular linked list, the last node points back to the first node instead of null.

双向链表为每个节点增加一个指向前驱节点的指针，从而支持双向遍历，并且删除给定节点更加容易，但代价是每个节点多一个指针。在循环链表中，最后一个节点不指向 null，而是指回头节点。

4. Stacks | 栈

A stack is an Abstract Data Type that follows the Last In, First Out (LIFO) principle. Elements are added to the top of the stack and removed from the top of the stack. The core operations are push (add an element), pop (remove and return the top element), peek or top (view the top element without removing it), and isEmpty (check whether the stack contains any elements).

栈是一种遵循后进先出（LIFO）原则的抽象数据类型。元素从栈顶加入，也从栈顶移除。核心操作包括 push（压栈）、pop（弹栈并返回栈顶元素）、peek 或 top（查看栈顶元素而不移除）以及 isEmpty（检查栈是否为空）。

If a push operation is attempted when the stack is full, a stack overflow occurs; if a pop is attempted on an empty stack, a stack underflow occurs. Both conditions must be handled carefully in examinations.

当栈已满时执行 push 会发生栈溢出（overflow）；当栈为空时执行 pop 会发生栈下溢（underflow）。考试中务必小心处理这两种情况。

Typical applications of a stack include: function call stacks in recursion, expression evaluation (converting infix to postfix), backtracking algorithms such as maze solving, and the undo feature in word processors.

栈的典型应用包括：递归中的函数调用栈、表达式求值（中缀转后缀）、迷宫求解等回溯算法，以及文字处理器中的撤销功能。

5. Queues | 队列

A queue is an Abstract Data Type that follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front. The main operations are enqueue (insert at the rear), dequeue (remove from the front), and isEmpty.

队列是一种遵循先进先出（FIFO）原则的抽象数据类型。元素从队尾加入，从队头移除。主要操作包括 enqueue（入队，在队尾插入）、dequeue（出队，从队头移除）和 isEmpty。

When a queue is implemented using a linear array, the front and rear pointers both move forwards over time, causing the unused space at the start of the array to be wasted. A circular queue solves this problem by wrapping the rear pointer back to the beginning of the array when it reaches the end. The condition (rear + 1) % size == front indicates that the circular queue is full.

使用数组实现线性队列时，front 和 rear 指针都会不断向后移动，导致数组前部的空闲空间被浪费。循环队列通过让 rear 指针到达数组末尾后回绕到开头来解决这一问题。当 (rear + 1) % size == front 时，表示循环队列已满。

Queues are widely used in CPU scheduling, print job management, breadth-first search (BFS), and buffering data streams between a producer and a consumer.

队列广泛用于 CPU 调度、打印任务管理、广度优先搜索（BFS）以及生产者和消费者之间的数据流缓冲。

6. Binary Trees | 二叉树

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Key terminology includes the root (the topmost node), leaf (a node with no children), height (the number of edges on the longest path from the root to a leaf), and depth (the number of edges from the root to a given node).

二叉树是一种层次数据结构，其中每个节点最多有两个子节点，分别称为左孩子和右孩子。关键术语包括根（最顶层的节点）、叶子（没有子节点的节点）、高度（从根到最远叶子的最长路径边数）以及深度（从根到某个节点的边数）。

Special types of binary trees include: a full binary tree, in which every node has either 0 or 2 children; a complete binary tree, in which all levels are fully filled except possibly the last level, with nodes filled from left to right; and a balanced binary tree, in which the height difference between the left and right subtrees of every node is at most 1.

二叉树有几种特殊类型：满二叉树中每个节点有 0 个或 2 个子节点；完全二叉树中除最后一层外所有层都填满，且最后一层从左到右填充；平衡二叉树中每个节点的左右子树高度差不超过 1。

For a binary tree of height h, the maximum number of nodes is:

2^(h+1) − 1

For 一棵高度为 h 的二叉树，其最大节点数为 2^(h+1) − 1。

7. Binary Search Trees and Traversals | 二叉搜索树与遍历

A binary search tree (BST) is a binary tree with the ordering property: for every node, all values in the left subtree are smaller than the node’s value, and all values in the right subtree are larger. This property enables efficient searching, insertion and deletion.

二叉搜索树（BST）是一种具有排序性质的二叉树：对于每个节点，其左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值。该性质使得搜索、插入和删除操作更加高效。

Operation	Average Case	Worst Case
Search / Insert / Delete	O(log n)	O(n)

The worst case occurs when nodes are inserted in sorted order, producing a degenerate tree that behaves like a linked list. Balanced BSTs such as AVL trees solve this problem by performing rotations to maintain logarithmic height.

最坏情况出现在节点按有序顺序插入时，产生的退化树表现得像链表一样。AVL 树等平衡 BST 通过旋转操作保持对数高度来解决这一问题。

Tree traversal visits every node exactly once. The three depth-first traversal methods are: preorder (root → left → right), inorder (left → root → right), and postorder (left → right → root). For a BST, inorder traversal visits nodes in ascending order. Breadth-first traversal, also called level-order traversal, visits nodes level by level from left to right.

树的遍历会恰好访问每个节点一次。三种深度优先遍历方法为：前序（根 → 左 → 右）、中序（左 → 根 → 右）和后序（左 → 右 → 根）。对于 BST，中序遍历按升序访问节点。广度优先遍历也称为层次遍历，逐层从左到右访问节点。

8. Graphs | 图

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections between vertices). Graphs can be directed (edges have a direction) or undirected (edges have no direction), and weighted (edges carry a numerical value) or unweighted. A graph in which every vertex is connected by an edge to every other vertex is called a complete graph.

图是一种非线性数据结构，由顶点（节点）和边（顶点之间的连接）组成。图可以是有向的（边有方向）或无向的（边无方向），也可以是有权重的（边带有数值）或无权重的。每个顶点都与其他所有顶点通过边相连的图称为完全图。

Two common representations exist. An adjacency matrix is a 2D array where matrix[i][j] is 1 (or the edge weight) if an edge exists from vertex i to vertex j, requiring O(V²) space. An adjacency list stores, for each vertex, a list of its neighbours, requiring O(V + E) space and being far more efficient for sparse graphs.

图有两种常见表示方式。邻接矩阵是一个二维数组，如果存在从顶点 i 到顶点 j 的边，则 matrix[i][j] 为 1（或边权重），其空间复杂度为 O(V²)。邻接矩阵？不，邻接表为每个顶点存储其邻居列表，空间复杂度为 O(V + E)，对稀疏图而言效率更高。

Breadth-first search (BFS) explores vertices level by level using a queue, and is useful for finding the shortest path in unweighted graphs. Depth-first search (DFS) explores as far as possible along each branch before backtracking, using a stack or recursion; it is useful for detecting cycles and topological sorting.

广度优先搜索（BFS）使用队列逐层探索顶点，适用于在无权重图中寻找最短路径。深度优先搜索（DFS）沿着每个分支尽可能深入再回溯，使用栈或递归实现；它适用于检测回路和拓扑排序。

9. Hash Tables | 哈希表

A hash table is a data structure that maps keys to values using a hash function. The hash function converts a key into an array index, allowing near-constant-time insertion, deletion and search. A good hash function should distribute keys uniformly across the array to minimise collisions.

哈希表是一种通过哈希函数将键映射到值的数据结构。哈希函数将键转换为数组下标，从而实现近似常数时间的插入、删除和查找。一个好的哈希函数应均匀地将键分布到数组中，以尽量减少冲突。

A collision occurs when two different keys produce the same hash index. Two common solutions are chaining and open addressing. In chaining, each array slot stores a linked list of all keys that hash to that slot. In open addressing, the table probes successive slots until an empty position is found; linear probing checks slot (index + 1), while quadratic probing checks (index + k²).

当两个不同键产生相同哈希下标时发生冲突。两种常见解决方案是链地址法和开放地址法。链地址法中，每个数组槽存储一个链表，包含所有哈希到该槽的键。开放地址法中，表按探测序列查找空位；线性探测检查 (index + 1)，二次探测检查 (index + k²)。

The load factor, defined as the number of entries divided by the table size, measures how full a hash table is. A higher load factor increases collision probability, so the table is usually resized when the load factor exceeds a threshold.

负载因子定义为条目数除以表大小，用于衡量哈希表的填满程度。负载因子越高，冲突概率越大，因此当负载因子超过阈值时通常需要对表进行扩容。

10. Time Complexity Comparison | 时间复杂度对比

Exam questions frequently require you to compare the time complexity of operations across different data structures. The table below summarises the average-case complexities you must memorise.

考试题目经常要求你比较不同数据结构操作的时间复杂度。下表汇总了需要牢记的平均情况复杂度。

Data Structure	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1) at head	O(1) at head
Stack / Queue	O(n)	O(n)	O(1)	O(1)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Hash Table	O(1)*	O(1)*	O(1)*	O(1)*

*For hash tables, O(1) is the average case; the worst case is O(n) when many collisions occur. Balancing a BST raises the worst-case complexity from O(n) to O(log n).

*对于哈希表，O(1) 是平均情况；当发生大量冲突时，最坏情况为 O(n)。使 BST 保持平衡可将最坏情况从 O(n) 改善为 O(log n)。

11. Choosing the Right Data Structure | 如何选择合适的数据结构

Examination questions often present a scenario and ask you to justify the most appropriate data structure. Your answer should link the scenario’s requirements to the characteristics of each structure, rather than simply naming a structure.

考试题经常给出一个场景，要求你论证最合适的数据结构。你的答案应把场景需求与每种结构的特点联系起来，而不是仅仅说出一个结构名称。

Need fast random access and a fixed number of elements? Choose an array — O(1) indexing without pointer overhead.
需要快速随机访问且元素数量固定？选择数组——O(1) 下标访问且无指针开销。
Need frequent insertion and deletion, especially at the ends? Choose a linked list — O(1) operations when the position is known.
需要频繁插入和删除，尤其是两端操作？选择链表——已知位置时操作复杂度为 O(1)。
Need to process items in reverse order, such as undo or function calls? Choose a stack — LIFO ordering.
需要按逆序处理项目，例如撤销操作或函数调用？选择栈——LIFO 顺序。
Need to process items in arrival order, such as printer jobs? Choose a queue — FIFO ordering.
需要按到达顺序处理项目，例如打印任务？选择队列——FIFO 顺序。
Need fast search, insertion and deletion with ordered data? Choose a balanced BST — O(log n) for all three operations.
需要对有序数据进行快速查找、插入和删除？选择平衡 BST——三种操作均为 O(log n)。
Need near-constant-time lookups by key, without ordering? Choose a hash table — average O(1) search.
需要按键进行近似常数时间查找，且不要求排序？选择哈希表——平均 O(1) 查找。

12. Common Exam Pitfalls | 常见考试失分点

Many students lose marks on data structure questions because of avoidable mistakes. The following points highlight the most frequent errors and how to avoid them.

许多学生在数据结构题目中因为可以避免的错误而失分。以下要点指出了最常见的错误及避免方法。

Confusing stack and queue: remember stack is LIFO, queue is FIFO. Use the mnemonic “last in, first out” versus “first in, first out”.
混淆栈和队列：记住栈是 LIFO，队列是 FIFO。可以用口诀“后进先出”对“先进先出”来区分。
Stating that hash table worst-case search is O(1): it is O(1) on average, but O(n) in the worst case due to collisions.
声称哈希表最坏情况查找为 O(1)：实际上平均情况为 O(1)，但最坏情况由于冲突为 O(n)。
Forgetting that array insertion and deletion are O(n) because elements must be shifted — not O(1).
忘记数组插入和删除是 O(n)，因为元素需要移动——而不是 O(1)。
Mixing up preorder and postorder in traversal questions: preorder visits the root first, postorder visits the root last.
混淆遍历中的前序和后序：前序先访问根节点，后序最后访问根节点。
Writing a BST search algorithm without checking for an empty tree — always include a base case.
编写 BST 搜索算法时未检查空树——务必包含基本情况。
Not drawing pointer updates clearly in linked list insertion/deletion questions — draw diagrams and update the pointers one at a time.
在链表插入/删除题目中指针更新不清晰——画图并逐一更新指针。

Finally, always practise tracing algorithms on small examples. Manually stepping through push and pop sequences, queue operations, tree traversals and hashing calculations with numbers will deepen your understanding and reduce mistakes in the actual examination.

最后，务必在小例子上练习追踪算法。手动逐步执行 push 和 pop 序列、队列操作、树的遍历以及带数字的哈希计算，将加深你的理解并减少实际考试中的错误。

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

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

Core Review of Basic Data Structures | 基本数据结构核心梳理