What Are ADTs?

IB Syllabus: B4.1.1 (HL) – Explain the properties and purpose of ADTs in programming.

This page is HL only.

Key Concepts
Worked Examples
Quick Code Check
Trace Exercise
Code Completion
Spot the Bug
Output Prediction
Practice Exercises
1. Core
2. Extension
3. Challenge
Connections

Key Concepts

An Abstract Data Type (ADT) is a theoretical model that describes what operations can be performed on data, without specifying how those operations are carried out internally.

Think of it like a vending machine: you know you can insert money, press a button, and receive an item. You do not need to know how the internal mechanism selects and delivers the item. The interface (buttons, coin slot) is separate from the implementation (motors, conveyor belts).

Key properties of an ADT:

Interface – a clearly defined set of operations the data type makes available (e.g., add, remove, search)
Encapsulation – the internal state is hidden; users interact only through the defined operations
Modularity – the implementation can be swapped without changing code that uses the ADT

Why this matters: the same ADT (e.g., a “List”) can be implemented using an array or a linked list. Code that uses the List ADT does not need to change when the implementation changes – this is the power of abstraction.

The Four Core Operations

Most ADTs support some combination of these fundamental operations:

Operation	What it does	Example
Insertion	Add a new element	Add a student to a roster
Deletion	Remove an existing element	Remove a cancelled order
Traversal	Visit every element in sequence	Print all items in a playlist
Search	Find a specific element	Look up a book by title

Static vs Dynamic Data Structures

Feature	Static (e.g., array)	Dynamic (e.g., linked list)
Size	Fixed at compile time	Grows and shrinks at runtime
Memory	Contiguous block, may waste space	Allocated per node, only as needed
Insertion/Deletion	Slow – must shift elements	Fast – just update references
Access by index	Fast – direct O(1)	Slow – must traverse O(n)

A static data structure like an array allocates a fixed block of contiguous memory. If you create an array of size 100 but only store 10 items, 90 slots are wasted. If you need to store 101 items, you cannot.

A dynamic data structure allocates memory on demand. Each element (called a node) is stored wherever space is available, and nodes are connected through references (pointers). The structure grows and shrinks as the program runs.

ADTs You Will Build in This Section

ADT	Defining Rule	Key Operations
Linked List	Linear sequence of connected nodes	insert, delete, traverse, search
Stack	Last In, First Out (LIFO)	push, pop, peek
Queue	First In, First Out (FIFO)	enqueue, dequeue, peek
Binary Search Tree	Left child < parent < right child	insert, delete, search, traverse
Set	Unordered, unique elements only	add, remove, contains, union, intersection
HashMap	Key-value pairs via hashing	put, get, remove, containsKey

Worked Examples

Example 1: ADT as a Contract

An ADT defines a contract – a set of operations that any implementation must support. In Java, we express this naturally with an interface.

// The ADT contract: what operations a SimpleList must support
public interface SimpleList {
    void add(String item);
    String get(int index);
    int size();
    boolean contains(String item);
}

This interface says nothing about how items are stored. Two different classes could implement it in completely different ways:

// Implementation 1: backed by an array (static structure)
public class ArrayBasedList implements SimpleList {
    private String[] data;
    private int count;

    public ArrayBasedList(int capacity) {
        data = new String[capacity];
        count = 0;
    }

    public void add(String item) {
        data[count] = item;
        count++;
    }

    public String get(int index) {
        return data[index];
    }

    public int size() {
        return count;
    }

    public boolean contains(String item) {
        for (int i = 0; i < count; i++) {
            if (data[i].equals(item)) {
                return true;
            }
        }
        return false;
    }
}

The key idea: any code written to use SimpleList works with any implementation. The caller never knows – or needs to know – whether an array or a linked list is used internally.

Example 2: Same Interface, Different Trade-offs

public class AdtDemo {
    public static void printAll(SimpleList list) {
        // This method works with ANY SimpleList implementation
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

    public static void main(String[] args) {
        SimpleList roster = new ArrayBasedList(50);
        roster.add("Aiko");
        roster.add("Ben");
        roster.add("Carlos");

        printAll(roster);  // prints all three names

        System.out.println("Contains Ben? " + roster.contains("Ben"));
        System.out.println("Size: " + roster.size());
    }
}

Output:

Aiko
Ben
Carlos
Contains Ben? true
Size: 3

If we later build a LinkedBasedList that also implements SimpleList, we can swap it in without changing printAll or any other code that uses the interface. This is the practical benefit of programming to an ADT rather than to a specific implementation.

Example 3: Static vs Dynamic – The Limits of Arrays

This example illustrates why dynamic structures are needed:

public class ArrayLimitDemo {
    public static void main(String[] args) {
        // Static: must decide size in advance
        String[] waitlist = new String[3];
        waitlist[0] = "Order-101";
        waitlist[1] = "Order-102";
        waitlist[2] = "Order-103";

        // What if a 4th order arrives?
        // waitlist[3] = "Order-104";  // ArrayIndexOutOfBoundsException!

        // Inserting in the middle requires shifting everything
        // To insert "Order-100" at position 0:
        // Must shift [0] -> [1], [1] -> [2], etc. -- O(n) work

        System.out.println("Array is full with " + waitlist.length + " slots");
        System.out.println("Cannot add more without creating a new, larger array");
    }
}

Output:

Array is full with 3 slots
Cannot add more without creating a new, larger array

With a dynamic structure (like a linked list), there is no fixed capacity – you simply create a new node and link it in. No shifting required.

Quick Code Check

Q1. What does an Abstract Data Type (ADT) describe?

Q2. Which ADT property hides the internal state from users?

Q3. Which of the following is a characteristic of a static data structure?

Q4. In the context of ADTs, what is the purpose of an interface?

Q5. Why are dynamic data structures considered more memory-efficient than arrays for unpredictable data sizes?

Q6. A program uses a SimpleList ADT. The underlying implementation is changed from an array to a linked list. What happens to the code that uses SimpleList?

Trace Exercise

Trace through the following code and fill in the values after each operation.

SimpleList items = new ArrayBasedList(5);
items.add("Red");
items.add("Green");
items.add("Blue");

After operation	get(0)	contains("Green")
new ArrayBasedList(5)	--
add("Red")
add("Green")	Red
add("Blue")	Red	true

Code Completion

Complete the Java interface for a SimpleStack ADT that supports the standard stack operations.

Fill in the missing method signatures to define the Stack ADT contract:

public interface SimpleStack {
    void (String item);  // add to top
    String ();             // remove from top
    String ();            // view top without removing
    boolean isEmpty();
    int ();               // number of elements
}

Complete the code to check if a list contains an item by traversing the internal array:

Fill in the blanks to implement the contains method:

public boolean contains(String item) {
    for (int i = 0; i < ; i++) {
        if (data[i].(item)) {
            return ;
        }
    }
    return false;
}

Spot the Bug

This add method should store items in sequence, but every item ends up at index 0:

1public void add(String item) { 2 if (count >= data.length) { 3 System.out.println("List is full"); 4 return; 5 } 6 data[count] = item; 7}

Pick the correct fix:

This contains method never finds any item even when it exists in the list:

1public boolean contains(String item) { 2 for (int i = 0; i < count; i++) { 3 if (data[i] == item) { 4 return true; 5 } 6 } 7 return false; 8}

Pick the correct fix for line 3:

Output Prediction

What does this code print?

SimpleList fruits = new ArrayBasedList(10);
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");

System.out.println(fruits.size());
System.out.println(fruits.get(1));
System.out.println(fruits.contains("Mango"));

Type the exact output: