Preface

Preface

Undergraduate-level computer science (CS) programs typically teach data structures and algorithms (DSA) in two phases across one or two courses early in the program. The first phase provides an introduction to foundational data structuring and covers basic containers and access alongside introductory algorithmic techniques for sorting, searching, self-balancing structures, graph traversals, and string processing. The second phase builds on these concepts by providing more advanced algorithmic design material focused on increasingly complex real-world problem spaces. This module focuses primarily on the former, providing readers with a grounded introduction to data structuring and rudimentary algorithmic application with reference implementations in the Rust programming language.

DSA foundations are largely programming-language agnostic. Core concepts such as asymptotic analysis and algorithmic correctness mostly rely on mathematics, formal proofs, and often even systems architectures or hardware constraints that hold true across programming languages. For this reason it is common to use pseudocode, a generic representation of high-level coding conventions, to describe algorithmic processes in both design and analysis. However, it is not possible to execute pseudocode directly, and providing concrete examples can greatly accelerate the learning process. As a result, it is common to see DSA texts written with examples in a specific programming language.

Historically, the most common languages used in DSA courses have included Pascal, Lisp, C, and more recently C++, Java, and Python. Each one of these languages carries its own tradeoffs which mostly center around language design and philosophies that present different layers of complexity to code authors. A given DSA text’s language preferences (or lack thereof) may also reflect intended audiences or a program’s priority on providing exposure to real-world language trends and usage.

Providing systems-language reference material fosters a deeper and more durable understanding of DSA by engaging readers with explicit reasoning about storage layouts, memory management, performance, and safety. For example, the techniques required to implement list structures from first principles form the backbone of much of the material presented in this module. Lists provide a convenient way to introduce readers to memory organization, traversal, mutation, and algorithmic behavior. The same concepts and tradeoffs reappear throughout the implementation of more complex structures, either through shared language semantics or through the direct use of lists as fundamental backing structures. By confronting these concepts directly instead of treating them as implementation details hidden behind high-level language abstractions, readers are better positioned to understand both the theoretical foundations of the material and their practical implications in real-world systems.

Among contemporary systems-level languages, the choice to use Rust was based in its strong emphasis on developer experience. Rust’s mature tooling ecosystem and rich compiler diagnostics provide an ergonomic and approachable systems programming experience.

Prerequisites

Similar to other DSA course materials, readers are generally expected to possess basic proficiency in writing and executing programs prior to engaging this module.

This module also assumes the reader has some prior knowledge of Rust, and does not provide an explicit language primer. The canonical resource for learning Rust is The Rust Book by Steve Klabnik and Carol Nichols. I have also collected some notes on the subject with an attempt at a language primer which can be viewed as a parallel module on this site as The Rust Language. This module also contains a fair amount of unsafe Rust, so readers will likely find Aria Desires’ narrative work through The Rustnomicon and Learn Rust With Entirely Too Many Linked Lists essential reading.

The subject matter also draws on foundational mathematical concepts. Familiarity with algebra (summation, function modeling, etc.) and discrete mathematics (relations, set theory, graph theory, etc.) can further aid comprehension, but rigorous study of these domains is not strictly necessary. For readers with no formal discrete mathematics background, Susanna Epp’s Discrete Mathematics with Applications provides a fantastic reference.

Content Organization

This module is broken up into four primary data structure categories. Each category introduces new concepts that build on previously introduced elements, and is thus designed to be consumed linearly.

The first chapter on sequential structures covers foundational in-memory data storage concepts. This chapter presents some of the most difficult Rust material in the module with Rust’s unsafe memory management and comparative ordering APIs. Some external language review is likely necessary to fully grok the implementation examples.
The second chapter on keyed structures introduces map and set structures, and illustrates how closely knit data structures and algorithms are by using previously introduced data storage concepts with additioanl logical layers to compose higher-level containers. This chapter introduces basic hashing and the module’s first sorted structure.
The third chapter on hierarchical structures provides a soft introduction to combinatorial graph structures by way of trees. This chapter presents new ways to utilize data typing to build and navigate non-linear invariants.
The fourth chapter on relational structures covers combinatorial graph structures in a more detail and explores graph-based modeling techniques for representing real-world relationships and connectivity. This chapter is algorithm heavy and provides a strong jumping off point to a subsequent module on algorithm design techniques.

Disclosures

This is a one-person project built entirely in my free time, for fun. In the absense of any sort of technical, architectural, editorial, or any other substantive human feedback, I feel it is responsible to disclose that I have leveraged LLMs to help provide eyes when mine are too tired to see. This mostly comes in the form of editorial feedback to tighten up wording, improve structure, and support iterative design review for the module’s companion library of pedagogical implementations. The basic ideas, structure, topical flow, and coverage presented here are my own.

As the sole author of this material I would much prefer to interact with a group of contributing editors and SMEs. If you find the subject matter interesting and would like to participate, or if you simply spot some glaring errors and want to set the record straight, please reach out!

This work is licensed under a Creative Commons (CC BY-NC-ND) 4.0 International License.