Abstract data type (ADT)

What is an Abstract Data Type?

An abstract data type is a high-level description of a set of values and the operations that can be performed on those values. It provides a logical blueprint for how data can be stored, accessed, and manipulated. The key idea behind ADTs is to separate the implementation details from the interface, allowing programmers to focus on the functionality rather than the underlying implementation.

ADTs are often compared to real-world objects. Just like a real-world object has properties and behaviours, an abstract data type has data and operations. For example, think of a car as an abstract data type. The properties of a car would include attributes such as colour, model, and year, while the behaviours would include actions like accelerating, braking, and changing gears.

Please note that we do NOT talk about [abstraction: abstract class and abstract methods]

Why are Abstract Data Types Important?

Abstract data types are important in programming for several reasons:

1. Modularity: ADTs promote modularity by encapsulating data and operations into a single unit. This allows programmers to break down complex problems into smaller, more manageable components.
2. Reusability: ADTs can be reused across different programs and projects. Once an ADT is implemented, it can be used in multiple contexts without having to rewrite the code.
3. Abstraction: ADTs provide a level of abstraction that simplifies the complexity of a program. By hiding the implementation details, ADTs enable programmers to focus on the essential aspects of the data and operations.
4. Maintainability: ADTs make code easier to maintain and debug. Since the implementation details are hidden, changes can be made to the underlying code without affecting the program’s overall functionality.

Common Examples of Abstract Data Types

There are several common examples of abstract data types that are used in programming:

1. Stack: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. It allows operations such as push (adding an element to the top) and pop (removing the top element).
2. Queue: A queue is a data structure that follows the First-In-First-Out (FIFO) principle. It allows operations such as enqueue (adding an element to the back) and dequeue (removing the front element).
3. Linked List: A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence.
4. Tree: A tree is a hierarchical data structure that consists of nodes connected by edges. It is commonly used for representing hierarchical relationships.
5. Graph: A graph is a collection of nodes (vertices) connected by edges. It is used to represent relationships between objects.

Implementing Abstract Data Types

There are various ways to implement abstract data types in programming languages. Some languages provide built-in support for certain ADTs, while others require custom implementations. Here are a few common approaches:

1. Using Class: Object-oriented programming languages such as C#, Python and PHP allow you to define classes that encapsulate data and operations. Each instance of the class represents a specific instance of the abstract data type.
2. Using Structure: Some programming languages, like C#, provide structures that can be used to define ADTs. Structs are similar to classes, but it is a value type while classes are a reference type.
3. Using Libraries: Many programming languages have libraries or frameworks that provide pre-implemented ADTs. These libraries can be imported and used directly in your code.

Abstract data type vs abstract class

• Model vs programming technique:
  [Abstract data type] is a mathematical model in computer science referring to a data structure, along with associated properties.
  [Abstract class] is a programming technique
• Think and talk vs write the code
  [Abstract data type] lets you think and talk about the solution of a problem
  [Abstract class] lets you write the code
• The common abstract data types are not abstract classes

Links

Code Examples

C#
using System.Collections;
Stack stack = new Stack();
stack.Push("A");
stack.Push("B");
int poppedItem = stack.Pop();

JavaScript
class Stack {
    constructor() {
        this.elements = [];
    }

    push(item) {
        this.elements.push(item);
    }

    pop() {
        if (this.elements.length === 0)
            throw new Error("Stack is empty");

        return this.elements.pop();
    }
}

// Usage
const stack = new Stack();
stack.push(10);
stack.push(20);
const poppedItem = stack.pop();

Python
class Stack:
    def __init__(self):
        self.elements = []

    def push(self, item):
        self.elements.append(item)

    def pop(self):
        if len(self.elements) == 0:
            raise IndexError("Stack is empty")
        return self.elements.pop()

PHP
<?php
class Stack {
    private $elements = [];

    public function push($item) {
        $this->elements[] = $item;
    }

    public function pop() {
        if (empty($this->elements))
            throw new Exception("Stack is empty");

        return array_pop($this->elements);
    }
}

// Usage
$stack = new Stack();
$stack->push(10);
$stack->push(20);
$poppedItem = $stack->pop();

Conclusion