Back to Study Material Data Structures and Algorithms

Abstract Data Types

An Abstract Data Type, or ADT, defines a data structure purely in terms of what operations it supports and what those operations are supposed to do, withou...

Abstract Data Types

Separating Interface from Implementation in Data Structures

An Abstract Data Type, or ADT, defines a data structure purely in terms of what operations it supports and what those operations are supposed to do, without specifying how those operations are implemented internally. The concept separates the interface, the what, from the implementation, the how.

A stack ADT, for instance, specifies three operations: push, which adds an element to the top; pop, which removes and returns the top element; and peek, which returns the top element without removing it. The ADT also specifies the behavioral contract: push followed by pop returns the pushed element, and pop on an empty stack is an error. This contract holds regardless of whether the stack is implemented with an array, a linked list, or any other underlying structure.

This separation provides several engineering benefits. Code that uses a stack depends only on the ADT contract, not on the implementation details. You can swap one implementation for another, say replacing an array-based stack with a linked-list-based stack, without changing any of the calling code. This is the Liskov Substitution Principle applied to data structures.

ADTs also serve as a communication tool. When designing a system, engineers can agree on an ADT interface before any implementation is written. One developer can implement the data structure while another writes code that uses it, and both can proceed in parallel because the contract is clear.

Common ADTs and their typical implementations: the Queue ADT is implemented with arrays (circular buffer) or linked lists. The Priority Queue ADT is typically implemented with a binary heap. The Map ADT, also called a dictionary or associative array, is implemented with hash tables for O(1) average operations or balanced binary search trees for O(log n) guaranteed operations. The Set ADT shares many implementations with the Map ADT since a set is essentially a map with keys but no associated values.

Languages formalize ADTs through interfaces, abstract classes, or protocols. Java's java.util.List is an interface specifying the List ADT; ArrayList and LinkedList are two concrete implementations. Python's collections.abc module defines abstract base classes for common ADTs.

Worked example: a to-do application needs to store tasks and retrieve the highest-priority one. Using a Priority Queue ADT, the application code calls insert and extract-max without caring whether the implementation is a binary heap, a Fibonacci heap, or a sorted list. Switching from a O(n) sorted-list implementation to a O(log n) binary heap later requires changing only the ADT implementation, not the application code.

Interview tip: when describing a solution, name the ADT first and the concrete implementation second. Saying "I will use a priority queue, implemented as a min-heap" demonstrates that you understand both levels of abstraction.