B4.1.1 Explain the properties and purpose of ADTs in programming. (HL only)

The big idea

An Abstract Data Type (ADT) is a concept, not a specific piece of code.
It describes what a data structure should do, not how it’s implemented.

Think of it as a contract:

• It defines the operations available (insert, remove, find, etc.).
• It hides the internal details of how those operations are carried out.

By separating what from how, ADTs allow developers to change the underlying implementation without affecting the code that uses it.

 

The purpose of ADTs

1. Abstraction: Programmers work with the operations, not the implementation details.
2. Modularity: You can swap out implementations without changing the rest of the program.
3. Reusability: The same ADT interface can be implemented in different ways for different needs.
4. Maintainability: Code depending on an ADT is easier to maintain because the interface stays consistent.

 

Properties of ADTs

1. Encapsulation:
   • The data is stored internally, and only accessible through defined operations.
   • Example: You don’t directly access the array in a stack — you use push() or pop().
2. Well-defined operations:
   • Every ADT specifies the operations that can be performed and their expected behavior.
   • Example: A queue must have enqueue (add) and dequeue (remove in FIFO order).
3. Implementation independence:
   • The same ADT can have multiple implementations.
   • Example: A list can be implemented using an array, a linked list, or a dynamic array — but its interface remains the same.
4. Predictable performance:
   • The time and space complexity of operations can be described and compared, even if the internal details differ.

 

Example: Stack ADT in Python

Interface (what it should do):

• push(item) – Add an item to the top
• pop() – Remove and return the top item
• peek() – Look at the top item without removing it
• is_empty() – Check if the stack is empty

Implementation (how it’s done):

class Stack:
    def __init__(self):
        self._items = []  # Internal storage

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if not self.is_empty():
            return self._items.pop()
        raise IndexError("Pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self._items[-1]
        return None

    def is_empty(self):
        return len(self._items) == 0

Usage (without knowing internals):

s = Stack()
s.push(10)
s.push(20)
print(s.pop())   # 20
print(s.peek())  # 10

The user doesn’t care whether _items is a list, linked list, or another structure — they only care that the stack operations work as expected.

 

Why this abstraction is powerful

• If performance needs change, you can replace _items with a linked list or deque without changing the interface.
• Other parts of the program still call push() and pop() — no rewrite required.
• This makes it easy to optimize or adapt code for different environments.