Preface

College-level computer science (CS) programs typically teach data structures and algorithms (DSA) across one or two courses early in the program. The material is often divided into two phases. The first phase provides an introduction to foundational data structuring such as contiguous storage, indirection, custom typing, and hierarchical organization alongside basic algorithmic techniques such as sorting, searching, self-balancing structures, and elementary graph or 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 material itself is largely programming-language agnostic. Core concepts such as asymptotic analysis (which describes an algorithm’s logical growth tendency and spatial requirements) and algorithmic correctness depend on mathematical principles, formal proofs, and often even systems architectures or hardware constraints that hold true across programming languages. However, it is not possible to execute pseudocode directly, and providing concrete examples greatly accelerates 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, often related to syntactic complexity and the ability to focus on underlying DSA concepts. Language preferences also reflect a given 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 the material by engaging readers with explicit reasoning about memory management, indirection, and safety. By confronting the concepts directly, readers are better positioned to understand and appreciate the theoretical foundations of DSA and their practical implications in real-world systems through methodologies such as data-oriented design. The choice to use Rust over a more traditional systems-level language 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, but are not assumed to have mastery of either the Rust language or the underlying mathematical principles of DSA.

This module 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.

The subject matter also draws on foundational mathematical concepts. Familiarity with algebra and discrete mathematics is beneficial, and exposure to more theoretical topics such as set and graph theory can further aid comprehension, but are 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 introductory data structures module covers a core set of abstract data types (ADTs), their various logical representations, and sufficient analysis to enable readers to make informed decisions when crafting programming solutions.

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 lists outlines basic in-memory data storage concepts and presents some of the most difficult Rust material in the module. The section provides an introduction to Rust’s most crucial memory management and ordering APIs, but further external language review is likely necessary to fully grok the implementation examples. This section also introduces how tightly knit the concepts of data structures and algorithms are by introducing the module’s first sorted structure.

The second chapter on keyed structures introduces the map and set structures as well as basic hashing. This chapter also applies the sorted structure introduced in the first chapter to illustrate how abstractions can be combined to create more complex creations.

The third chapter on hierarchical structures introduces self-referential types used to build complex structures through indirection. These structures are most intuitively navigated via recursive traversal algorithms. This chapter culminates with the module’s first utility program which uses a custom tree structure and traversal algorithm used to parse a Markdown file and print a hierarchical visualization of its headers.

The fourth chapter on relational structures introduces graphs and the many ways graphs can be used to model real-world networking concepts. This chapter is algorithm heavy and provides a strong jumping off point to a subsequent module on algorithm design techniques.

Reference Documentation

References to this module’s companion library are scattered throughout the material. The library contains fully-functional pedagogical reference implementations, complete with design documentation. The library provides links to source code, but readers not familiar with the rustdoc style may prefer direct project repository access.

The next page of this module lays the foundations for a formal lexicon to help navigate the material moving foward. Indeed, even seemingly simple terms like “data structure” represent a loose categorization of several concepts with specific semantics and implications. So put a kettle on and lets get started!