10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a mathematical model that defines a set of data and the operations that can be performed on that data. It focuses on what the data represents and what operations are available, without specifying how these operations are implemented.

Key Concepts

• Data Type: The kind of data the ADT will hold (e.g., integers, strings, lists).
• Operations: The actions that can be performed on the data (e.g., insert, delete, search, sort).
• Abstraction: Hiding the underlying implementation details from the user. Users interact with the ADT through its defined operations.

Benefits of Using ADTs

• Modularity: ADTs promote modularity by separating the data representation from the operations.
• Flexibility: The underlying implementation of an ADT can be changed without affecting the code that uses the ADT, as long as the interface (operations) remains the same.
• Code Reusability: ADTs can be reused in different parts of a program or in different programs.
• Improved Maintainability: Changes to the implementation are isolated to the ADT, making the code easier to maintain.

Example: The List ADT

Consider a list ADT. It can be defined as a collection of ordered elements.

Operation	Description	Precondition	Postcondition
CreateList()	Creates an empty list.	None	Returns an empty list.
Insert(element, position)	Inserts an element at a specified position in the list.	position is a valid index within the list.	The element is added to the list at the specified position.
Delete(position)	Deletes the element at a specified position in the list.	position is a valid index within the list.	The element at the specified position is removed from the list.
Get(position)	Returns the element at a specified position in the list.	position is a valid index within the list.	Returns the element at the specified position.
Size()	Returns the number of elements in the list.	None	Returns the number of elements in the list.

The list ADT defines what a list is and what operations are possible. The actual implementation of the list (e.g., using an array or a linked list) is hidden from the user. Different implementations can exist as long as they provide the same interface.

$$ \text{ADT List} = \text{Data} + \text{Operations} $$

Where:

• Data: A collection of elements.
• Operations: A set of well-defined actions that can be performed on the elements of the list.