Abstract Data Types (ADTs) - Notes
Definition:
An Abstract Data Type (ADT) is a logical description of how data is viewed and the operations that can be
performed on that data without specifying how the operations are implemented.
Characteristics of ADTs:
1. Abstraction: Focuses on what the data does, not how it works.
2. Encapsulation: Hides internal implementation details.
3. Modularity: Separates data structure's interface from implementation.
4. Reusability: Can be reused in various programs by changing the implementation.
Why Use ADTs?
- To simplify complex programs
- To improve code readability and maintainability
- To allow programmers to build efficient and error-free programs
- To ensure data integrity and security
Common Abstract Data Types:
1. List - A linear collection of elements (insert, delete, traverse)
2. Stack - LIFO structure (push, pop, peek)
3. Queue - FIFO structure (enqueue, dequeue, peek)
4. Deque - Double-ended queue (insertFront, insertRear, deleteFront, deleteRear)
5. Set - Unordered unique elements (add, remove, union, intersection)
6. Map/Dictionary - Key-value pair (insert, delete, search by key)
7. Tree - Hierarchical structure (insert, delete, search, traverse)
8. Graph - Nodes connected by edges (add/remove vertex or edge, traverse)
Examples of ADTs:
Stack: Operations - push(), pop(), peek(), isEmpty()
Abstract Data Types (ADTs) - Notes
Example: Undo feature in editors
Queue: Operations - enqueue(), dequeue(), isEmpty(), peek()
Example: Printer queue
List: Types - Singly linked list, doubly linked list, array list
Example: Music playlist
Difference Between ADT and Data Structure:
ADT:
- Defines what operations can be done
- Independent of programming language
- Focuses on interface
Data Structure:
- Defines how operations are implemented
- Language-specific implementation
- Focuses on implementation