Abstract Data Types (ADT) Overview

Abstract Data Type (ADT) Definition

• An Abstract Data Type (ADT) is a specification for a data structure that defines its behavior but not its implementation.
• It encapsulates data and operations on that data, hiding the underlying representation.
• Users interact with an ADT through a well-defined interface, ignoring how the data is stored or manipulated internally.
• This allows for flexibility in implementation choices without affecting the way the ADT is used.

Characteristics of ADTs

• Abstraction: Hides the internal implementation details.
• Encapsulation: Bundles data and operations that act on the data within a single unit.
• Well-defined interface: Users interact with ADTs using specific operations (functions or methods).
• Data and operations: Defines the types of data to be stored and the allowed operations on that data.
• Implementation independence: The implementation can change without affecting user code.

Examples of ADTs

• Stack:

  • A data structure that stores elements in a last-in, first-out (LIFO) order.
  • Key operations: push (add an element), pop (remove and return the top element), peek (return the top element without removing), isEmpty (check if empty), isFull (check if full).

• Queue:

  • A data structure that stores elements in a first-in, first-out (FIFO) order.
  • Key operations: enqueue (add an element), dequeue (remove and return the front element), peek (return the front element without removing), isEmpty (check if empty), isFull (check if full).

• List:

  • A linear collection of elements, where elements can be accessed by their position.
  • Key operations: insert, delete, access (using index), search.

• Set:

  • A collection of unique elements.
  • Key operations: add, remove, contains, isEmpty, size.

• Map/Dictionary:

  • A collection of key-value pairs, where each key is unique.
  • Key operations: put (add a key-value pair), get (return the value for a specific key), remove (remove a key-value pair), containsKey (check if a key exists).

• Tree:

  • A hierarchical data structure, typically with a root node and branches of nodes.
  • Key operations: insert, delete, search, traverse (inorder, preorder, postorder).

• Graph:

  • A collection of nodes (vertices) connected by edges.
  • Key operations: add node, add edge, traverse (depth-first search, breadth-first search).

• Priority Queue:

  • Queue where each element has an associated priority. The highest priority element is retrieved first.
  • Key operations: insert, remove (retrieve the highest priority element), peek (get highest priority element without removal), isEmpty, size.

• Circular Buffer/Queue:

  • A buffer or queue whose last element is connected to the first element.
  • Useful for simulating cyclic or continuous data streams.

Importance of ADTs

• Modularity: Breaks down complex data structures into manageable components.
• Maintainability: Easier to change or update the implementation without affecting the rest of the code.
• Reusability: Can be used in different parts of a program or even in different programs without modification.
• Abstraction: Handles the complexity of data structures.
• Security: By hiding implementation details, prevents unauthorized access to internal data.