Core Principles of Abstract Data Types (ADTs)
High-Level Description
- An ADT (Abstract Data Type) describes:
- What operations can be performed.
- Not necessarily how they are implemented.
- Separates the logical view (concepts and operations) from the implementation (data structures, code).
Example
Stack (push/pop), Queue (enqueue/dequeue), Set (union/intersection).
Purpose of ADTs
- Provide a blueprint for data handling.
- Allow programmers to work with consistent interfaces while underlying implementation can change.
- Promote modularity and reusability in programming.
Underlying Mechanics
- Hash Tables
- Store data using a hash function to map keys → values.
- Must handle collisions (chaining, open addressing).
- Efficiency depends on load factor (ratio of stored elements to available slots).
- Sets as ADTs
- Built on top of arrays, linked lists, or hash tables.
- Ensure uniqueness and unordered nature of elements.
- Provide efficient operations for union, intersection, difference, membership.
Examples in Languages
- Java:
- HashMap<K,V> (key–value pairs).
- HashSet<E> (unique, unordered collection).
- Python:
- dict (dictionary for key–value pairs).
- set (for unordered, unique elements).
Exam technique
Always remember:
- ADT = idea, Implementation = concrete code.
- Stack is an ADT → can be implemented using array or linked list.
- Set is an ADT → implemented using hash tables in most languages.
Common Mistake
- Confusing ADT with data structure:
- ADT = concept (e.g., stack).
- Data structure = implementation (e.g., array-based stack, linked-list stack).
- Ignoring the importance of abstraction:
- Focusing too much on implementation details instead of understanding the ADT’s role.
- Forgetting efficiency factors:
- Hash tables may degrade in performance if load factor is too high.
- Poor hashing → too many collisions.
