Show understanding that an ADT is a collection of data and a set of operations on those data

10.4 Introduction to Abstract Data Types (ADT) 📚

What is an ADT? 🤔

An Abstract Data Type is a conceptual model that defines a collection of data and a set of operations that can be performed on that data, without specifying how the data is stored or how the operations are implemented. Think of it as a black‑box that tells you what you can do, not how it does it.

Core Components of an ADT

• Data Set (D): The type of data the ADT manages.
• Operations (O): The functions that can be applied to the data.

Mathematically, an ADT can be expressed as:

$$\text{ADT} = (D, O)$$

Common ADT Examples

1. Stack – LIFO (Last In, First Out). Operations: push, pop, peek.
2. Queue – FIFO (First In, First Out). Operations: enqueue, dequeue, front.
3. List – Ordered collection. Operations: insert, delete, search, display.
4. Set – Unordered, no duplicates. Operations: add, remove, contains.

Analogy: The Vending Machine 🍭

Imagine a vending machine. You know you can:

• Insert a coin.
• Select a product.
• Receive the product.

You do not need to know how the machine stores the snacks or how it dispenses them. That is how an ADT works – you interact with its operations, not its internals.

Implementing an ADT

An ADT can be implemented using various underlying data structures:

• Array – fast random access, fixed size.
• Linked List – dynamic size, efficient insert/delete.
• Tree – hierarchical data, balanced for search.
• Hash Table – fast lookup, but unordered.

The key point: the interface (operations) stays the same, even if the implementation changes.

Exam Tip Box 📌

When answering questions about ADTs:

• State the data set and the operations clearly.
• Use the notation (D, O) if you can.
• Explain that the implementation is hidden (abstract).
• Give a real‑world example (e.g., a phone contact list).

Quick Quiz 🚀

1. What are the two core components of an ADT?
2. List the three primary operations of a stack.
3. Why is it useful that an ADT hides its implementation?

Summary Table of ADT Operations