Fundamentals of data structures — AQA A-Level Computer Science

Data structures are fundamental building blocks in computer science, providing organised ways to store, manage, and retrieve data efficiently. In the AQA A-Level Computer Science specification, you'll explore static and dynamic structures, including arrays, records, lists, tuples, stacks, queues, trees, graphs, and hash tables. Understanding these structures is crucial because they directly impact algorithm performance and memory usage—choosing the wrong structure can make a program slow or even unworkable.

This topic builds on your GCSE knowledge of simple arrays and lists, extending into more complex structures like binary trees and graphs. You'll learn not only how each structure works but also when to apply them, such as using a stack for expression evaluation or a queue for breadth-first search. Mastery of data structures is essential for tackling algorithms, databases, and even object-oriented programming, as many real-world systems rely on efficient data organisation.

By the end of this topic, you should be able to implement key operations (insertion, deletion, traversal) for each structure, analyse their time and space complexity, and justify your choices in exam questions. This knowledge forms the backbone of problem-solving in computer science, from operating systems to artificial intelligence.

• →Static vs dynamic structures: Static structures (e.g., arrays) have fixed size, while dynamic structures (e.g., linked lists) can grow/shrink at runtime.
• →Abstract Data Types (ADTs): Stacks (LIFO), queues (FIFO), trees (hierarchical), graphs (networked) – understand their properties and typical operations.
• →Traversal algorithms: For trees (pre-order, in-order, post-order) and graphs (depth-first, breadth-first) – know the order and use cases.
• →Hash tables and collision resolution: How hashing works, handling collisions via chaining or open addressing (linear probing, quadratic probing).
• →Complexity analysis: Big O notation for insertion, deletion, search, and traversal of each structure (e.g., O(1) for stack push/pop, O(n) for array search).

• Correct identification and application of data structures to solve problems.
• Ability to distinguish between static and dynamic data structures.
• Correct implementation of operations for queues (linear, circular, priority) and stacks (push, pop, peek).
• Understanding of graph representations (adjacency matrix vs adjacency list) and tree traversal methods (pre-order, post-order, in-order).
• Application of hashing algorithms and collision handling via rehashing.
• Understanding of vector operations including addition, scalar multiplication, and dot products.

• 💡Practice tracing algorithms for stack and queue operations to ensure you understand the state changes.
• 💡Be prepared to draw and interpret diagrams for graphs and trees.
• 💡Ensure you can explain the advantages and disadvantages of different data structures for specific scenarios.
• 💡Memorize the standard operations for each abstract data type (e.g., push/pop for stacks, enqueue/dequeue for queues).
• 💡Use clear, annotated diagrams when explaining graph or tree traversals.
• 💡Always draw diagrams when answering questions about data structures. A clear sketch of a stack pushing/popping or a tree traversal can earn method marks even if your explanation is slightly off.
• 💡When comparing structures, explicitly mention time complexity for key operations (e.g., 'Array insertion at the front is O(n) because elements must shift, whereas linked list insertion is O(1) if you have a pointer').
• 💡For algorithm questions, state which data structure you would use and justify it with two reasons – one about efficiency and one about the nature of the problem (e.g., 'I would use a queue because it processes tasks in the order they arrive, and enqueue/dequeue are O(1)').

• Confusing the properties of static and dynamic data structures.
• Incorrectly implementing circular queue logic, particularly handling the wrap-around.
• Failing to distinguish between different graph traversal algorithms and their specific applications.
• Misunderstanding the difference between an adjacency matrix and an adjacency list in terms of space and time complexity.
• Errors in calculating the dot product of vectors or applying vector operations in the wrong context.
• Misconception: 'A stack and a queue are the same thing.' Correction: Stacks are LIFO (Last In, First Out) – like a pile of plates; queues are FIFO (First In, First Out) – like a line at a till.
• Misconception: 'Binary trees are always sorted.' Correction: Not all binary trees are binary search trees (BSTs). A BST has the property that left child < parent < right child, but a general binary tree has no such ordering.
• Misconception: 'Hash tables guarantee O(1) lookup.' Correction: In the worst case (many collisions), lookup can degrade to O(n). Good hash functions and load factor management are essential.