Scribd
Upload
6 views18 pages

Understanding Abstract Data Types (ADTs)

Module 1 focuses on Abstract Data Types (ADTs) and their role in managing software complexity through abstraction, modularity, and encapsulation. It defines ADTs as models characterized by a set of values and operations, and discusses various abstraction mechanisms like parameterization and specification. The module also covers types of abstraction, including procedural, data, type hierarchies, and iteration, alongside their implementation in concrete systems.

Uploaded by

23001003104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views18 pages

Understanding Abstract Data Types (ADTs)

Module 1 focuses on Abstract Data Types (ADTs) and their role in managing software complexity through abstraction, modularity, and encapsulation. It defines ADTs as models characterized by a set of values and operations, and discusses various abstraction mechanisms like parameterization and specification. The module also covers types of abstraction, including procedural, data, type hierarchies, and iteration, alongside their implementation in concrete systems.

Uploaded by

23001003104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Module 1: Abstract Data Types (ADTs)

Understanding Abstraction and Data Modeling


Why Study Abstract Data Types?
• Manage software complexity using
abstraction
• ADTs provide modularity and encapsulation
• Bridge between problem domain and
implementation
What is an Abstract Data Type?
• Definition: ADT is a model where behavior is
defined by a set of values and operations, not
by implementation.

• Example: Stack, Queue, List


• Formula: ADT = (Set of Values, Set of
Operations)
System Decomposition
• Break complex systems into smaller
components
• Each module has a clear responsibility
• Leads to modular and reusable systems

• Example: Bank → Accounts, Transactions,


Users
Concept of Abstraction
• Focus on essential details, ignore irrelevant
ones
• Hides internal implementation
• Types: Control, Data, Procedural, Iteration

Quote: 'Abstraction is selective ignorance.' –


Andrew Koenig
Abstraction Mechanisms
• Parameterization – making behavior generic
via parameters
• Specification – defining what a component
should do

• Both improve clarity and reusability


Parameterization Example
• Example:
• class Stack<T> {
• void push(T item);
• T pop();
• }

• Benefit: One template for multiple data types.


Specification Example
• Defines behavior through preconditions and
postconditions

• Operation: push(x)
• Precondition: Stack not full
• Postcondition: x is on top of stack

• Provides a formal contract for implementation.


Kinds of Abstraction
• 1. Procedural Abstraction
• 2. Data Abstraction
• 3. Type Hierarchies
• 4. Iteration Abstraction
Procedural Abstraction
• Define a procedure without exposing internal
logic
• Example: sort(data)

• The caller doesn’t know the algorithm used


(QuickSort or MergeSort)
Data Abstraction
• Represent data using an interface
• Example: Stack → push(), pop(), top()
• Implementation independent (array or linked
list)

• Encourages encapsulation
Type Hierarchies
• Organize related types hierarchically
• Example: Shape → Circle, Rectangle, Triangle

• Promotes code reuse and polymorphism


Iteration Abstraction
• Hide iteration mechanism from the user
• Example:
• for (x in stack): print(x)

• Simplifies traversal of collections


Implementing ADTs
• Concrete State Space – data representation
• Concrete Invariant – properties that always
hold true
• Abstraction Function – maps concrete to
abstract state
Concrete State Space
• Defines how data is stored internally.
• Example: Stack = Array + Top Index
• Ensures predictable operations.
Concrete Invariant
• Property that must always hold.
• Example: 0 ≤ top ≤ MAX_SIZE
• Violating invariants means an invalid state.
Abstraction Function
• Maps concrete implementation → abstract
model
• Example: A(Stack) = sequence of elements
from bottom to top
• Ensures behavior consistency.
Example: Stack ADT
Implementation
• Abstract Definition: push(), pop(), isEmpty()

• Concrete Implementation:
• class Stack {
• void push(int x) {...}
• int pop() {...}
• }

• Bridges abstract model and code.

You might also like