B4.1 Fundamentals of ADTs: notes and practice

What you need to know

Our summary of the topic in our own words, not the IB guide. Points marked HL are for Higher Level only.

• Explain what an abstract data type is: a set of data plus the operations on it, separate from its implementationHL
• Explain why separating interface from implementation lets the implementation change safelyHL
• Choose an appropriate ADT for a described problem and justify itHL
• Describe the structure of a linked list in terms of nodes and referencesHL
• Compare a linked list with an array on insertion, deletion, access and memoryHL
• Distinguish singly linked, doubly linked and circular linked listsHL
• Trace insertion and deletion in a linked list, including at the head, the tail and the middleHL
• Write code that builds and traverses a linked listHL
• Describe the structure of a binary search tree and the ordering property it maintainsHL
• Insert values into a binary search tree and draw the resulting treeHL
• Search a binary search tree and state the complexity in the balanced and unbalanced casesHL
• Perform in-order, pre-order and post-order traversals of a binary treeHL
• Explain why a tree becomes unbalanced and what rebalancing achievesHL
• Remove a node from a binary search tree, including the case with two childrenHL
• Describe a set as an unordered collection with no duplicates and name its operationsHL
• Write code that uses a set to solve a problem such as removing duplicates or testing membershipHL
• Apply set operations including union, intersection and differenceHL
• Compare the ADTs studied and select the right one for a described requirement, justifying on complexity and behaviourHL
• Describe how a hash table stores and retrieves by key, and what a collision isHL

Practice questions

Original questions written for the 2027 course, marked as you go. Easiest first.

• Stack or queue: print jobs and undoWritten · Core
• Changing a stack to use a linked listWritten · Stretch

Exam tips for B4.1

• Draw linked lists and trees as you trace insertions and deletions. Pointer changes are easy to lose in your head.
• Know the three tree traversals (in-order, pre-order and post-order) and practise them on small trees.
• Justify your choice of ADT with the operation the problem does most often.