HL Topic 5 introduces abstract data structures: their properties, implementations, and use cases. Students must understand how stacks, queues, linked lists, and binary trees work and when to use each.
Stack (LIFO): push (add to top), pop (remove from top), peek (view top). Applications: undo operations, expression evaluation, backtracking algorithms, call stack in recursion. Queue (FIFO): enqueue (add to rear), dequeue (remove from front). Applications: print queues, BFS, scheduling. Circular queue to avoid wasted space.
Each node contains data and a pointer to the next node. Head pointer references the first node; last node points to null. Advantages over arrays: dynamic size, efficient insertion/deletion. Disadvantages: no direct access (must traverse), extra memory for pointers. Operations: insert (at beginning, end, middle), delete, search, traverse.
Each node has at most two children (left, right). Binary search tree (BST): left child < parent < right child. Traversals: in-order (left, root, right — gives sorted order), pre-order (root, left, right — copy tree), post-order (left, right, root — delete tree). Searching a balanced BST: O(log n). Insertion and deletion maintain BST property.
Recursive algorithms have base case (termination) and recursive case (calls itself with smaller input). Call stack stores return addresses and local variables. Big-O: describes worst-case growth rate. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) log-linear, O(n²) quadratic, O(2ⁿ) exponential. Compare algorithm efficiency: binary search O(log n) vs linear O(n).
Paper 2 (HL) tests ADTs using Java. You should be able to implement basic stack/queue operations, linked list traversal, and binary tree traversals in Java. However, the exam often provides partial code and asks you to complete or trace it, rather than writing from scratch. Focus on understanding the logic and being able to trace through given code. For the IA, you can use any language.
Book a Trial + Diagnostic session. Get a personalized Learning Path with clear milestones, tutor match, and a plan recommendation — all within 24 hours.
Book Trial + Diagnostic →