Abstract Data Types and Algorithms

ADT contracts and complexity models

An abstract data type specifies operations and behavior; a data structure supplies a concrete representation. Before comparing implementations, state the operation, input size, and guarantee. Worst-case cost bounds every valid operation sequence of the relevant size; expected cost uses a probability model; amortized cost distributes total work across a sequence without necessarily using randomness. Space matters alongside time. An implementation with fast lookup may pay for spare capacity or additional pointers. Client code should rely on the specified contract rather than undocumented storage details.

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Array lists, circular queues, and amortization

An array gives constant-time indexed access. Inserting near the front of an array list shifts many elements, making that operation linear. Appending is usually cheap until capacity is exhausted. If capacity doubles when full, occasional copying is expensive but total copying over many appends remains linear, yielding constant amortized append cost. A circular queue stores logical position i at a wrapped physical index. Maintain head and size carefully to distinguish empty and full states. Shrink thresholds should avoid growing and shrinking repeatedly after a small oscillation in size.

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Linked structures, stacks, and deques

A linked node stores an item plus references connecting nodes. Inserting after a known node can take constant time, but locating the node by index may require a linear traversal. Singly linked lists support efficient head operations; doubly linked lists make movement in both directions easier at the cost of additional references and update obligations. A sentinel can simplify empty and endpoint cases. After insertion or deletion, verify all forward and backward links, size, and head/tail invariants. Linked storage does not automatically make every list operation faster.

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Hash tables and expected lookup cost

A hash function maps keys into a manageable index range; collisions occur when different keys map to the same bucket or probe region. Chaining stores colliding entries together; open addressing searches alternative slots. The load factor measures entries relative to available capacity. Good expected performance depends on hash behavior, collision handling, and resizing policy. Equality and hashing must agree: keys considered equal need compatible hash codes. Hash-table iteration generally does not provide sorted order. Deleting an open-addressed entry needs care so that it does not break the search path for later entries.

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Search trees, heaps, and a worked insertion

A binary search tree orders keys so that left descendants are smaller and right descendants are larger under its comparison rule. Search cost follows height; balancing prevents a sorted insertion order from forming a long chain. A binary min-heap instead requires each parent to be no larger than its children. Insert 2 into heap [3, 5, 8, 9]: append it, swap with parent 5, then swap with root 3, giving [2, 3, 8, 9, 5]. This restores heap order in logarithmic time but does not create a sorted array.

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Graph representations and traversals

An adjacency matrix stores potential edges in a square table and offers direct edge checks using quadratic space. Adjacency lists store existing neighbors and use space proportional to vertices plus edges. Breadth-first search uses a queue and discovers shortest edge-count distances in an unweighted graph. Depth-first search explores one route before returning and can support connectivity and cycle reasoning. Mark vertices at the appropriate point to avoid repeated processing. Traversal costs depend on representation: examining every neighbor list totals O(V + E), whereas scanning a matrix row per vertex can cost O(V squared).

References: COMP 2402 ABC — Fall 2024 course outline · Pat Morin — Open Data Structures, Java edition

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• COMP 2402 ABC — Fall 2024 course outline ↗Course scope · Fall 2024
• Pat Morin — Open Data Structures, Java edition ↗Open textbook · Java edition; CC BY