Abstract Data Types
IB Syllabus: B4.1 – Abstract Data Types (HL only)
This entire section is HL only.
Overview
In earlier sections you used arrays, ArrayLists, stacks, and queues through Java’s built-in classes. You called push(), pop(), add(), and remove() without worrying about how those operations actually work inside.
This section takes you behind the scenes. You will build data structures from scratch using nodes and references, understand the trade-offs between different implementations, and learn when each structure is the right tool for the job.
| Topic | Structure | Key Idea | Syllabus |
|---|---|---|---|
| What Are ADTs? | Conceptual | Interface vs implementation, why abstraction matters | B4.1.1 |
| Linked Lists | Singly linked list | Node class, traversal, insert, delete | B4.1.2, B4.1.3 |
| Ordered Linked Lists | Sorted linked list | Insert in order, maintaining sorted property | B4.1.3 |
| Doubly Linked Lists | Doubly linked list | prev + next references, bidirectional traversal | B4.1.2, B4.1.3 |
| Stacks from Scratch | Stack (node-based) | Building LIFO with linked nodes | B4.1.1 |
| Queues from Scratch | Queue (node-based) | Building FIFO with linked nodes | B4.1.1 |
| Binary Search Trees | BST | Node with left/right, insert, search, in-order | B4.1.4 |
| BST Operations | BST (advanced) | Delete, height, balanced vs unbalanced, traversals | B4.1.4 |
| Sets and HashMaps | HashSet, HashMap | Hashing, collision resolution, unique elements | B4.1.5, B4.1.6 |
| Choosing the Right Structure | Comparison | Trade-off table, decision flowchart | All B4 |
Using vs Building: In B2.2 you learned to use stacks and queues through Java’s library classes. Here you learn to build them from scratch using node classes and pointer manipulation – a fundamentally different skill.
How This Section Connects
- Prerequisites: OOP Fundamentals (classes, encapsulation, object references), Recursion (for BST traversal)
- Builds on: Stacks and Queues (using built-in classes)
- Supports: Internal Assessment projects that need custom data structures