Abstract Data Types (ADT) — The Missing Mental Model

We've established that Abstract Data Types are defined by their operations—not by how they're stored or implemented. Now let's see this principle in vivid detail by examining one of the most ubiquitous ADTs in programming: the List.

The List ADT appears in virtually every programming language and underlies countless applications. Yet most developers interact with Lists without fully appreciating what operations define it, what contracts those operations establish, and why those definitions matter independently of implementation.

This page will dissect the List ADT operation by operation, showing how each contributes to defining what a List is. By the end, you'll understand that a List is not "a thing made of arrays or nodes"—it's an ordered, indexed collection with specific behavioral guarantees. The implementation is merely how those guarantees are fulfilled.

Before examining individual operations, let's establish the List ADT's core identity:

The List ADT represents an ordered, indexed collection of elements where:

• Elements are arranged in a linear sequence
• Each element occupies a specific position (index), starting from 0
• Elements can be added, removed, and accessed by position
• Duplicate elements are permitted
• The collection can grow and shrink dynamically

This description captures the essence of a List—but notice what it does NOT say:

• It doesn't mention arrays or memory layout
• It doesn't specify whether access is O(1) or O(n)
• It doesn't describe how insertion shifts elements or modifies pointers
• It doesn't commit to any storage mechanism

All of those are implementation concerns, not part of the ADT itself.

The List ADT vs. Similar ADTs:

It helps to contrast List with related ADTs to sharpen our understanding:

The List's distinctive features are:

1. Position-based access — You can directly access any element by its index
2. Insertion at any position — Unlike Stack/Queue which restrict where you add/remove
3. Order preservation — The sequence of elements is maintained; element 0 before element 1, etc.

These characteristics emerge from the List's operations, which we'll now examine in detail.

Every ADT has a set of core operations—the minimal set that defines its essential nature. For the List ADT, these core operations are:

Let's examine each core operation in detail:

add(element) — Append to End

Operation: add(e)

Precondition:
  - None (can add to empty or non-empty list)

Postcondition:
  - Element e is now at position size()-1 (the last position)
  - All existing elements retain their original indices
  - size() increases by 1

Behavior:
  - The list [A, B, C] after add(D) becomes [A, B, C, D]
  - D is now at index 3
  - Indices of A (0), B (1), C (2) unchanged

get(index) — Access by Position

Operation: get(i) → e

Precondition:
  - 0 ≤ i < size()  // Valid index range

Postcondition:
  - Returns element at position i
  - List is unchanged (this is a pure query)

Error Behavior:
  - If i < 0 or i ≥ size(): IndexOutOfBoundsException

Behavior:
  - List [A, B, C]: get(0)→A, get(1)→B, get(2)→C, get(3)→Error

set(index, element) — Modify by Position

Operation: set(i, e)

Precondition:
  - 0 ≤ i < size()  // Valid index range

Postcondition:
  - Element at position i is now e
  - Size unchanged
  - All other elements unchanged

Typically Returns:
  - The old element that was replaced (useful for undo operations)

Behavior:
  - List [A, B, C]: after set(1, X): [A, X, C]
  - Old element B may be returned

remove(index) — Delete by Position

Operation: remove(i)

Precondition:
  - 0 ≤ i < size()  // Valid index range

Postcondition:
  - Element at position i is removed
  - Elements at positions i+1, i+2, ... shift down by 1
  - size() decreases by 1

Typically Returns:
  - The removed element

Behavior:
  - List [A, B, C, D]: after remove(1): [A, C, D]
  - C moves from index 2 to index 1
  - D moves from index 3 to index 2

size() — Query Count

Operation: size() → n

Precondition:
  - None

Postcondition:
  - Returns the current count of elements (n ≥ 0)
  - List is unchanged

Invariant:
  - After any add: new_size = old_size + 1
  - After any remove: new_size = old_size - 1
  - Empty list: size() = 0

Beyond core operations, most List implementations provide extended operations for convenience. These are derivable from core operations but provided directly for usability:

Why Extended Operations Exist:

You could implement contains(e) using only core operations:

def contains(self, element):
    for i in range(self.size()):
        if self.get(i) == element:
            return True
    return False

But providing it directly offers advantages:

1. Clarity — list.contains(x) is more readable than a loop
2. Optimization — The implementation might have a faster way than iteration
3. Consistency — Same method name across all List implementations

Important Distinction:

Extended operations don't add to the ADT's definition—they're conveniences built atop the core. However, they may have different performance characteristics depending on implementation:

Even though both provide identical behavior, performance differs based on underlying structure.

The add(index, element) Operation — Insert at Position:

Operation: add(i, e)

Precondition:
  - 0 ≤ i ≤ size()  // Note: i = size() means append

Postcondition:
  - Element e is now at position i
  - Elements formerly at positions i, i+1, ... shift to i+1, i+2, ...
  - size() increases by 1

Behavior:
  - List [A, B, C]: after add(1, X): [A, X, B, C]
  - X is inserted at index 1
  - B moves from index 1 to index 2
  - C moves from index 2 to index 3
  - add(0, e) inserts at front
  - add(size(), e) is equivalent to add(e) — appends to end

This operation is particularly interesting because it shows how the List maintains its ordering invariant: elements shift to make room, preserving relative order of existing elements.

Beyond individual operations, the List ADT is defined by invariants—properties that always hold, no matter what sequence of operations is performed. These invariants distinguish List from other ADTs.

Why Invariants Matter:

Invariants are the rules of the game. They're what clients rely on:

# Client relies on contiguous indexing invariant
for i in range(list.size()):
    print(list.get(i))  # This MUST work for all i in range

# Client relies on order preservation
list.add("first")
list.add("second")
assert list.get(0) == "first"   # Order is preserved
assert list.get(1) == "second"  # Not scrambled

# Client relies on size consistency
initial_size = list.size()
list.add("new")
assert list.size() == initial_size + 1  # Size updated correctly

If an implementation violated any invariant, client code would break. For example:

• If indices had gaps, the traversal loop would crash or miss elements
• If order wasn't preserved, sorted data would become unsorted
• If size() was inaccurate, loops would terminate early or overflow

For those who appreciate mathematical rigor, we can specify the List ADT using equational axioms. These axioms define List behavior precisely and independently of any implementation.

Signature (Operations):

SORT    List[E]                        -- A List containing elements of type E
NEW     empty()         -> List        -- Create empty list
MUTATOR add(List, E)    -> List        -- Add element to end
MUTATOR addAt(List, N, E)  -> List     -- Add element at index
MUTATOR remove(List, N)    -> List     -- Remove element at index
MUTATOR set(List, N, E)    -> List     -- Set element at index
QUERY   get(List, N)       -> E        -- Get element at index
QUERY   size(List)         -> N        -- Count of elements
QUERY   isEmpty(List)      -> Bool     -- Check if empty

What These Axioms Achieve:

These axioms completely specify List behavior:

• Axioms 1-5: Define how each operation affects size
• Axioms 6-7: Define emptiness in terms of operations
• Axioms 8-11: Define positional access and modification
• Axioms 12-14: Define how insertion shifts elements
• Axioms 15-16: Define how removal shifts elements
• Axioms 17-18: Define error conditions

Example Derivation:

Let's trace: get(add(add(empty(), 'A'), 'B'), 0)

get(add(add(empty(), 'A'), 'B'), 0)
= get(add([A], 'B'), 0)           -- Inner add produces [A]
= get([A], 0)  by Axiom 9          -- 0 < size([A])=1, so get from inner
= 'A'                              -- Element at index 0

Verification: Starting with empty list, we added 'A' (index 0), then 'B' (index 1). get(0) should return 'A'. ✓

The List ADT can be implemented with fundamentally different data structures, each satisfying the same behavioral contract but with different performance trade-offs.

Implementation 1: Dynamic Array (ArrayList)

class ArrayList:
    def __init__(self):
        self._data = [None] * 10   # Initial capacity
        self._size = 0              # Actual element count
    
    def add(self, element):
        if self._size == len(self._data):
            self._resize()           # Double capacity when full
        self._data[self._size] = element
        self._size += 1
    
    def get(self, index):
        if not 0 <= index < self._size:
            raise IndexError()
        return self._data[index]     # Direct array access
    
    def remove(self, index):
        if not 0 <= index < self._size:
            raise IndexError()
        # Shift elements left
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        self._size -= 1
    
    def size(self):
        return self._size

Key Characteristics:

• Contiguous memory storage
• O(1) access by index (direct calculation: address = base + index * element_size)
• O(n) insertion/removal in middle (elements must shift)
• O(1) amortized append (occasional resize is O(n))
• Cache-friendly: elements are adjacent in memory

Implementation 2: Linked List (LinkedList)

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self._head = None
        self._size = 0
    
    def add(self, element):
        new_node = Node(element)
        if self._head is None:
            self._head = new_node
        else:
            current = self._head
            while current.next:
                current = current.next
            current.next = new_node
        self._size += 1
    
    def get(self, index):
        if not 0 <= index < self._size:
            raise IndexError()
        current = self._head
        for _ in range(index):
            current = current.next
        return current.value
    
    def remove(self, index):
        if not 0 <= index < self._size:
            raise IndexError()
        if index == 0:
            self._head = self._head.next
        else:
            current = self._head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next
        self._size -= 1
    
    def size(self):
        return self._size

Key Characteristics:

• Non-contiguous memory (nodes scattered)
• O(n) access by index (must traverse from head)
• O(1) insertion/removal IF you have the node reference (just rewire pointers)
• O(n) to find position for insertion/removal
• Not cache-friendly: nodes may be scattered in memory

The true power of thinking in ADTs is that client code can be written against the List interface without any knowledge of—or dependence on—the implementation.

Example: ADT-Focused Code

// This code works with ANY List implementation
public class ListProcessor {
    
    public static <T> T findLast(List<T> list) {
        if (list.isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        return list.get(list.size() - 1);
    }
    
    public static <T> void removeDuplicates(List<T> list) {
        Set<T> seen = new HashSet<>();
        int i = 0;
        while (i < list.size()) {
            if (seen.contains(list.get(i))) {
                list.remove(i);  // Don't increment i; next element slides to i
            } else {
                seen.add(list.get(i));
                i++;
            }
        }
    }
    
    public static <T> List<T> reverse(List<T> list) {
        List<T> reversed = new ArrayList<>();  // Could parameterize this too
        for (int i = list.size() - 1; i >= 0; i--) {
            reversed.add(list.get(i));
        }
        return reversed;
    }
}

Note what this code does NOT do:

• It doesn't check if it's an ArrayList or LinkedList
• It doesn't access any internal arrays or nodes
• It doesn't rely on any implementation-specific behavior
• It uses ONLY the List ADT operations

Switching Implementations:

Because ListProcessor depends only on the List ADT, we can use it with any implementation:

public class Main {
    public static void main(String[] args) {
        // Works with ArrayList
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1); arrayList.add(2); arrayList.add(3);
        System.out.println(ListProcessor.findLast(arrayList));  // 3
        
        // Works identically with LinkedList
        List<Integer> linkedList = new LinkedList<>();
        linkedList.add(1); linkedList.add(2); linkedList.add(3);
        System.out.println(ListProcessor.findLast(linkedList));  // 3
        
        // Works with any future List implementation
        List<Integer> customList = new MyCustomList<>();  // Some new class
        customList.add(1); customList.add(2); customList.add(3);
        System.out.println(ListProcessor.findLast(customList));  // 3
    }
}

This is the payoff of ADT thinking:

1. ListProcessor code never changes regardless of implementation
2. We can optimize by switching implementations without touching client code
3. New List implementations work automatically
4. Testing can use mock List implementations
5. Different use cases can choose different implementations

The List ADT is universal, but its expression varies across languages. Understanding how different languages represent the same ADT deepens your appreciation of the abstraction.

Observations:

1. Languages with explicit interfaces (Java, C#) make the ADT visible in the type system. You can declare a variable of type List<T> without committing to an implementation.

2. Languages with duck typing (Python, JavaScript) rely on convention. If it has the right methods, it's a List—but there's no formal type checking.

3. Languages with templates/generics but no interfaces (C++, Go) often provide a single dominant implementation that becomes the de facto ADT representation.

The ADT Transcends Language:

Despite these differences, the concept of List is the same everywhere:

• An ordered sequence of elements
• Access by position (index)
• Insertion and removal at any position
• Dynamic size

Whether you write list.get(i) (Java) or list[i] (Python) or list.at(i) (C++), you're performing the same ADT operation. The syntax varies; the semantics are identical.

We've thoroughly examined the List ADT as a case study in operation-defined abstraction. Let's consolidate:

What's Next:

Now that we've seen how the List ADT can have multiple implementations, let's generalize this principle. The next page explores how the same ADT can be implemented with vastly different data structures—and how understanding this multiplicity enables informed trade-off decisions in real engineering.