Cambridge Syllabus Notes

19.1 Algorithms – Abstract Data Types (ADT)

What is an ADT? 📦

An Abstract Data Type is a conceptual model that defines a set of values and a set of operations that can be performed on those values, without specifying how the data is stored or how the operations are implemented. Think of it as a vending machine: you know you can insert coins, select a product, and receive an item, but you don’t need to know how the machine stores the coins or how it dispenses the product.

Common ADTs and Their Operations

ADT	Key Operations	Typical Complexity
Stack	push, pop, peek, isEmpty	O(1)
Queue	enqueue, dequeue, front, isEmpty	O(1)
Linked List	insert, delete, search, traverse	O(n) worst‑case

Stack Example: Push & Pop

A stack follows the Last In, First Out (LIFO) rule. Imagine a stack of plates: you can only add or remove the top plate.

Initial stack: []
Push 5 ➜ [5]
Push 10 ➜ [5, 10]
Pop ➜ returns 10, stack becomes [5]

Pseudocode:

push(item):
    stack[top] = item
    top = top + 1

pop():
    if top == 0: error "empty"
    top = top - 1
    return stack[top]

Exam Tip: ADT Questions

• Identify the ADT – Look for keywords like “stack”, “queue”, “list” in the question. • List all operations – Write them in a table. • State time complexities – Use Big‑O notation. • Explain the abstraction – Describe why the implementation details are hidden. • Use LaTeX for formulas – e.g., $O(1)$, $O(n)$, $O(\log n)$.

Key Takeaway 🎓

Abstract Data Types let you focus on what you want to do (the operations) rather than how you do it. This separation of concerns is a powerful tool for designing clear, maintainable algorithms and for preparing for exam questions that test your understanding of data structures at a conceptual level.

Show understanding of and use Abstract Data Types (ADT)