Abstract Data Types, Formal Signatures & Core Containers

In VCE Algorithmics, an ADT separates what operations are available from how they are implemented in hardware or a concrete programming language. While a Data Structure is a concrete memory layout (such as a contiguous block of RAM or pointer-linked nodes), an Abstract Data Type is a purely algebraic specification. In procedural languages (such as C), an ADT is typically stored using a struct, whereas object-oriented programming (OOP) languages (such as Java or Python) encapsulate ADTs using classes and objects.

Structure of a Formal ADT Signature

Every formal ADT specification in VCE Algorithmics consists of three mandatory sections:

• name: The identifier of the ADT being defined (e.g., stack, queue, dictionary).
• import: Existing primitive or composite types required to define the operations (commonly element, boolean, integer, key, value).
• ops: The list of operation signatures mapping domain types (inputs before $\rightarrow$) to codomain types (outputs after $\rightarrow$). An operation with nothing to the left of $\rightarrow$ is a constructor (initialiser) that takes no arguments and creates a fresh instance of the ADT.

name: <adt_name>
import: element, boolean, integer
ops:
  newADT:                   -> <adt_name>
  mutatorOp: <adt_name> x element -> <adt_name>
  queryOp:   <adt_name>           -> element
  isEmpty:   <adt_name>           -> boolean

A List is an ordered collection of elements where the same value may appear more than once. Unlike sets, lists preserve positional sequence ($(a, b) \neq (b, a)$) and permit duplicates ($(a, a, b)$). In strongly typed OOP languages like Java, a homogeneous list is declared with generics such as ArrayList<String>, whereas a heterogeneous list (permitting mixed element types) can be declared as ArrayList<Object> because every Java class inherits from the root Object class.

name: list
import: element, integer, boolean
ops:
  emptyList:                       -> list
  isEmpty:   list                  -> boolean
  prepend:   list x element        -> list
  append:    list x element        -> list
  head:      list                  -> element
  tail:      list                  -> list
  length:    list                  -> integer

name: array
import: integer, element, boolean
ops:
  newArray:                         -> array
  get:      array x integer         -> element
  set:      array x integer x element -> array
  insert:   array x integer x element -> array
  delete:   array x integer         -> array
  search:   array x element         -> boolean

Array ADT: Unsorted vs Sorted Time Complexity (BC, AC, WC)

An Array stores $n$ elements in contiguous memory cells of capacity $c \gg n$ indexed by integers $0 \dots n-1$. Because any memory address can be computed in $\Theta(1)$ arithmetic via $\text{base\_addr} + i \times \text{elem\_size}$, direct index lookup (GET) is always $\Theta(1)$ across Best Case (BC), Average Case (AC), and Worst Case (WC). Note also that arrays follow reference semantics: assigning one array variable to another (e.g., B = A) copies only the memory reference (address pointer), not the underlying array elements.

In the HESS curriculum notes, Unsorted Array INSERT and DELETE at an interior index $i < n$ achieve $\Theta(1)$ time when positional order does not need to be preserved by using the Overwrite/Swap trick, whereas Sorted Array INSERT uses one of two $\Theta(n)$ approaches:

• Unsorted Array INSERT at index $i < n$ ($\Theta(1)$ Overwrite vs $\Theta(n)$ Shift): Move the existing element at index $i$ to the first free slot at the end of the array (A[n] = A[i]), write the new value into A[i] = x, and increment $n$. This takes $\Theta(1)$ in BC, AC, and WC! (If positional sequence must be preserved, elements $i \dots n-1$ must shift right, costing $\mathcal{O}(n)$).
• Unsorted Array DELETE at index $i < n$ ($\Theta(1)$ Last-Element Swap vs $\Theta(n)$ Shift): Overwrite the deleted slot with the last element in the array (A[i] = A[n - 1]) and decrement the size $n$ by 1. This avoids leaving a hole in contiguous memory in $\Theta(1)$ time!
• Sorted Array INSERT ($\Theta(n)$ via Two Equivalent HESS Methods): Either (1) run a modified Binary Search ($\mathcal{O}(\log n)$) to locate the insertion index $i$ and shift all elements from $i \dots n-1$ right by 1 cell ($\mathcal{O}(n)$), or (2) append the new element at index $n$ in $\Theta(1)$ and run one pass of Insertion Sort ($\mathcal{O}(n)$) to bubble it left into sorted position.

Stacks and Queues restrict where elements can be inserted and removed, guaranteeing $\mathcal{O}(1)$ time complexity for their primary operations when properly implemented.

name: stack
import: element, boolean
ops:
  newStack:                 -> stack
  push:     stack x element -> stack
  pop:      stack           -> stack
  peek:     stack           -> element
  isEmpty:  stack           -> boolean

name: queue
import: element, boolean
ops:
  newQueue:                 -> queue
  enqueue:  queue x element -> queue
  dequeue:  queue           -> queue
  front:    queue           -> element
  isEmpty:  queue           -> boolean

Concrete Implementations of Stack & Queue (Array Ring Buffer vs Linked List)

In the HESS study guide, the structural difference between a Stack and a Queue is illuminated by comparing how they manipulate array indices and linked-list pointers:

• Circular Ring Buffer (Array Queue with front = -1, back = -1): A naive array queue that shifts elements left on dequeue degrades to $\Theta(n)$. Instead, a Circular Array Queue initialises two indices front = -1 and back = -1. When enqueue advances back past the end of the array (back + 1 > n - 1) and free slots exist at the start due to prior dequeues, back wraps around to index 0 (modulo $n$). Similarly, when front > n - 1, front wraps around to 0. This guarantees $\Theta(1)$ worst-case time for both enqueue and dequeue.
• Linked List Symmetry (Same End vs Opposite Ends): In a pointer-based Linked List maintaining head and tail pointers:
  • Stack (LIFO): Inserts (push) and deletes (pop) at the same end—specifically at head / head in $\Theta(1)$ time (or tail / tail if doubly linked).
  • Queue (FIFO): Inserts (enqueue) and deletes (dequeue) at opposite ends—specifically inserting at tail and deleting from head in $\Theta(1)$ time (or head / tail in a doubly linked list).

A Set models a mathematical finite set: an unordered collection of distinct (unique) elements. Adding an element already present in the set has no effect ($S \cup \{x\} = S$ when $x \in S$). Standard binary set operations include Union ($A \cup B$), Intersection ($A \cap B$), and Set Difference ($A \setminus B$).

A Dictionary (also called an Associative Array or Map) stores a collection of $(\text{key}, \text{value})$ pairs such that each key appears at most once. Looking up, inserting, or deleting a value is performed by its associated key rather than an integer position.

name: set
import: element, boolean
ops:
  emptySet:               -> set
  insert:     set x element -> set
  remove:     set x element -> set
  contains:   set x element -> boolean
  isEmpty:    set         -> boolean
  union:      set x set   -> set
  intersect:  set x set   -> set
  difference: set x set   -> set

name: dictionary
import: key, value, boolean
ops:
  newDict:                        -> dictionary
  put:      dictionary x key x value -> dictionary
  get:      dictionary x key      -> value
  remove:   dictionary x key      -> dictionary
  contains: dictionary x key      -> boolean
  isEmpty:  dictionary            -> boolean

A Priority Queue (PQ) is an abstract data type similar to a regular queue or stack, except that every element has an associated priority (key). In a Min-Priority Queue (used in Prim's, Dijkstra's, and A* search), the element with the lowest numerical key is extracted first; in a Max-Priority Queue, the element with the highest priority is extracted first. Elements with equal priority are served according to their order in the queue.

name: priority_queue
import: element, priority, boolean
ops:
  newPQ:                                    -> priority_queue
  insert:     priority_queue x element x priority -> priority_queue
  pull:       priority_queue                -> priority_queue
  peek:       priority_queue                -> element
  requeue:    priority_queue x element x priority -> priority_queue
  isEmpty:    priority_queue                -> boolean

Concrete Implementations & Isomorphism to Sorting Algorithms

In the HESS curriculum notes, each concrete implementation of a Priority Queue directly mirrors a classic sorting algorithm when $n$ elements are inserted into the PQ and then repeatedly extracted until empty:

name: set
import: element, boolean
ops:
  newSet:                  -> set
  add:       set x element -> set
  remove:    set x element -> set
  contains:  set x element -> boolean
  intersect: set x set     -> set

• I can write a complete VCE ADT signature using name, import, and ops with Cartesian products ($\times$) and arrows ($\rightarrow$).
• I can compare Unsorted vs Sorted Array complexities for GET ($\mathcal{O}(1)$), SEARCH ($\mathcal{O}(n)$ vs $\mathcal{O}(\log n)$), and INSERT/DELETE ($\mathcal{O}(n)$ shifting).
• I can explain how Unsorted Array, Sorted Array, and Binary Heap Priority Queues correspond to Selection Sort, Insertion Sort, and Heapsort.