Preface

It is difficult to completely decouple the concepts of data structures and algorithms (DSA), as a proper understanding of one often implies consequences for the other. In 1976, Niklaus Wirth, the designer of the Pascal programming language, published the influential introductory text Algorithms + Data Structures = Programs, which captured the relationship so clearly that it effectively defined the genre. What made Wirth’s book distincitve was its pedagogical approach to material that had previously been presented largely as compendia, collections for the cognoscenti rather than beginner-focused introductions to the domain.

Audience

It is common for college-level computer science (CS) programs to cover DSA material over one or two courses in the first or second year of the program. As a prerequisite, students are generally expected to have the basic ability to write and execute code before studying DSA, but are not expected to have mastery over any particular programming language.

Language Presentation

DSA material is largely programming-language agnostic. Core concepts such as asymptotic analysis (which describes the algorithm’s logical structure), algorithmic correctness, and operational efficiency (which reflects real-world implementation) depend on mathematical principles, formal proofs, and hardware constraints that hold across programming languages. That said, you cannot execute pseudocode directly, so you must choose a concrete programming language to implement and experiment with these concepts.

Due to academic funneling, it is common to present DSA material using a CS program’s programming language du jour. In some curricula, students are introduced to a particular language before encountering DSA material, either as part of an intentional program pipeline or as an independent prerequisite for a DSA course. As a result, it is common to see DSA texts written with explicit reference to a specific language.

Historically, languages commonly 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 how directly that syntactic complexity supports focusing on underlying DSA concepts rather than incidental language details. This module presents the material using Rust, a modern, memory-safe systems programming language.

The choice of Rust reflects a single guiding principle: engaging with structural and algorithmic complexity while explicitly accounting for memory model management and safety fosters a deeper, more durable understanding of the concepts involved. By confronting these concerns directly, students are better positioned to appreciate both the theoretical foundations of DSA and their practical implications in real-world systems.

Coverage

Material covered in DSA courses typically covers a core set of abstract data types (ADTs), their various logical representations, and enough analysis to allow the student to make informed decisions when crafting programming solutions. Many representations contain operational trade-offs

A typical DSA curriculum covers a core set of abstract data types (ADTs), their various logical representations, and sufficient analysis to enable students to make informed decisions when crafting programming solutions. Specific implementations are often left as independent exercises. Accordingly, this module only occasionally discusses implementations, primarily as a means of illustrating particular concepts. However, the project does provide a companion library of pedagogical Rust implementations for reference.

Reference Documentation

One of the most effective ways to understand a topic is through hands-on learning. This project includes a companion library to illustrate the concepts covered in this module. You can also visit the project repository for direct access to code examples.

Instructional Approach

The focus of this material is on introducing core DSA concepts to beginners using a modern systems language. The material does not cover esoteric optimizations or performance-oriented “black magic” aimed at bleeding edge performance for production systems. Many real-world solutions balance clear code that is simple to read and reason about with hyper-efficient, domain-specific solutions. Presenting implementation examples in a system language like Rust provides exposure to the concepts while also providing an opportunity for students to take the material further with their own designs and optimizations that may not be as easily accessible in other high-level languages.

This material is designed to be consumed linearly. The goal is to introduce foundational concepts before progressively building more complex compositions, moving from basic modeling to more advanced algorithmic design. Many college-level programs divide this content into an introductory data structures course followed by a course in algorithm design. This module follows a similar progression.

Content Organization

There is no single canonical way to classify the content covered in a typical data structures and algorithms series. There are also a wide variety of ways to accomplish the same programming tasks. As a result, it is common to encounter wildly different coverage and approaches across equally as valid eductational programs and texts. The good news is that you dont need to know every data structure or algorithm to become a successful programmer. This module simply outlines the key members and provides some specific examples to illustrate the concepts. After you understand the fundamentals, it becomes much easier to seek out (or even design new) data structures and algorithms more finely tuned to your specific code solution.

The rest of this section lays the foundations for a formal lexicon of covered concepts to provide a way to talk about how the content itself is organized throughout this module. Indeed, even the term “data structure” itself is a loose categorization of several concepts with specific semantics and implications.

The following tables group common ADTs and their data structure implementations into broader data model categories. These include sequential, hierarchical, associative, and graph-based families of ADTs and their concrete realizations. Each table summarizes key properties, such as whether the structure is sorted, common in-memory structuring, and whether standard library implementations exist for each listed language. Not all ADTs have standard or concrete implementations, so I hope you’re ready to get crafty.

To save space and visual noise the tables in this section use a symbol-based short-hand to convey properties.

Symbol	Description
S	Sorted
U	Unsorted
I	Indexed (typically within contiguous memory arenas)
L	Linked (traditional pointer-based structures)
/	Either/or, listed in order of commonality or preference
+	Composite structures that use more than one type of memory structure

Sequential Structures

The sequential structures in this table are all unsorted by default. The stack and queue variants use a specific kind of ordering by default. Though not exactly a sorting scheme, the The First In First Out (FIFO) and Last In First Out (LIFO) orderings provide the primary behavioral characteristics of each structure type in this group.

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
List	Static array	U	I	T[]	[n]T	[T; N]
List	Dynamic array	U	I	ArrayList<E>	[]T	Vec<T>
List	Linked list	U	L	LinkedList<E>	container/list	LinkedList<T>
Stack	Any list	LIFO	I/L	Deque<E>	[]T	Vec<T> / LinkedList<T>
Queue	Any list	FIFO	I/L	Queue<E>*	container/list	VecDeque<T>
Deque	Any list	FIFO/LIFO	I/L	ArrayDeque<E>	container/list	VecDeque<T>

* via LinkedList<E>

Hierarchical Structures

Heaps

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
Heap	Binary heap	S	I/L	Custom	Custom	BinaryHeap<T>

General Trees

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
N-ary tree	Custom recursive tree node	U	I/L	Custom	Custom	Custom
Trie	Custom n-ary tree	S	I + L	Custom (TreeNode)	Custom	Custom

Search Trees

The most common search trees are binary search trees (BSTs)

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
BST	AVL tree	S	I/L	Custom	Custom	Custom
BST	Spaly tree	S				Custom
BST	(2, 4) tree	S				Custom
BST	Red-Black tree	S	I/L	TreeMap<K, V>	Custom	Custom
N-ary search tree	B-tree	S	I/L	Custom	Custom	Custom

Associative Structures

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
Map	Chaining hash table	U	I		Custom	Custom
Map	Probing hash table	U	I	HashMap<K, V>	Custom	Custom
Sorted map	Tree map or skip list	S	L + I			BTreeMap<K, V>
Multimap	Any hash table	S	I
Set	Any hash table or skip list	U	I	HashSet<E>	map[K]struct	HashSet<T>
Sorted set	Tree map or skip list	S	L + I

Graph Structures

ADT	Sorted/unsorted	Backing Structure	Java	Go	Rust
Directed graphs	U*	L/I	Custom (Graph<V, E>)	Custom	Custom
Undirected graphs	U	L/I	Custom	Custom	Custom
Weighted graphs	U**	L/I	Custom	Custom	Custom
Directed acyclic graphs	S***	L/I	Custom	Custom	Custom

* Sorted in topological applications

** Sorted for shortest paths

*** For topological ordering

Basic Algorithms

This section covers some common algorithmic themes. See the sub-sections for deeper dives into these algorithms.

Type	Sub-Type	Complexity	Std. Lib. Implementation
Sorting	Insertion sort	O(n^2)	Java/Rust:
	Merge sort		Java: Rust:
	Quick sort		Java/Rust:
Searching	Linear/sequential search	O(n)
	Binary search	O(log(n))
Hashing
Graph Algs.