Abstract Data Types (ADT) — The Missing Mental Model

The distinction between ADT and data structure isn't just a classification scheme—it embodies a deeper design principle that has shaped the last fifty years of software engineering: the separation of interface from implementation.

This principle is so fundamental that it appears under many names:

• Information Hiding (David Parnas, 1972)
• Encapsulation (Object-Oriented Programming)
• Abstraction (General Computer Science)
• Contract-Based Design (Design by Contract)
• Programming to Interfaces (SOLID Principles)

All of these are facets of the same insight: what a component does should be defined independently of how it does it. When you master this principle, you unlock the ability to build software that evolves gracefully rather than decaying into unmaintainable spaghetti.

Let's establish precise definitions before exploring implications:

Interface: The set of operations that a component exposes to the outside world, along with the contract specifying each operation's behavior (preconditions, postconditions, invariants).

Implementation: The internal mechanisms, data structures, algorithms, and code that fulfill the interface's contract.

Think of it this way:

• The interface is the promise
• The implementation is how you keep the promise

The ADT Connection:

An ADT is an interface specification. It defines what operations are available and what behavior they exhibit. A data structure (combined with algorithms) is an implementation that fulfills the ADT's contract.

So when we separated ADT from data structure in the previous page, we were separating interface from implementation. These are different vocabularies for the same fundamental distinction:

The ADT vocabulary emphasizes mathematical specification; the design vocabulary emphasizes software engineering practices. Both describe the same separation.

The separation of interface from implementation isn't just aesthetically pleasing—it solves real engineering problems that plagued early software development.

The Economic Argument:

Software costs are dominated by maintenance, not initial development. Studies consistently show that 70-90% of software lifecycle costs come after the initial release. This means:

1. Code will be read more often than written
2. Code will be changed more often than initially understood
3. Changes should be localized, not rippling through the entire system

Interface/implementation separation directly addresses point 3. When implementation details are hidden, changes to those details are local. Without this separation, changing an array to a linked list might require modifications throughout the codebase—wherever the internal structure was accessed.

The Ripple Effect Without Separation:

Imagine a system where everyone directly accesses data:

# Without separation: Everyone knows stack uses a list
def push_to_stack(stack, item):
    stack._data.append(item)  # Direct access

def pop_from_stack(stack):
    return stack._data.pop()  # Direct access

def peek_stack(stack):
    return stack._data[-1]  # Direct access to internal structure

Now suppose you want to change the internal representation from a Python list to a custom array for performance. You must find and modify EVERY location that accesses _data. In a large system, you'll miss some. Bugs ensue.

With Separation:

# With separation: Stack exposes only operations
def push_to_stack(stack, item):
    stack.push(item)  # Interface operation

def pop_from_stack(stack):
    return stack.pop()  # Interface operation

def peek_stack(stack):
    return stack.peek()  # Interface operation

Now changing the internal structure requires modifying only the Stack class itself. All client code continues working without changes.

An interface is more than a list of method signatures—it's a contract between the component and its users. This contract has multiple dimensions that together fully specify expected behavior.

Bertrand Meyer's Design by Contract:

Bertrand Meyer formalized this thinking in his "Design by Contract" (DbC) methodology. In DbC:

• Preconditions: The caller promises to satisfy these before calling. If violated, it's the caller's fault.
• Postconditions: The implementation promises to establish these upon return. If violated, it's the implementation's fault.
• Invariants: Both parties promise these hold at all observable moments.

This contract-based view transforms debugging. When something goes wrong, you can ask:

1. Were preconditions satisfied? → If not, the caller has a bug
2. Were preconditions satisfied but postconditions violated? → The implementation has a bug
3. Is an invariant broken? → Some operation violated the contract

Example: Full Contract for Stack.pop()

Operation: pop()

Precondition:
  - !isEmpty()  // Stack contains at least one element

Postcondition:
  - Returns element e such that:
    - e was the most recently pushed element not yet popped
  - After return:
    - size() == old(size()) - 1
    - e is no longer in the stack
    - Element that was second from top is now top (if it exists)

Invariant Maintained:
  - LIFO property: Next pop returns element pushed most recently among those remaining

Error Behavior:
  - If precondition violated: Throws EmptyStackException
  - No other exceptions possible from this operation

Performance:
  - Time: O(1)
  - Space: O(1) additional

This complete contract tells users everything they need to know to use pop() correctly—without revealing any implementation details.

Modern programming languages provide mechanisms to enforce the separation of interface from implementation. Understanding these mechanisms helps you apply the principle effectively in any language.

Java Example:

// Interface: Defines the contract (ADT specification)
public interface Stack<T> {
    void push(T item);
    T pop();
    T peek();
    boolean isEmpty();
    int size();
}

// Implementation 1: Array-based
public class ArrayStack<T> implements Stack<T> {
    private T[] data;       // Hidden: internal structure
    private int top;        // Hidden: implementation detail
    
    @Override
    public void push(T item) {
        // Implementation using array...
    }
    // ... other methods
}

// Implementation 2: Linked list-based
public class LinkedStack<T> implements Stack<T> {
    private Node<T> head;   // Hidden: different structure
    private int count;      // Hidden: different tracking
    
    @Override
    public void push(T item) {
        // Implementation using nodes...
    }
    // ... other methods
}

// Client code: Works with EITHER implementation
public void processStack(Stack<Integer> stack) {
    stack.push(1);
    stack.push(2);
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    }
}

The processStack method accepts any Stack<Integer>. The client doesn't know—and shouldn't care—whether it receives an ArrayStack or LinkedStack. This is the power of separation.

Python Example (Using ABC):

from abc import ABC, abstractmethod

# Interface (Abstract Base Class)
class Stack(ABC):
    @abstractmethod
    def push(self, item): pass
    
    @abstractmethod
    def pop(self): pass
    
    @abstractmethod
    def peek(self): pass
    
    @abstractmethod
    def is_empty(self) -> bool: pass

# Implementation
class ListStack(Stack):
    def __init__(self):
        self._data = []  # Private by convention
    
    def push(self, item):
        self._data.append(item)
    
    def pop(self):
        return self._data.pop()
    
    def peek(self):
        return self._data[-1]
    
    def is_empty(self) -> bool:
        return len(self._data) == 0

The interface/implementation separation leads directly to one of the most important principles in object-oriented design: the Liskov Substitution Principle (LSP).

Liskov Substitution Principle: If S is a subtype of T, then objects of type T may be replaced with objects of type S without altering any of the desirable properties of the program.

In practical terms: if your code works with a Stack interface, it should work correctly with ANY implementation of Stack—ArrayStack, LinkedStack, or any future implementation. The implementation can be substituted without breaking the program.

Why LSP Matters for ADTs:

LSP is the guarantee that interface/implementation separation actually works. If different implementations could behave differently in ways that break clients, the separation would be pointless.

For LSP to hold, implementations must:

1. Honor the contract — Every precondition, postcondition, and invariant must be respected
2. No additional preconditions — An implementation can't require more than the interface specifies
3. No weakened postconditions — An implementation must provide at least what the interface promises
4. Preserve invariants — All invariants of the interface must hold in the implementation

Real-World LSP Violations:

The classic example is the Square/Rectangle problem:

class Rectangle {
    protected int width, height;
    
    public void setWidth(int w) { width = w; }
    public void setHeight(int h) { height = h; }
    public int area() { return width * height; }
}

// LSP Violation: Square changes Rectangle's behavior
class Square extends Rectangle {
    @Override
    public void setWidth(int w) { width = w; height = w; }  // Also sets height!
    @Override
    public void setHeight(int h) { width = h; height = h; } // Also sets width!
}

Rectangle has an implicit contract: setWidth() changes only width, setHeight() changes only height. Square violates this. If client code relies on this contract:

void resizeRectangle(Rectangle r) {
    r.setWidth(10);
    r.setHeight(5);
    assert r.area() == 50;  // Fails if r is a Square!
}

Square is not truly substitutable for Rectangle, despite inheritance. LSP is violated.

The Lesson: Inheritance is not about 'is-a' relationships from the real world. It's about behavioral substitutability. A square is a rectangle geometrically, but a Square object cannot substitute for a Rectangle object if Rectangle has mutable dimensions.

A direct application of interface/implementation separation is the practice of programming to interfaces. This principle, canonized in the Gang of Four's Design Patterns book, states:

Program to an interface, not an implementation. Clients should depend on abstract interfaces rather than concrete classes.

In code, this means preferring:

// Good: Depends on interface
List<String> names = new ArrayList<>();  // Variable type is List, not ArrayList

void processList(List<String> items) {   // Parameter type is List, not ArrayList
    // Works with ANY List implementation
}

Over:

// Less flexible: Depends on implementation
ArrayList<String> names = new ArrayList<>();  // Variable type is ArrayList

void processList(ArrayList<String> items) {   // Only works with ArrayList
    // Cannot pass LinkedList, even though it has same operations
}

Practical Guidelines:

1. Declare variables with interface types — Use List, Set, Map, not ArrayList, HashSet, HashMap.

2. Accept interface types in method parameters — This maximizes flexibility for callers.

3. Return interface types from methods — This lets you change implementations without breaking callers.

4. Instantiate concrete types only at creation — The new ArrayList<>() is the one place you commit to an implementation.

5. Push implementation choice to configuration — Dependency injection and factory patterns can make even creation abstract.

Exception: When Implementation Matters

Sometimes you genuinely need a specific implementation's behavior:

// LinkedList has addFirst/addLast that List doesn't
LinkedList<String> list = new LinkedList<>();
list.addFirst("first");  // Not available on List interface

// TreeMap guarantees sorted iteration that Map doesn't
TreeMap<String, Integer> orderedMap = new TreeMap<>();
// Clients that need ordering use TreeMap specifically

In these cases, use the specific type—but understand you're accepting tighter coupling for specific capabilities.

David Parnas formalized interface/implementation separation as the Information Hiding Principle in his influential 1972 paper. His insight went beyond simply separating concerns—it provided guidance on what to hide.

Information Hiding Principle: Modules should be designed so that the information (data structures and algorithms) contained within a module is inaccessible to other modules that have no need for such information.

What should be hidden? Parnas identified design decisions that are likely to change as the primary candidates for hiding. If a decision might change later, hide it behind an interface.

Parnas's Decomposition Criteria:

Parnas argued that modules should be decomposed not by workflow ('first we do A, then B, then C') but by secrets:

• Each module hides a design decision
• The module's interface reveals nothing about that decision
• Changes to the decision affect only that module

This was revolutionary. Previous practice decomposed by flow (input module, processing module, output module). Parnas showed that decomposition by secrets led to more maintainable systems.

Example: A Logging System

Bad decomposition (by flow):

• Module 1: Read configuration
• Module 2: Format message
• Module 3: Write to file

Change the storage from file to database: Modules 1 and 3 likely need changes. The 'secret' (storage mechanism) is spread across modules.

Good decomposition (by secret):

• Config Module: Hides where/how configuration is stored
• Format Module: Hides message formatting rules
• Storage Module: Hides where logs are persisted

Change storage from file to database: Only the Storage Module changes. The secret is encapsulated.

Let's walk through designing a component with proper interface/implementation separation. We'll design a Cache for a web application.

Step 1: Identify the Required Operations (Define the Interface)

How will the cache be used? What operations are needed?

Cache ADT Operations:
  - get(key) -> value or null    // Retrieve cached value
  - put(key, value)              // Store value
  - contains(key) -> boolean     // Check if key exists
  - remove(key)                  // Evict specific key
  - clear()                      // Evict everything
  - size() -> int                // Number of entries

These operations define the interface—what clients will use.

Step 2: Identify What to Hide (Design Decisions)

What implementation decisions might change?

• Storage mechanism: In-memory HashMap? Redis? Memcached?
• Eviction policy: LRU? LFU? Time-based expiration?
• Capacity limits: How many entries? How much memory?
• Serialization: How are values stored if external system?
• Thread safety: Synchronized? Lock-free? Single-threaded assumption?

All of these should be hidden behind the interface.

Step 3: Define the Interface in Code

public interface Cache<K, V> {
    V get(K key);
    void put(K key, V value);
    boolean contains(K key);
    void remove(K key);
    void clear();
    int size();
}

Note what the interface does NOT include:

• No mention of eviction policy
• No mention of storage mechanism
• No configuration for capacity
• No details about thread safety

These are implementation concerns, not interface concerns.

Step 4: Implement with Different Strategies

// Implementation 1: Simple HashMap-based
public class HashMapCache<K, V> implements Cache<K, V> {
    private final Map<K, V> store = new HashMap<>();
    
    public V get(K key) { return store.get(key); }
    public void put(K key, V value) { store.put(key, value); }
    // ... other methods
}

// Implementation 2: LRU eviction
public class LRUCache<K, V> implements Cache<K, V> {
    private final LinkedHashMap<K, V> store;  // Ordered for LRU
    private final int capacity;
    
    // Custom implementation with eviction logic
}

// Implementation 3: Redis-backed
public class RedisCache<K, V> implements Cache<K, V> {
    private final RedisClient client;
    private final Serializer<V> serializer;
    
    // Delegates to external Redis instance
}

Step 5: Clients Use the Interface

public class UserService {
    private final Cache<Long, User> userCache;
    
    // Constructor accepts any Cache implementation
    public UserService(Cache<Long, User> cache) {
        this.userCache = cache;
    }
    
    public User getUser(Long id) {
        User cached = userCache.get(id);
        if (cached != null) return cached;
        
        User fromDb = loadFromDatabase(id);
        userCache.put(id, fromDb);
        return fromDb;
    }
}

The UserService works with ANY Cache implementation. Today you use HashMapCache for development, LRUCache for production, RedisCache for distributed systems—the service code never changes.

We've explored the principle that underlies ADT thinking and shapes all of modern software design. Let's consolidate:

What's Next:

Now that we understand interface/implementation separation, let's see it in action with a detailed example. The next page examines the List ADT—exploring its operations, how those operations define what a List is, and how multiple implementations (ArrayList, LinkedList) provide the same abstraction with different trade-offs.