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 does, rather than how it is implemented. This separation of concerns allows for flexibility in implementation and promotes code reusability.

Key Concepts of ADTs

• Data Type: The kind of data the ADT will hold (e.g., integers, characters, strings).
• Operations: The actions that can be performed on the data (e.g., adding, removing, accessing).
• Interface: The set of operations that are publicly available to users of the ADT.
• Implementation: The underlying way the ADT is physically stored and implemented (e.g., using arrays, linked lists, trees). This is hidden from the user.

Why Use ADTs?

Using ADTs offers several advantages:

• Abstraction: Hides the implementation details, making code easier to understand and maintain.
• Flexibility: Allows for different implementations of the same ADT without changing the code that uses it.
• Modularity: Promotes well-organized and reusable code.
• Data Integrity: Defines clear rules for how data can be manipulated, helping to prevent errors.

Examples of ADTs

Common examples of ADTs include stacks, queues, and linked lists. These are fundamental data structures used in many computer science applications.

Stack

A stack is an ADT that follows the Last-In, First-Out (LIFO) principle. Think of a stack of plates ÔÇô the last plate added is the first one removed.

Operation	Description	Complexity
push	Adds an element to the top of the stack.	O(1)
pop	Removes the element from the top of the stack.	O(1)
peek	Returns the element at the top of the stack without removing it.	O(1)
isEmpty	Checks if the stack is empty.	O(1)

Implementation Examples: Stacks can be implemented using arrays or linked lists.

Queue

A queue is an ADT that follows the First-In, First-Out (FIFO) principle. Think of a queue of people waiting in line ÔÇô the first person in line is the first one served.

Operation	Description	Complexity
enqueue	Adds an element to the rear of the queue.	O(1)
dequeue	Removes the element from the front of the queue.	O(1)
peek	Returns the element at the front of the queue without removing it.	O(1)
isEmpty	Checks if the queue is empty.	O(1)

Implementation Examples: Queues can be implemented using arrays (circular queues) or linked lists.

Linked List

A linked list is an ADT where elements are stored in nodes, and each node contains a data value and a pointer (or link) to the next node in the list.

Linked lists provide dynamic memory allocation, meaning they can grow or shrink as needed. They are useful when the size of the data is not known in advance.

Operation	Description	Complexity
insert	Adds a new node to the list.	O(1) (if position is known), O(n) (if searching for position)
delete	Removes a node from the list.	O(1) (if node is known), O(n) (if searching for node)
search	Finds a node with a specific value.	O(n)
isEmpty	Checks if the list is empty.	O(1)

Implementation: Linked lists are typically implemented using pointers (references) to the next node in the sequence.