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 the language’s built-in tools (Java’s library classes, Python’s lists). 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 | Syllabus | Key Concepts | Level |
|---|---|---|---|---|
| 1 | What Are ADTs? | B4.1.1 | Interface vs implementation, why abstraction matters | HL |
| 2 | Linked Lists | B4.1.2, B4.1.3 | Node class, traversal, insert, delete | HL |
| 3 | Ordered Linked Lists | B4.1.3 | Insert in order, maintaining the sorted property | HL |
| 4 | Doubly Linked Lists | B4.1.2, B4.1.3 | prev + next references, bidirectional traversal | HL |
| 5 | Stacks from Scratch | B4.1.1 | Building LIFO with linked nodes | HL |
| 6 | Queues from Scratch | B4.1.1 | Building FIFO with linked nodes | HL |
| 7 | Binary Search Trees | B4.1.4 | Node with left/right, insert, search, in-order traversal | HL |
| 8 | BST Operations | B4.1.4 | Delete, height, balanced vs unbalanced, traversals | HL |
| 9 | Sets and HashMaps | B4.1.5, B4.1.6 | Hashing, collision resolution, unique elements | HL |
| 10 | Choosing the Right Structure | All B4.1 | Trade-off table, decision flowchart | HL |
Using vs Building: In B2.2 you learned to use stacks and queues through ready-made tools (Java’s library classes, Python’s lists). 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