Unit 3 – Area of Study 1: Data Modelling with Abstract Data Types

Abstract Data Type (ADT)

A conceptual data model defined by the operations it supports, not how it is implemented. ADTs hide details and provide a clear interface, promoting abstraction, modularity, reuse, and easier reasoning.

Why use ADTs?

They let you focus on what operations do, not how. This reduces complexity, allows implementation changes without affecting other parts of the program, and supports modular, reusable code.

Set

Unordered collection of distinct elements. No duplicates allowed. Operations: add, remove, membership test. Useful for tracking visited nodes or unique items.

List

Ordered collection of elements where duplicates are allowed. Supports access by index, insertion, and deletion. Useful for sequences, steps, or ordered records.

Array

Fixed-size, contiguous block of memory. Provides constant-time access by index. Insertions/deletions may require shifting elements. Efficient for random access.

Dictionary (Map)

Collection of key–value pairs, each key is unique and maps to a value. Supports fast lookup, insertion, and deletion. Example: student ID → student record.

Stack

A Last-In-First-Out (LIFO) collection. Operations: push (add), pop (remove), peek (view top). Models nested processes like function calls, undo systems, expression evaluation.

Queue

A First-In-First-Out (FIFO) collection. Items enqueued at back, dequeued from front. Models waiting lines and task scheduling.

Priority Queue

Collection where each item has a priority. Highest priority item is dequeued first, not necessarily the earliest added. Often implemented with heaps. Used in Dijkstra’s algorithm and scheduling.

Graph

Vertices (nodes) + edges (connections). Can be directed/undirected, weighted/unweighted. Models networks such as maps, transport routes, or social connections.

Graph features

Paths (sequences of edges), weighted path lengths (sum of weights), cycles (closed loops), subgraphs (smaller graphs inside a larger one).

Graph types

Complete (every pair connected), Connected (path exists between all vertices), Directed Acyclic Graph (directed, no cycles), Tree (connected acyclic graph).

Decision Tree

A tree of decisions where branches represent choices and leaves represent outcomes. Used for planning, classification, or decision processes.

State Graph

Vertices represent system states; edges represent transitions between states. Useful for problem-solving and search (e.g., maze navigation).

Application: Which ADT models a waiting line?

A queue, since it preserves First-In-First-Out order, matching real-world lines.

Application: Which ADT models a network of cities?

A graph with weighted edges, since it can represent distances or travel times.

Comparison: Stack vs Queue

Stack: Last-In-First-Out, useful for nested tasks (function calls). Queue: First-In-First-Out, useful for scheduling and fairness.

Comparison: Array vs List

Array: fixed size, O(1) access, slower insertions/deletions. List: flexible size, easier to insert/delete, slower access.