10.4 Introduction to Abstract Data Types (ADT)

What is an Abstract Data Type?

An Abstract Data Type (ADT) is a theoretical model of data structure that defines a set of operations and their behavior, without specifying how the data is stored. It focuses on what the data structure does, rather than how it is implemented.

Think of an ADT as a contract. It specifies the interface – the operations you can perform – and the expected results, but leaves the internal implementation details hidden.

This abstraction allows for flexibility in implementation. The same ADT can be implemented using different underlying data structures (e.g., an array, a linked list) without affecting the code that uses the ADT.

Examples of ADTs

Common examples of ADTs include stacks, queues, and linked lists. These are fundamental building blocks in computer science.

Stack

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

• Key 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.

Example Use Case: Function call stack in programming languages.

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.

• Key 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.

Example Use Case: Print queue, task scheduling in operating systems.

Linked List

A linked list is an ADT where elements are stored in nodes, and each node contains a data element and a pointer (or link) to the next node in the sequence. It's a linear collection of data.

• Key Operations:
• Insert: Adds a new node to the list.
• Delete: Removes a node from the list.
• Search: Finds a specific element in the list.
• Get (or Access): Retrieves an element at a specific position.

Example Use Case: Implementing stacks, queues, and other complex data structures; representing dynamic lists.

Table Summarizing ADTs

By using ADTs, programmers can write code that is more modular, easier to understand, and more maintainable. The focus on the interface allows for changes to the underlying implementation without affecting the rest of the program.