Abstract Data Types

This lesson covers Abstract Data Types (ADTs) — a foundational concept in the OCR A-Level Computer Science (H446) specification. Understanding ADTs is essential for designing clean, modular, and maintainable software.

---

What is an Abstract Data Type?

An Abstract Data Type (ADT) is a logical description of a data structure that defines:

1. What data it stores.
2. What operations can be performed on the data.

An ADT does not specify how the data is stored or how the operations are implemented. It describes the interface (what you can do) without revealing the implementation (how it is done).

Analogy

Think of a television remote control:

• Interface: You know you can press "Volume Up", "Channel Down", "Power On/Off".
• Implementation: You do not need to know the electronics inside the remote.

---

Why Use ADTs?

Benefit	Description
Abstraction	Users interact with the interface, not the implementation.
Encapsulation	Implementation details are hidden — changes to the implementation do not affect the user.
Modularity	Code is organised into self-contained units that can be developed and tested independently.
Reusability	An ADT can be reused in different programs with different implementations.
Flexibility	The implementation can be changed (e.g., from an array to a linked list) without changing the code that uses the ADT.

---

Interface vs Implementation

Concept	Definition	Example (Stack)
Interface	The set of operations the ADT provides	push(), pop(), peek(), isEmpty()
Implementation	The actual code and data structures used	Array-based, linked list-based

Key Insight

The same ADT can have multiple implementations:

ADT	Implementation 1	Implementation 2
Stack	Array-based	Linked list-based
Queue	Circular array	Linked list
List	Array	Linked list
Priority Queue	Sorted array	Binary heap
Dictionary	Hash table	BST

The user of the ADT does not need to know or care which implementation is being used — they just use the defined operations.

---

Common ADTs in Computer Science

1. Stack ADT

Operation	Description
push(item)	Add an item to the top
pop()	Remove and return the top item
peek()	Return the top item without removing
isEmpty()	Return true if the stack is empty
size()	Return the number of items

2. Queue ADT

Operation	Description
enqueue(item)	Add an item to the rear
dequeue()	Remove and return the front item
front()	Return the front item without removing
isEmpty()	Return true if the queue is empty
size()	Return the number of items

3. List ADT

Operation	Description
insert(index, item)	Insert item at given position
remove(index)	Remove item at given position
get(index)	Return item at given position
set(index, item)	Replace item at given position
contains(item)	Check if item exists in the list
size()	Return the number of items
isEmpty()	Return true if the list is empty

4. Dictionary (Map) ADT

Operation	Description
put(key, value)	Add or update a key-value pair
get(key)	Return the value associated with the key
remove(key)	Remove the key-value pair
containsKey(key)	Check if the key exists
keys()	Return all keys
size()	Return the number of key-value pairs

5. Priority Queue ADT

Operation	Description
insert(item, priority)	Add an item with a given priority
removeHighest()	Remove and return the highest-priority item
peekHighest()	Return the highest-priority item without removing
isEmpty()	Return true if the queue is empty

---

Designing an ADT: Step by Step

When designing a new ADT, follow these steps:

Step 1: Identify the Data

What information does the ADT need to store?

Step 2: Define the Operations

What actions can be performed on the data? Define each operation with:

• Name
• Input parameters
• Output/return value
• Pre-conditions (what must be true before the operation)
• Post-conditions (what is true after the operation)

Step 3: Consider Edge Cases

What happens when the structure is empty? What about invalid inputs?