IB Computer Science B4.1: Fundamentals of abstract data types (HL only)

New IB Computer Science syllabus · first exams May 2027 · Theme B · Paper 2 · HL only · Python and Java

B4 Abstract data types is HL only (23 hours) and is the final unit of the syllabus. It covers the data structures behind efficient programs: linked lists, binary search trees, sets and hash tables.

Key points

B4.1.1 What an ADT is

An ADT is defined by what operations it supports, not how they're implemented. For example, a List ADT promises insert, delete, traverse and search. Whether it's built on an array or a linked list is hidden.

B4.1.2–B4.1.3 Linked lists

• Each node holds data and a pointer to the next node.
• Three types:
  • Singly linked: each node points to the next. The last node's next is null.
  • Doubly linked: each node points to both the next and the previous node. This suits "skip forward and back", as in a music playlist.
  • Circular: the last node points back to the head, so traversal stops when it returns to the head, not at null.
• Operations: insertion, deletion, traversal, search.
• Compared with arrays:
  • Advantages: grows freely, and inserts or deletes without shifting other elements.
  • Disadvantages: no direct indexing (you reach an item by following pointers), and extra memory for each pointer.

B4.1.4 Binary search trees

• The BST property: every node's left subtree holds smaller values and its right subtree holds larger values.
• Operations: insert, delete, search and traverse.
• An in-order traversal (left → node → right) visits the values in ascending order.
• Deleting a node with two children: replace it with its in-order successor (the smallest value in its right subtree), so the tree stays in order.

B4.1.5 Sets

• A set is unordered and holds unique elements.
• Set operations: union, intersection and difference.
• You also need code to:
  • check membership
  • add and remove elements
  • test for a subset or superset
• Python: set. Java: HashSet.

B4.1.6 Hash tables

A hash function maps each key to a position in a table. You need three ideas:

• Collisions happen when two keys hash to the same position. They're resolved by chaining or open addressing.
• The load factor is how full the table is. As it rises, collisions increase and performance drops, so the table is resized.
• Python: dict and set. Java: HashMap and HashSet.

Exam-style question

Describe, step by step, how the values 40, 20, 60, 50 would be inserted into an initially empty BST, and state the order in which an in-order traversal of the resulting tree would visit them. [5]

Mark scheme

[1] for each of the four insertion positions, [1] for the correct in-order output:

• 40 is inserted first, so it becomes the root.
• 20 < 40, so it becomes 40's left child.
• 60 > 40, so it becomes 40's right child.
• 50 > 40, so go right; then 50 < 60, so it becomes 60's left child.
• In-order traversal: 20, 40, 50, 60.

        40
       /  \
     20    60
          /
        50

Common mistakes that cost marks

• Stopping a circular list traversal at null. There's no null; stop when you get back to the head.
• Deleting a node with two children by just removing it, which leaves two orphaned subtrees.
• Saying sets keep elements in order. Sets are unordered and remove duplicates.
• Describing a hash table without collisions or load factor, the two ideas the guide requires.

Frequently asked questions

Is B4 on the SL syllabus?
No. The whole of B4 Abstract data types is HL only.

Which built-in structures should I know?
HashMap and HashSet in Java; dict and set in Python.

Go further

• Practise B4.1 with instant marking on ExamHaus, in Python or Java. → examhaus.com
• Full B4.1 presentations (linked lists; trees, sets and hashing) and question bank with mark scheme on CS Exam Ready. → csexamready.com/resources/ib-diploma
• IB CS mock exams: Paper 2 in Python and Java. → examhaus.com/mock-exams