Algorithmic Foundations

Abstract Data Types

An abstract data type (ADT) is a contract — what operations exist and what they guarantee — decoupled from any specific data structure that implements it. List, Stack, and Map are ADTs; ArrayList, ArrayDeque, and HashMap are implementations.

An ADT specifies behavior (operations and their pre/post-conditions), never how it is stored
The same ADT can have wildly different implementations with different performance shapes — a Stack can sit on an array or a linked list
Java interfaces (List, Queue, Map) are the language mechanism for expressing an ADT; classes (ArrayList, LinkedList) are implementations
Programming against the ADT, not the implementation, is what lets you swap implementations later without touching callers
Choosing a data structure is really choosing an ADT first, then an implementation whose performance profile matches the workload

The distinction matters because it separates two different design questions. "What can I do with this collection?" is answered by the ADT — a Queue supports enqueue and dequeue, full stop. "How fast is each operation, and what is the memory shape?" is answered by the implementation — a queue backed by a circular array behaves very differently under contention or cache pressure than one backed by linked nodes, even though both satisfy the exact same Queue contract.

ADT vs. representative Java implementations
ADT	Core operations	Example implementations
Stack	push, pop, peek (LIFO)	array-backed, `ArrayDeque` used as a stack
Queue	enqueue, dequeue, peek (FIFO)	circular array, singly-linked list
Priority Queue	insert, extract-min/max	binary heap, balanced BST
Map	put, get, remove by key	hash table, balanced BST (sorted map)
Set	add, contains, remove, no duplicates	hash table, balanced BST

One ADT, two implementations, identical contract

interface IntStack {                 // the ADT: the contract, nothing about storage
    void push(int x);
    int pop();
    boolean isEmpty();
}

class ArrayIntStack implements IntStack {   // implementation A: contiguous array
    private int[] data = new int[16];
    private int size = 0;
    public void push(int x) { data[size++] = x; }   // O(1) amortized
    public int pop() { return data[--size]; }
    public boolean isEmpty() { return size == 0; }
}

class LinkedIntStack implements IntStack {  // implementation B: linked nodes
    private Node top;
    private record Node(int val, Node next) {}
    public void push(int x) { top = new Node(x, top); }  // O(1) worst case, one allocation
    public int pop() { int v = top.val(); top = top.next(); return v; }
    public boolean isEmpty() { return top == null; }
}