10.4 Introduction to Abstract Data Types (ADT)

What is an Abstract Data Type (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 type does, rather than *how* it is implemented.

Think of an ADT as a blueprint. It specifies the behavior of a data structure without specifying the underlying implementation. This allows for flexibility in how the ADT is implemented (e.g., using an array, a linked list, etc.) without changing the interface.

Key characteristics of an ADT:

• Defined by a set of data.
• Defined by a set of operations.
• The behavior of each operation is specified.
• The internal implementation is hidden from the user.

Common Abstract Data Types

1. Stack

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

Common Stack Operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack.
• Peek (or Top): Returns the element at the top of the stack without removing it.
• isEmpty: Checks if the stack is empty.

Implementation Options:

• Array-based Stack: Uses an array to store elements.
• Linked List-based Stack: Uses a linked list to store elements.

2. Queue

A queue is an ADT that follows the First-In, First-Out (FIFO) principle. Imagine a queue of people – the first person in line is the first one served.

Common Queue Operations:

• enqueue: Adds an element to the rear of the queue.
• dequeue: Removes the element from the front of the queue.
• peek (or front): Returns the element at the front of the queue without removing it.
• isEmpty: Checks if the queue is empty.

Implementation Options:

• Array-based Queue: Uses an array to store elements (can be inefficient for large queues).
• Linked List-based Queue: Uses a linked list to store elements (more efficient).

3. 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 sequence. It does not require contiguous memory allocation.

Common Linked List Operations:

• insertAtBeginning: Adds a new node at the beginning of the list.
• insertAtEnd: Adds a new node at the end of the list.
• deleteNode: Removes a specified node from the list.
• search: Finds a node with a specific data value.

Implementation:

A linked list typically consists of a series of nodes. Each node contains:

• Data: The value stored in the node.
• Pointer (or link): A reference to the next node in the list.

Storing Data with ADTs

We can use the ADTs discussed above (stack, queue, linked list) to store data in various ways. The choice of ADT depends on the specific requirements of the application.

For example:

• Stack: Can be used to implement undo/redo functionality, function call stacks in programming languages, and expression evaluation.
• Queue: Can be used to manage tasks in a system, implement breadth-first search algorithms, and handle print queues.
• Linked List: Can be used to represent dynamic lists of data, implement stacks and queues, and create flexible data structures.

Comparison Table

Feature	Stack	Queue	Linked List
Data Order	LIFO	FIFO	Sequential (can be ordered based on pointers)
Insertion	Top	Rear	Can be inserted at any position
Deletion	Top	Front	Can be deleted from any position
Memory Allocation	Can be static or dynamic	Can be static or dynamic	Dynamic
Efficiency (Typical)	O(1) for push/pop	O(1) for enqueue/dequeue	O(1) for insertion/deletion at known position, O(n) for search