Skip to content
Tutorials Center
My learning

Topics

Lesson 129 of 132 ยท Practice and Review

Data Structures in Safe Rust

Build a linked list with Option<Box>, a binary search tree, an index-based graph and a segment tree in safe Rust, then make them generic. Learn why ownership shapes each design.

Textbook data structures are written with pointers everywhere: a node points to the next node, a parent points to its child and the child points back. In Rust, that style collides with ownership. Every value has one owner, so a structure where two nodes "own" each other cannot be written naively. The good news is that the collision teaches useful design habits, and every structure in this lesson is written in safe Rust, with no unsafe and no reference counting.

You will build four structures: a stack-like singly linked list with Option<Box<Node>>, a binary search tree, a graph that stores indices instead of pointers, and a segment tree backed by a plain Vec. At the end each one is made generic. You should know Box and ownership, enums and Option and generics. If you later need doubly linked structures or raw pointers, see unsafe data structures.

Why Option<Box>

A node that contains another node of the same type has infinite size, so the compiler rejects it. Putting the next node behind a Box (a heap pointer with a known size) fixes that, and Option marks the end of the list:

Rust
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

The head owns the second node, which owns the third, and so on. Ownership flows in one direction, which is exactly what the borrow checker likes.

A singly linked list

The key tool is Option::take: it moves the value out of an Option and leaves None behind. Without it you could not move out of &mut self.

Rust A linked list stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Read reverse slowly; it is the classic exercise. It walks the list, and for each node it detaches the tail (take), points the node at the previous head, and moves on. No node is copied; ownership is passed along like a baton.

One caveat: dropping a very long list drops nodes recursively, which can overflow the stack for a million elements. A production list implements Drop with a loop that takes nodes one at a time. For everyday use, Vec or VecDeque is faster anyway (other collections).

A binary search tree

A tree node owns up to two children, again Option<Box<Node>>. Insertion recurses down the correct side. Because each node owns its children, no parent pointers are needed.

Rust Binary search tree: insert, contains, in-order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The loop in insert walks a &mut Option<Box<Node>> cursor down the tree and writes into the empty slot it finds. That "pointer to the slot" idea is the safe-Rust trick for mutating a spot in a structure without recursion. An in-order walk of a BST always produces sorted output, which makes a handy test.

A graph without pointers

Graphs are where beginners hit the wall: a node would point to neighbors, which point back. The standard safe answer is to store the nodes in a Vec and refer to them by index. The indices are plain integers (Copy), so there are no ownership problems.

Rust Graph with indices: adjacency list and BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

This design has real advantages: nodes sit in contiguous memory (fast), cycles are no problem, deleting is done by marking slots or using a "generational" index, and the whole graph is trivially Clone and Send. Many production crates use the same idea (often called an arena).

A segment tree

A segment tree answers "sum of items from l to r" quickly while allowing point updates, both in O(log n). Instead of node objects it uses a Vec where the children of index i are 2*i and 2*i + 1, so there are no pointers at all.

Rust Segment tree: range sum with updates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The sum of 8 + 6 + 2 is 16 before the update and 20 after it, because index 3 changed from 6 to 10.

Making them generic

Real libraries do not hard-code i32. To make the BST generic, replace i32 with a type parameter T: Ord, so comparisons work for numbers, strings and your own types that implement Ord:

Rust A generic binary search tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The same code now stores integers and Strings. The only requirement is T: Ord.

Practice

  1. Add len and remove_min to the generic tree.
  2. Give the linked list an iterator (custom iterators) that yields &T.
  3. Add a depth-first search to the graph using an explicit stack.
  4. Change the segment tree to compute the minimum instead of the sum; what must the "combine" operation satisfy?

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a recursive Node struct need Box?

    A node containing a node of its own type directly has no finite size. Box stores the child on the heap behind a pointer of known size.
  2. 2. What does Option::take do?

    take replaces the Option with None and returns the old value, which lets you move out of a place you only borrow mutably.
  3. 3. How does the graph avoid ownership problems between neighbors?

    Indices are plain Copy integers, so any number of nodes can refer to any other node without owning it.
  4. 4. What bound makes the generic BST able to compare keys?

    Ord provides total ordering, which insert uses to choose the left or right subtree.

Summary

  • Ownership dictates data-structure design: one owner per node, flowing downward.
  • Option<Box<Node>> builds lists and trees; take, as_ref and &mut cursors move and edit nodes safely.
  • Graphs and many trees are easier with a Vec of nodes and integer indices instead of pointers.
  • A segment tree uses array arithmetic only, with O(log n) queries and updates.
  • Generic versions need only the bounds they use, such as T: Ord.

Next: Rust Interview Questions tests what you have learned.