Introduction
An abstract data type (ADT) is a theoretical model that defines a set of data values and the operations that can be performed on them, without specifying how those operations are implemented internally. An ADT describes what a structure does (its interface and behavior), while a data structure describes how it is actually built in memory. This separation between interface and implementation is one of the most important ideas in computer science, because it allows programmers to reason about correctness at a high level while implementers remain free to choose the most efficient underlying representation.
Cricket analogy: The DRS review system is defined by its interface — raise the finger, ball-tracking confirms or overturns — while commentators never see the internal Hawk-Eye software; that split between contract and implementation is exactly what an ADT formalizes.
How It Works
Consider the Stack ADT: it is defined purely by its behavior — push (add an element to the top), pop (remove and return the top element), peek (view the top element without removing it), and isEmpty (check if the stack has elements) — with the rule that elements are removed in Last-In-First-Out (LIFO) order. Nothing in this definition says whether a stack must be built from an array or a linked list. A List ADT similarly defines operations like insert, remove, and get, without dictating whether the underlying structure is a dynamic array or a linked list. Different concrete data structures can implement the same ADT with different performance trade-offs: an array-backed stack offers fast access but may need resizing, while a linked-list-backed stack avoids resizing but uses more memory per element due to pointers. Common ADTs include Stack, Queue, List, Set, Map (Dictionary), and Priority Queue.
Cricket analogy: The Stack ADT's push/pop/peek/isEmpty behavior is like a fast bowler's over: only the last ball bowled (LIFO) is the one just reviewed on replay, whether the broadcast is built on Star Sports' or Sky's replay rig underneath.
Example
class ArrayStack:
"""Stack ADT implemented using a Python list (dynamic array)."""
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item) # O(1) amortized
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
return self._items.pop() # O(1)
def peek(self):
return self._items[-1]
def is_empty(self):
return len(self._items) == 0
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class LinkedListStack:
"""The SAME Stack ADT implemented using a singly linked list."""
def __init__(self):
self._top = None
def push(self, item):
self._top = Node(item, self._top) # O(1)
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
value = self._top.value
self._top = self._top.next
return value # O(1)
def peek(self):
return self._top.value
def is_empty(self):
return self._top is None
# Both classes expose the identical Stack ADT interface
for stack in (ArrayStack(), LinkedListStack()):
stack.push(1)
stack.push(2)
stack.push(3)
print(type(stack).__name__, "pops:", stack.pop(), stack.pop(), stack.pop())Analysis
Both ArrayStack and LinkedListStack fulfill the exact same Stack ADT contract: push, pop, peek, and is_empty behave identically from the caller's perspective, and both preserve LIFO order. Yet their internal implementations are completely different — one uses a contiguous, resizable array, and the other uses a chain of dynamically allocated nodes connected by pointers. A caller using either class through its public interface cannot tell which implementation is underneath, and does not need to. This is the power of the ADT abstraction: code written against the Stack interface continues to work correctly even if the implementation is later swapped for a more efficient one, as long as the new implementation still honors the same contract.
Cricket analogy: Two different bowling machines — one gear-driven, one pneumatic — can both deliver a perfect yorker to spec; the batsman facing them can't tell which mechanism produced the ball, just as callers can't tell ArrayStack from LinkedListStack.
Key Takeaways
- An ADT defines WHAT operations are available and their expected behavior, not HOW they are implemented.
- A data structure is a concrete implementation that realizes an ADT's behavior in memory.
- The same ADT (e.g. Stack) can be implemented by multiple different data structures (array or linked list) with different performance trade-offs.
- Common ADTs include Stack, Queue, List, Set, Map, and Priority Queue.
- Separating interface from implementation makes code more maintainable and swappable.
Practice what you learned
1. What best distinguishes an abstract data type (ADT) from a data structure?
2. Which of the following is an example of an abstract data type rather than a specific implementation?
3. In the code example, why can ArrayStack and LinkedListStack be used interchangeably by client code?
4. Which of these is NOT typically classified as an abstract data type?
Was this page helpful?
You May Also Like
Stacks
A LIFO data structure supporting O(1) push and pop, used for undo history, parsing, and recursion simulation.
Queues
A FIFO data structure supporting O(1) enqueue and dequeue, ideal for task scheduling and breadth-first traversal.
Introduction to Data Structures
A foundational overview of what data structures are, why they matter, and how they are classified.
Choosing the Right Data Structure
A practical decision framework for picking between arrays, linked lists, hash tables, trees, graphs, and heaps.