Abstract Data Types (ADT) vs Data Structures | Data Structures

A common source of confusion in computer science is the distinction between an Abstract Data Type (ADT) and a Data Structure. While often used interchangeably, one represents the interface (what it does), and the other represents the implementation (how it works).

The Analogy: Interface vs Implementation

Think of an automobile:

The ADT: Steering wheel, brake pedal, gas pedal, gear selector. It defines the operations you can perform and their expected outcomes, without exposing mechanical engine details.
The Data Structure: Internal combustion engine, electric motor, mechanical cables, regenerative braking system. It is the concrete physical machinery executing those operations.

+-------------------------------------------------------+
|                Abstract Data Type (ADT)               |
|      Defines behavior: operations, inputs, outputs    |
|             (e.g., List, Queue, Stack, Map)           |
+-------------------------------------------------------+
                           |
            implemented by one or more
                           |
                           v
+-------------------------------------------------------+
|                    Data Structure                     |
|    Concrete memory layout, algorithmic instructions   |
|         (e.g., ArrayList, LinkedList, HashMap)        |
+-------------------------------------------------------+

Common ADTs and Their Concrete Implementations

Abstract Data Type (ADT)	Core Operations (Contract)	Possible Concrete Data Structures
List	`get(i)`, `add(item)`, `remove(i)`, `size()`	Dynamic Array (`ArrayList`), Singly Linked List, Doubly Linked List
Stack	`push(item)`, `pop()`, `peek()`, `isEmpty()`	Array with top index, Linked List with head pointer
Queue	`enqueue(item)`, `dequeue()`, `peek()`	Circular Array, Doubly Linked List
Priority Queue	`insert(item)`, `extractMax()` or `extractMin()`	Binary Heap, Fibonacci Heap, Sorted Array
Map / Dictionary	`put(k, v)`, `get(k)`, `remove(k)`, `containsKey(k)`	Hash Table (with chaining), Red-Black Tree, Trie
Set	`add(item)`, `contains(item)`, `remove(item)`	Hash Set (backed by Hash Table), Balanced BST (`TreeSet`), BitSet

Kotlin Code Example

In object-oriented programming, interfaces represent ADTs, while classes implement data structures:

// 1. ADT: Defines the public contract
interface StackADT<T> {
    fun push(element: T)
    fun pop(): T?
    fun peek(): T?
    fun isEmpty(): Boolean
}

// 2. Concrete Data Structure 1: Array-backed Stack
class ArrayStack<T>(private val capacity: Int = 10) : StackADT<T> {
    private val storage = arrayOfNulls<Any>(capacity)
    private var top = -1

    override fun push(element: T) {
        if (top == capacity - 1) throw IllegalStateException("Stack Overflow")
        storage[++top] = element
    }

    @Suppress("UNCHECKED_CAST")
    override fun pop(): T? {
        if (isEmpty()) return null
        return storage[top--] as T
    }

    @Suppress("UNCHECKED_CAST")
    override fun peek(): T? = if (isEmpty()) null else storage[top] as T
    override fun isEmpty(): Boolean = top == -1
}

// 3. Concrete Data Structure 2: Node-backed Stack
class LinkedStack<T> : StackADT<T> {
    private class Node<T>(val data: T, val next: Node<T>?)
    private var head: Node<T>? = null

    override fun push(element: T) {
        head = Node(element, head)
    }

    override fun pop(): T? {
        val value = head?.data ?: return null
        head = head?.next
        return value
    }

    override fun peek(): T? = head?.data
    override fun isEmpty(): Boolean = head == null
}

Why This Distinction Matters

Decoupling: Calling code relies only on ADT methods. You can swap an ArrayList for a LinkedList without changing business logic.
Performance Tuning: You can choose different concrete data structures depending on whether your workload is read-heavy or write-heavy.
Clean Architecture: Encourages programming to interfaces rather than concrete implementations.

Summary

An ADT specifies what operations are supported and their formal mathematical behavior.
A Data Structure defines how that data is physically stored in memory and algorithmically manipulated.