Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Data structures and abstract data types

Definitions, contrasts, and exam-ready specifications of Data Structures versus Abstract Data Types (ADTs), with axioms, invariants, abstraction functions, and small Python examples.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers design and choose data structures to make programs fast, memory‑efficient, and easy to maintain. Abstract Data Types (ADTs) let you specify what operations a structure must support without fixing how it is implemented, so you can swap implementations (array, linked list, tree, hash) without changing the rest of the code.

Key ideas

  • Interface: The list of operations of an ADT with their signatures (input/output types) and specifications (preconditions and postconditions). Example: For a Stack ADT: push(x), pop(), top(), isEmpty().
  • Implementation: A concrete data structure and algorithms that realize the ADT operations. Example: Implement Stack using a Python list or using a singly linked list.
  • Precondition: A condition that must be true before an operation is called. Example: For pop() on a stack, the precondition is stack is not empty.
  • Postcondition: A condition guaranteed to be true after an operation finishes if the precondition was true. Example: After push(x), x is on top of stack.
  • Representation: The internal data fields used by an implementation. Example: For a queue, representation could be an array with head and tail indices.
  • Encapsulation: Hiding representation and internal details so clients use only the interface. This reduces coupling and allows changing implementation without affecting users of the ADT.
  • Modularity: Splitting a program into parts (modules), each with a specific responsibility (e.g., an ADT module for stack), to improve maintainability, testing, and reuse.
  • Representation invariant (rep invariant): A condition over the internal representation that is always true whenever the object is visible to clients (before and after any public operation). Example: For an array‑based queue of capacity C, 0 ≤ size ≤ C and head, tail ∈ [0, C−1].
  • Abstraction function: A mapping from the internal representation to the abstract value that the ADT represents. It formally explains how to interpret the fields to get the abstract value. Example: For a stack implemented by an array A and top index t, the abstraction function maps (A, t) to the sequence [A[0], A[1], …, A[t−1]].
  • Algebraic specification (axiomatic specification): Defining an ADT by giving operation signatures and equations (axioms) that describe how operations relate to each other. Example axioms for a stack: top(push(S, x)) = x; pop(push(S, x)) = S.
  • Behavioral equivalence: Two implementations are behaviorally equivalent if, for all valid operation sequences, they produce the same externally visible results as specified by the ADT.
  • Linear vs. non‑linear data structures: Linear structures arrange elements in a sequence (array, list, stack, queue). Non‑linear structures arrange elements hierarchically or as networks (trees, graphs).
  • Static vs. dynamic data structures: Static structures have fixed size at compile time (e.g., statically allocated arrays). Dynamic structures can grow/shrink at runtime (linked lists, dynamic arrays).
  • Homogeneous vs. heterogeneous: Homogeneous structures store one type of data (array<int>). Heterogeneous can store different types, often via records/objects (structs) or tagged unions.
  • Ephemeral vs. persistent structures: Ephemeral are updated in place, keeping only the latest version. Persistent preserve older versions after updates (useful in functional programming and for undo).
  • Cost model (RAM model): Standard assumption for algorithm and data structure analysis: each basic operation on a word‑sized value costs O(1), and memory is uniformly accessible. We use this when comparing implementations (time/space trade‑offs). Detailed time analysis belongs under “Algorithm analysis: time and space complexity”.
  • Exact statements commonly required in exams:
    • Definition: “A Data Structure is a concrete organization of data and associated algorithms for accessing and modifying the data.”
    • Definition: “An Abstract Data Type (ADT) is a mathematical model of a data type that defines its domain of values and the set of operations on those values along with their semantics, independent of any representation.”
    • Theorem‑style claim (substitutability under encapsulation): If two implementations I1 and I2 of an ADT both satisfy the same external specification, and each implementation meets its own representation invariant and abstraction function correctness obligations, then any client that uses only the ADT interface cannot distinguish I1 from I2 by observable behavior. Assumption: clients call operations only when their preconditions hold.
  • How to derive a correct implementation from an ADT (steps universities often expect):
    1. Choose a representation: pick fields that can encode any abstract value.
    2. State the representation invariant.
    3. State the abstraction function mapping representation to abstract value.
    4. For each operation: write preconditions and postconditions from the ADT.
    5. Implement the operation and prove partial correctness: show that if the rep invariant holds before and the precondition is true, then after the code runs, the postcondition holds and the rep invariant is restored.
    6. Analyze time and space (refer to “Algorithm analysis: time and space complexity”).
  • Diagram to draw and label (Interface vs. Implementation): Draw two stacked boxes. Top box labelled “ADT Interface (operations, pre/post)”. Bottom box labelled “Implementation (representation + algorithms)”. An arrow from bottom to top labelled “abstraction function”. A loop arrow on the bottom box labelled “representation invariant holds before/after operations”. A client stick‑figure to the side with an arrow only to the top box labelled “uses operations”.
  • Example ADT algebraic specifications often asked:
    • Stack ADT (elements from set E):
      • Constructors/observers/mutators: empty : → Stack; push : Stack×E → Stack; pop : Stack → Stack (pre: not isEmpty); top : Stack → E (pre: not isEmpty); isEmpty : Stack → Bool.
      • Axioms:
        • isEmpty(empty) = true
        • isEmpty(push(S, x)) = false
        • top(push(S, x)) = x (pre: true)
        • pop(push(S, x)) = S (pre: true)
    • Queue ADT (FIFO):
      • empty, enqueue(Q, x), dequeue(Q) (pre: not isEmpty), front(Q) (pre: not isEmpty), isEmpty(Q).
      • Axioms:
        • isEmpty(empty) = true
        • isEmpty(enqueue(Q, x)) = false
        • front(enqueue(empty, x)) = x
        • front(enqueue(Q, x)) = front(Q) if not isEmpty(Q)
        • dequeue(enqueue(empty, x)) = empty
        • dequeue(enqueue(Q, x)) = enqueue(dequeue(Q), x) if not isEmpty(Q)
    • Set ADT (finite sets over universe U):
      • empty, insert(S, x), delete(S, x), member(S, x), size(S), union(S, T), intersect(S, T).
      • Axioms (samples): member(insert(S, x), x) = true; delete(insert(S, x), x) = S; size(insert(S, x)) = size(S) if member(S, x) else size(S)+1.

Formulas

- empty() → Stack<E>
- push(S: Stack<E>, x: E) → Stack<E>
- pop(S: Stack<E>) → Stack<E>  pre: not isEmpty(S)
- top(S: Stack<E>) → E         pre: not isEmpty(S)
- isEmpty(S: Stack<E>) → Bool
  • Queue ADT:
    • empty() → Queue<E>
    • enqueue(Q: Queue<E>, x: E) → Queue<E>
    • dequeue(Q: Queue<E>) → Queue<E> pre: not isEmpty(Q)
    • front(Q: Queue<E>) → E pre: not isEmpty(Q)
    • isEmpty(Q: Queue<E>) → Bool
  • Set ADT:
    • empty() → Set<U>
    • insert(S: Set<U>, x: U) → Set<U>
    • delete(S: Set<U>, x: U) → Set<U>
    • member(S: Set<U>, x: U) → Bool
    • union(S: Set<U>, T: Set<U>) → Set<U>
    • intersect(S: Set<U>, T: Set<U>) → Set<U>
    • size(S: Set<U>) → int
  • Proof obligations to remember when implementing an ADT:
    • Maintain representation invariant before and after every public operation.
    • Each operation must satisfy its precondition ⇒ postcondition as per the abstraction function.

Worked examples

  1. Model answer: Define DS vs. ADT, differentiate with examples, and draw a labelled diagram.
  • Definition of Data Structure: A data structure is a concrete organization of data in memory and the algorithms to operate on it. Examples: array, singly linked list, binary tree, hash table.
  • Definition of ADT: An Abstract Data Type is a mathematical model specifying the set of values and allowed operations, independent of implementation. Examples: Stack, Queue, Deque, Set, Map (Dictionary), Priority Queue.
  • Differences:
    • Level: DS is concrete; ADT is abstract.
    • Focus: DS focuses on representation and algorithms; ADT focuses on interface and semantics.
    • Substitutability: Multiple DS can implement the same ADT (e.g., Stack via array or linked list). Clients use only ADT operations, so implementations can be swapped.
    • Analysis: ADT defines what is correct; DS choice determines performance (time/space), analyzed under the RAM model.
  • Examples mapping ADT ↔ DS:
    • Stack ADT ← array with top index; or singly linked list with head at top.
    • Queue ADT ← circular array; or linked list with head and tail pointers.
    • Map (Dictionary) ADT ← hash table; or balanced search tree.
  • Diagram (describe to draw): Draw two stacked boxes. Top box: “ADT Interface: push, pop, top, isEmpty; pre/post”. Bottom box: “Array with top index t; algorithms for push/pop”. Arrow from bottom to top labelled “abstraction function (sequence A[0..t−1])”. Loop on bottom labelled “rep invariant: 0 ≤ t ≤ capacity”. A client stick‑figure to the side pointing to top box only.
  1. Algebraic specification with derivation: Stack ADT
  • Operations and preconditions:
    • empty : → Stack
    • push : Stack×E → Stack
    • pop : Stack → Stack pre: not isEmpty(S)
    • top : Stack → E pre: not isEmpty(S)
    • isEmpty : Stack → Bool
  • Axioms (complete set for exam answers):
    1. isEmpty(empty) = true
    2. isEmpty(push(S, x)) = false
    3. top(push(S, x)) = x
    4. pop(push(S, x)) = S
  • Derivation example (typical exam step): Prove that after n pushes on empty, size is n, where size can be defined by recursion:
    • Define size(empty) = 0; size(push(S, x)) = size(S) + 1.
    • Then by induction on n using the equations above, size(push(push(...push(empty, x1)..., xn))) = n.
  • Representation design sketch (array): representation is (A: array[E], t: int). Rep invariant: 0 ≤ t ≤ len(A). Abstraction function: Abs(A, t) = sequence [A[0], A[1], …, A[t−1]]. Operation proofs (sketch):
    • push: if t < len(A) then A[t]=x; t←t+1. Post: Abs(A, t_after) = Abs(A, t_before) ∘ [x]. Rep invariant holds since t_after ≤ len(A).
  1. Design an ADT with invariants and a small implementation: Rational numbers
  • Problem: Define an ADT Rational to represent fractions p/q with q ≠ 0, and implement add and multiply. Show rep invariant and abstraction function, and give runnable Python code with sample I/O.
  • ADT specification:
    • Values: all rational numbers ℚ.
    • Representation choice: pair of integers (num, den) with den ≠ 0.
    • Operations:
      • make(num: int, den: int) → Rational pre: den ≠ 0
      • add(r1, r2) → Rational
      • mul(r1, r2) → Rational
      • toFloat(r) → float
    • Rep invariant: den ≠ 0; gcd(|num|, |den|) = 1; den > 0 (canonical sign in numerator).
    • Abstraction function: Abs(num, den) = num/den ∈ ℚ.
    • Proof sketch of closure: For add and mul, resulting denominator ≠ 0. Reducing by gcd preserves value and rep invariant.
  • Python implementation (runnable):
from math import gcd

class Rational:
    def __init__(self, num: int, den: int):
        if den == 0:
            raise ValueError("denominator cannot be zero")
        # normalize sign to denominator > 0
        if den < 0:
            num, den = -num, -den
        g = gcd(abs(num), den)
        self._num = num // g
        self._den = den // g

    def add(self, other: "Rational") -> "Rational":
        # (a/b) + (c/d) = (ad+bc)/bd
        a, b = self._num, self._den
        c, d = other._num, other._den
        return Rational(a*d + b*c, b*d)

    def mul(self, other: "Rational") -> "Rational":
        # (a/b) * (c/d) = (ac)/(bd)
        a, b = self._num, self._den
        c, d = other._num, other._den
        return Rational(a*c, b*d)

    def to_float(self) -> float:
        return self._num / self._den

    def __str__(self) -> str:
        return f"{self._num}/{self._den}"

# Sample I/O demonstration
if __name__ == "__main__":
    r1 = Rational(2, 3)
    r2 = Rational(3, 4)
    s = r1.add(r2)
    p = r1.mul(r2)
    print(r1)        # expected 2/3
    print(r2)        # expected 3/4
    print(s)         # expected 17/12
    print(p)         # expected 1/2
    print(f"s≈{s.to_float():.6f}")
  • Sample input and exact output:
    • (Program has no stdin; it constructs objects. Output:)
2/3
3/4
17/12
1/2
s≈1.416667
  • Notes linking to ADT concepts: The class hides representation (encapsulation). The rep invariant is enforced by constructor normalization. Abstraction function maps fields to the mathematical rational value.
  1. Short implementation example for an ADT via multiple data structures: Stack
  • Requirement: Same Stack ADT API; two implementations: array‑based and list‑based. Show that clients can use either without change.
  • Array‑based stack (Python):
class ArrayStack:
    def __init__(self):
        self._a = []  # representation: Python dynamic array
    def push(self, x):
        self._a.append(x)
    def pop(self):
        if not self._a:
            raise IndexError("pop from empty stack")
        return self._a.pop()
    def top(self):
        if not self._a:
            raise IndexError("top from empty stack")
        return self._a[-1]
    def is_empty(self):
        return len(self._a) == 0
  • Linked‑list stack (Python):
class _Node:
    __slots__ = ("data", "next")
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class ListStack:
    def __init__(self):
        self._head = None
    def push(self, x):
        self._head = _Node(x, self._head)
    def pop(self):
        if self._head is None:
            raise IndexError("pop from empty stack")
        x = self._head.data
        self._head = self._head.next
        return x
    def top(self):
        if self._head is None:
            raise IndexError("top from empty stack")
        return self._head.data
    def is_empty(self):
        return self._head is None
  • Client code that works with either:
def evaluate_postfix(tokens, stack):
    for tok in tokens:
        if tok.isdigit():
            stack.push(int(tok))
        else:
            b = stack.pop(); a = stack.pop()
            if tok == '+': stack.push(a+b)
            elif tok == '-': stack.push(a-b)
            elif tok == '*': stack.push(a*b)
            elif tok == '/': stack.push(a//b)
            else: raise ValueError("unknown op")
    return stack.pop()

if __name__ == "__main__":
    expr = "3 4 2 * 1 5 - 2 3 ^ ^ / +"  # simplified here without ^ support
    tokens = "3 4 + 2 * 7 -".split()
    print(evaluate_postfix(tokens, ArrayStack()))  # expected 7
    print(evaluate_postfix(tokens, ListStack()))   # expected 7
  • Sample output:
7
7
  • Link to ADT: The evaluate_postfix function depends only on the Stack ADT operations; it does not care whether the stack is array‑ or list‑based.

Common mistakes

  • No representation invariant: Implementations that do not state or maintain invariants (e.g., forgetting to update size or indices), leading to bugs.
  • Violating encapsulation: Exposing internal fields so clients rely on them, preventing changes in implementation later.
  • Incomplete algebraic specification: Forgetting key axioms like pop(push(S, x)) = S and top(push(S, x)) = x.
  • Ambiguous abstraction function: Not clearly mapping from fields to the abstract value, making proofs of correctness unclear.
  • Over‑specifying performance in the ADT: The ADT should specify semantics, not big‑O costs. State performance when choosing among data structures (refer to “Algorithm analysis: time and space complexity”).
  • Ignoring error cases: Not specifying behavior for invalid inputs (e.g., denominator 0 in Rational, or dequeue on empty queue).

For your exam

  • Short notes: Contrast ADT vs. DS with examples; Linear vs. Non‑linear structures; Static vs. Dynamic.
  • Derivations/specifications: Give algebraic specification for Stack/Queue/Set and derive properties (e.g., size after operations) using axioms.
  • Design questions: Choose a representation for an ADT (e.g., polynomial, rational number, complex number, time‑of‑day), state rep invariant and abstraction function, and outline operation implementations.
  • Programs: Implement a Stack/Queue as a class with methods; demonstrate client code that uses only the ADT interface; small demonstration I/O. Expression conversion/evaluation belongs under their dedicated topics but is often paired with stack ADT use.
  • Diagrams: Interface vs. Implementation layering; show abstraction function and rep invariant.
  • What a full‑marks answer includes:
    • Clear definitions with bold key terms on first use.
    • For ADTs: operation signatures, preconditions/postconditions, and complete axioms.
    • A stated representation invariant and an abstraction function for any concrete design.
    • For correctness: a brief argument that operations preserve the invariant and meet postconditions.
    • Clean, runnable code if asked, with sample input/output that matches exactly.
    • If analysis is requested, state assumptions (RAM model) and refer to the algorithm analysis topic for big‑O definitions.

Quick check

  1. What is an Abstract Data Type (ADT), and how is it different from a Data Structure?
  2. State two axioms of the Stack ADT involving push, pop, and top.
  3. What are a representation invariant and an abstraction function, and why are they needed?

Answers: 1) An ADT defines a set of values and operations with semantics independent of implementation; a data structure is a concrete implementation that stores data and supports those operations. 2) pop(push(S, x)) = S and top(push(S, x)) = x; also isEmpty(empty) = true and isEmpty(push(S, x)) = false. 3) A representation invariant is a condition that must always hold over the internal fields; an abstraction function maps the internal representation to the abstract value; they are needed to prove that an implementation correctly realizes the ADT and that operations preserve correctness.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?