Q&A

What are abstract data types?

By AlgoInsight Team2026-06-18arraysdata-structuresoop

Overview

An ADT specifies the what - the operations and their semantics - and hides the how. The same ADT can have multiple concrete implementations with different performance trade-offs. This is the principle behind Java's List, Queue, and Map interfaces, Python's abstract base classes, and virtually every programming language's collection types.

graph TD
    A[Abstract Data Type] --> B[Defines: WHAT operations exist + their contracts]
    A --> C[Hides: HOW they are implemented]
    B --> D["Stack ADT: push, pop, peek, isEmpty"]
    D --> E[Implementation 1: array-based]
    D --> F[Implementation 2: linked-list-based]
    style A fill:#1e1b4b,color:#fff

Key ADTs and Their Operations

Stack (LIFO)

• push(element) - add to the top
• pop() - remove and return top element
• peek() - inspect top without removing
• isEmpty() - check if empty
• Invariant: the last element pushed is the first popped.

Queue (FIFO)

• enqueue(element) - add to the back
• dequeue() - remove from the front
• peek() - inspect front
• isEmpty()
• Invariant: first in, first out.

List (ordered, index-accessible)

• get(i), set(i, v), add(v), remove(i), size()
• Implementations: ArrayList (O(1) random access, O(n) insert), LinkedList (O(n) access, O(1) insert at head).

Map / Dictionary (key→value)

• put(k, v), get(k), remove(k), containsKey(k), keys(), values()
• Implementations: HashMap (O(1) average), TreeMap (O(log n), sorted keys).

Set

• add(v), remove(v), contains(v), size()
• Implementations: HashSet (O(1)), TreeSet (O(log n), sorted).

ADT vs Data Structure

ADT in Code: Interface as Contract

In Java, the interface is the ADT; the implementing class is the concrete data structure:

// ADT as interface:
interface Stack<T> {
    void push(T item);
    T pop();
    T peek();
    boolean isEmpty();
}

// Concrete implementation 1:
class ArrayStack<T> implements Stack<T> { /* array-based */ }

// Concrete implementation 2:
class LinkedStack<T> implements Stack<T> { /* linked-list-based */ }

Code that programs to the Stack interface works with either implementation.

In Python, ADTs are expressed through abc.ABC and abstractmethod, or informally via duck typing.

Why ADTs Matter

• Encapsulation - clients use operations, not internal details; the implementation can change without breaking callers.
• Polymorphism - any implementation satisfying the ADT contract can be substituted.
• Testing and reasoning - you can verify behavior against the ADT's contract independently of any implementation.
• Design vocabulary - "stack," "queue," "map" are universal concepts that communicate intent.

Why This Matters in Interviews

ADT questions test whether you think in abstractions before implementations. Know the core ADTs (stack, queue, list, map, set) and their canonical operations; understand the ADT = interface, data structure = implementation distinction; and articulate that the separation enables polymorphism and hides complexity. Connecting ADTs to language constructs (Java interfaces, Python ABCs) and explaining that different implementations (ArrayList vs LinkedList) trade off different complexities for the same ADT is the depth signal.

Common Pitfalls

• Confusing the ADT with a specific implementation (e.g. calling a LinkedList a "stack" without defining which operations you're using it as).
• Defining an ADT by its implementation details rather than its behavioral contract.
• Forgetting that the same concrete structure can implement multiple ADTs (e.g. ArrayDeque implements both Stack and Queue ADTs in Java).

References

• Abstract data type: https://en.wikipedia.org/wiki/Abstract_data_type
• Java Collections Framework (ADTs as interfaces): https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/package-summary.html

More answers