Abstract data types/data structures — AQA A-Level Computer Science

Abstract Data Types (ADTs) provide high-level models of data storage that encapsulate data representation behind well-defined operational interfaces. In AQA A-Level Computer Science, this topic explores both the conceptual mechanics and the practical implementations of stacks, queues, linked lists, trees, graphs, hash tables, and dictionaries.

Understanding ADTs bridges the gap between software design and algorithmic efficiency. Selecting the correct data structure directly governs the time and space complexity of computational solutions, forming a foundational component of Paper 1 and Paper 2 assessment objectives.

• →Abstraction vs Implementation: An ADT describes what operations can be performed (e.g., push, pop, peek), whereas a data structure represents how those operations are physically stored in memory.
• →Static vs Dynamic Data Structures: Static structures have fixed memory allocations determined at compile time (e.g., fixed-size arrays), while dynamic structures allocate memory from the heap at runtime using pointers.
• →Linear vs Non-Linear Structures: Stacks, queues, and linked lists store elements sequentially, while trees and graphs represent non-linear hierarchical or interconnected network relationships.
• →Collision Resolution in Hash Tables: Techniques such as open addressing (linear probing) and closed addressing (chaining with linked lists) resolve scenarios where two distinct keys hash to the same index.

• Identifies the stack as LIFO, meaning the last item pushed is the first item popped.
• Describes push as adding an item to the top and pop as removing the item from the top.
• Recognises that only the top element is directly accessible at any time.
• Links the stack to a practical use such as subroutine return addresses or undo functionality.

• 💡Trace a short sequence of push and pop operations step by step on paper to check the final contents.
• 💡Remember that the most recently pushed item is always the next one popped.
• 💡When an MCQ asks about removal order, check whether the answer option reflects last in, first out.
• 💡When drawing or tracing pointer operations for linked lists and trees, explicitly label pointer variables (e.g. 'Head', 'Prev', 'Curr') and denote null pointers clearly using ground symbols or the value 'null'.
• 💡Always state time complexities using Big-O notation when comparing operations across structures (e.g., hash table retrieval is O(1) average case, whereas unindexed linked list search is O(n)).
• 💡In pseudocode questions, remember to implement defensive programming checks: verify 'isFull()' before pushing/enqueueing and 'isEmpty()' before popping/dequeueing.

• Treats a stack as FIFO, which is the behaviour of a queue; correct by remembering that a stack reverses the order of arrival.
• Assumes items can be removed from the bottom or middle; correct by restricting removal to the top only.
• Confuses push and pop, or reverses their effects; correct by linking push to adding and pop to removing from the top.
• Assuming dynamic data structures are always superior to static data structures. While dynamic structures avoid overflow and conserve unused memory, they incur memory overhead for pointer storage and lack direct random index access.
• Believing a circular queue moves items in memory during dequeue operations. Circular queues use modulo arithmetic to advance pointer indices; the existing data elements are not physically shifted.
• Confusing graph traversals with tree traversals. Graphs may contain cycles and disconnected components, requiring a 'visited' set or boolean flags to prevent infinite loops during BFS or DFS traversals.

1. 1Day 1-3: Master linear ADTs. Code and trace stacks, linear queues, circular queues, and priority queues using static arrays and dynamic linked lists.
2. 2Day 4-6: Study non-linear structures. Practice manual insertion, deletion, and tree traversals (pre-order, in-order, post-order) for binary search trees.
3. 3Day 7-9: Explore graphs and hash tables. Implement adjacency matrices vs adjacency lists, hash functions, and collision resolution strategies.
4. 4Day 10-12: Solve past AQA exam questions focusing on 6-mark comparative essays, pointer-trace diagrams, and pseudocode algorithms.

• 📋Trace and diagram questions: Filling tables or drawing diagrams to trace pointers, stack frames, or queue indices across sequential operations.
• 📋Algorithm implementation: Writing or completing pseudocode for core operations like tree insertions, linked list deletions, or hash table lookups.
• 📋Comparative analysis: Evaluating trade-offs between static vs dynamic structures or adjacency matrices vs adjacency lists for specific application contexts.