Ownership vs. Reference — Companion Code

Data Structures and Algorithms in Rust and Java

Companion repository for the book Ownership vs. Reference: Data Structures and Algorithms in Rust and Java by Zeeshan Ali.

Every data structure in this repository is implemented twice: once in Rust and once in Java. The gap between the two implementations is the lesson. Where they look nearly identical, ownership is not the interesting question for that structure. Where they diverge sharply, the divergence tells you something about what the language's memory model demands of you and why. This is not a Rust tutorial with Java asides. It is the same twelve chapters of interview-grade DSA, implemented in both languages, with the comparison as the actual point.

📖 Get the book: Gumroad ·

---

Who this is for

Engineers refreshing DSA fundamentals before a senior interview, or genuinely trying to understand what Rust's ownership model costs and buys you, structure by structure. If you have used a HashMap for years without knowing what happens during a resize, or written a recursive tree traversal without thinking about how deep a tree could safely get, this book and repo are aimed directly at that gap.

---

Chapter index

Chapter	Structure	The ownership question it raises
01	Arrays and Dynamic Arrays	Stack vs heap allocation, and why resizing is amortised O(1) not O(n)
02	Linked Lists	Where Box is enough, and where Rc<RefCell<T>> becomes unavoidable
03	Stacks and Queues	Vec as stack, VecDeque circular buffer, the naive O(n) queue trap
04	Binary Search Trees	Hierarchical ownership, Box<Node> maps cleanly to tree structure
05	Heaps and Priority Queues	Array-indexed structure sidesteps ownership entirely
06	Tries	Each node owns a fixed array of optional children
07	Hash Maps	Borrow conflict on simultaneous reference and insert, the Entry API
08	Graphs	Why cycles break Rc<RefCell<T>> and index-based storage does not care
09	Sorting	In-place mutation, stability, and why Java needs a swap Rust does not
10	Dynamic Programming	Memoisation as owned state vs borrowed state
11	Arena Allocators	Generational indices as the answer to "who owns this now?"
12	Union-Find	The index-based pattern's cleanest, final payoff

---

Repository structure

ownership-vs-reference/
├── rust/            Cargo workspace, one crate per chapter
│   ├── ch01_arrays/
│   │   ├── src/lib.rs           the chapter's from-scratch structure
│   │   ├── src/problems/        one file per problem from that chapter
│   │   └── examples/            small illustrative snippets from the prose
│   └── ch02_linked_lists/ ...
├── java/            Maven multi-module project, same chapter layout
│   ├── ch01_arrays/
│   │   ├── src/main/java/       the from-scratch structure plus one class per problem
│   │   └── src/test/java/       JUnit tests where present
│   └── ch02_linked_lists/ ...
└── README.md

Both layouts mirror the book's chapter numbering and match the naming used in its Problems sections and Appendix B's problem index, so a specific problem is easy to find from either direction.

---

Building and running

Rust: Rust 2021 edition, stable toolchain.

cd rust
cargo build --workspace
cargo test --workspace

Individual snippets from the chapter prose can be run with cargo run --example demo_1 from within a specific chapter directory.

Java: Java 17 or later.

cd java
mvn compile
mvn test

Chapters that use external crates (slotmap, bumpalo in ch11) note the dependency in their Cargo.toml. No chapter requires anything beyond what ships with the standard library for Java.

---

Verification status

This repository has been built and tested end-to-end with a real toolchain. cargo build --workspace, cargo test --workspace, mvn compile, and mvn test all pass cleanly across every module in both languages. That was not true when the repo was first generated. It took several rounds of real compiler and test failures to get here. What that process actually found is worth knowing, since it is a more honest signal than "it compiles":

• Several problem files needed explicit imports that Rust's module system does not grant automatically from the crate root.
• Two or three cases where a chapter's own internal type shared a name with something a specific problem needed, requiring a rename.
• One genuine cross-chapter type dependency (Chapter 5 needing Chapter 2's ListNode), needed independently in both languages.
• One real borrow-checker error in a recursive cycle-detection function, fixed by copying a Copy value out of a match scrutinee before a guard clause needed a mutable borrow of the same data.
• A small utility method (swap) the book's Java code calls but never defines — a real gap in the source text, not an extraction artifact, since Rust never needed it (slices have a built-in .swap()).

All of that is fixed. What this does not mean: only four problems have real assertions checking their output is correct. Everything else compiles and was traced by hand for logical correctness but does not have an automated test proving it. Adding tests for the rest would be the natural next step if you extend this repo.

What is tested

Problem	Chapter	What the test checks
Two Sum	1	[2,7,11,15], target 9 → indices [0,1]
Valid Parentheses	3	"()[]{}" is valid, "(]" is not
Merge Sort	9	[5,3,8,1,9,2] sorts to [1,2,3,5,8,9]
Climbing Stairs	10	n=1,2,5 → 1, 2, 8

---

What to read alongside

The book gives the full context: the opening incident that motivates each structure, complete implementations with comments explaining the why rather than the what, three to five LeetCode-style problems per chapter with naive and optimal solutions in both languages, and a production section covering when to reach for each structure and when not to.

The repo is the runnable version of everything in the book. If something in the code does not make sense without the surrounding explanation, the book is where the explanation lives.

---

⭐ If this repository helped you understand the difference between how Rust and Java think about memory, consider starring it.