Abstract Data Type

TL;DR

  • It is an abstract black box:

    • With language details -> not ADT

    • With implementation details -> not ADT

    • With internal details -> not ADT

  • It is a data type:

    • Not used to keep data -> not ADT

  • ADTs covered in our courses:

    • List

    • Stack

    • Queue

    • Deque

    • Priority Queue

    • Map

    • Set

Definition

An Abstract Data Type (ADT) is a high-level mathematical model that defines a set of data values and a set of operations that can be performed on those values, without specifying how the data is represented or how the operations are implemented. It provides a clear interface for interacting with data, allowing programmers to focus on the functionality of the data structure rather than its implementation details. ADTs are essential in computer science for organizing and managing data efficiently, and common examples include stacks, queues, lists, and trees.

Context

  • High-level abstraction of data structures.

  • Usually defined as Interface in various programming languages.

  • May have multiple implementations.

Characteristics

  • Encapsulation: ADTs encapsulate data and operations into a single unit, providing a well-defined interface for interacting with the data while hiding the internal details. This concept is closely related to the idea of data abstraction.

  • Implementation independence: ADTs are independent of their implementation, meaning that the interface is defined in such a way that it does not depend on the underlying implementation. This allows the implementation to be changed without affecting the interface.

  • Abstraction: ADTs abstract away the low-level details of data manipulation, focusing on high-level behaviors and operations. This abstraction simplifies complex data structures and algorithms, making them easier to understand and use.

  • Modularity: ADTs promote modular design by encapsulating data and operations within a self-contained unit. This modular approach enhances code organization and maintainability.

Describing ADTs

  • Describe by interface as a set of operations.

  • For each operation, describe its behavior.

    • What does it do?

    • What are its parameters?

    • What are its return values?

    • What are its preconditions?

    • What are its postconditions?

    • Do not describe how it is implemented.

Example: Stack ADT

  • We do not describe how the data is stored or how the operations are implemented. So it is not accurate to say that a stack is like a stack of items that you can only add and remove from the top. This is an implementation detail, not part of the ADT.

  • The only essential information is FILO (First in last out)

  • Operations:

    • push(item)

      • Behavior: Pushes an item into the stack.

      • Parameters: item - the item to be pushed.

      • Returns: None.

      • Preconditions: None.

      • Postconditions: item is added to the stack.

    • pop()

      • Behavior: Removes and returns the last item that is pushed into the stack. (FILO)

      • Parameters: None.

      • Returns: The last item that is pushed into the stack.

      • Preconditions: The stack is not empty.

      • Postconditions: The last item that is pushed into the stack is removed.

    • peek()

      • Behavior: Returns the item the last item that is pushed into the stack without removing it.

      • Parameters: None.

      • Returns: The last item that is pushed into the stack.

      • Preconditions: The stack is not empty.

      • Postconditions: None.

    • isEmpty()

      • Behavior: Returns whether the stack is empty.

      • Parameters: None.

      • Returns: True if the stack is empty, False otherwise.

      • Preconditions: None.

      • Postconditions: None.