MACRO NEPAL
Complete Guide to Rust Data Structures
awiskar acharya
March 10, 2026
4:15 pm

Introduction to Rust Data Structures

Data structures are fundamental building blocks for organizing and managing data in programs. Rust provides a rich set of data structures through its standard library, along with the ability to create custom structures. Understanding these structures is crucial for writing efficient, safe, and idiomatic Rust code.

Key Concepts

  • Ownership: Each data structure owns its data
  • Memory Safety: Compile-time guarantees prevent memory issues
  • Performance: Zero-cost abstractions with control over memory layout
  • Type Safety: Generic structures maintain type information
  • Iterator Support: Most structures provide iteration capabilities

1. Sequence Containers

Vec - Dynamic Array

fn main() {
// Creating vectors
let mut v1: Vec<i32> = Vec::new();
let v2 = vec![1, 2, 3, 4, 5];
let v3 = vec![0; 10]; // Ten zeros
// Adding elements
v1.push(10);
v1.push(20);
v1.push(30);
// Accessing elements
let third = v1[2];
println!("Third element: {}", third);
// Safe access with get
match v1.get(5) {
Some(value) => println!("Value: {}", value),
None => println!("Index out of bounds"),
}
// Removing elements
let last = v1.pop(); // Returns Option<T>
println!("Popped: {:?}, remaining: {:?}", last, v1);
// Inserting and removing
v1.insert(1, 15); // Insert at index 1
println!("After insert: {:?}", v1);
let removed = v1.remove(0);
println!("Removed: {}, remaining: {:?}", removed, v1);
// Iteration
for item in &v1 {
println!("Item: {}", item);
}
// Modifying while iterating
for item in &mut v1 {
*item *= 2;
}
// Vector operations
println!("Length: {}", v1.len());
println!("Capacity: {}", v1.capacity());
println!("Is empty: {}", v1.is_empty());
// Resizing
v1.resize(5, 0);
println!("After resize: {:?}", v1);
// Sorting
let mut unsorted = vec![3, 1, 4, 1, 5, 9, 2, 6];
unsorted.sort();
println!("Sorted: {:?}", unsorted);
// Binary search (requires sorted data)
let index = unsorted.binary_search(&4);
println!("Index of 4: {:?}", index);
// Deduplication
let mut duplicates = vec![1, 1, 2, 3, 3, 4, 4, 5];
duplicates.dedup();
println!("After dedup: {:?}", duplicates);
}

VecDeque - Double-ended Queue

use std::collections::VecDeque;
fn main() {
// Creating a VecDeque
let mut deque: VecDeque<i32> = VecDeque::new();
// Adding to front and back
deque.push_back(3);
deque.push_back(4);
deque.push_front(2);
deque.push_front(1);
println!("Deque: {:?}", deque); // [1, 2, 3, 4]
// Removing from front and back
let front = deque.pop_front();
let back = deque.pop_back();
println!("Front: {:?}, Back: {:?}", front, back);
println!("Remaining: {:?}", deque);
// Peeking
if let Some(first) = deque.front() {
println!("First: {}", first);
}
if let Some(last) = deque.back() {
println!("Last: {}", last);
}
// Rotating
let mut deque = VecDeque::from(vec![1, 2, 3, 4, 5]);
// Rotate left
deque.rotate_left(2);
println!("Rotated left 2: {:?}", deque); // [3, 4, 5, 1, 2]
// Rotate right
deque.rotate_right(1);
println!("Rotated right 1: {:?}", deque); // [2, 3, 4, 5, 1]
// Using as a queue
let mut queue = VecDeque::new();
queue.push_back(1);
queue.push_back(2);
queue.push_back(3);
while let Some(item) = queue.pop_front() {
println!("Processing: {}", item);
}
// Using as a stack
let mut stack = VecDeque::new();
stack.push_front(1);
stack.push_front(2);
stack.push_front(3);
while let Some(item) = stack.pop_front() {
println!("Popped: {}", item);
}
// Capacity management
let mut deque = VecDeque::with_capacity(10);
println!("Capacity: {}", deque.capacity());
deque.push_back(1);
deque.push_back(2);
deque.shrink_to_fit();
println!("Shrunk capacity: {}", deque.capacity());
}

LinkedList - Doubly-linked List

use std::collections::LinkedList;
fn main() {
// Creating a LinkedList
let mut list1 = LinkedList::new();
list1.push_back(1);
list1.push_back(2);
list1.push_back(3);
let mut list2 = LinkedList::new();
list2.push_back(4);
list2.push_back(5);
list2.push_back(6);
println!("List1: {:?}", list1);
println!("List2: {:?}", list2);
// Appending lists
list1.append(&mut list2);
println!("After append: {:?}", list1);
println!("List2 now: {:?}", list2); // Empty
// Splitting
let mut list = LinkedList::new();
for i in 1..=10 {
list.push_back(i);
}
let split_point = 5;
let mut back_half = list.split_off(split_point);
println!("Front half: {:?}", list);
println!("Back half: {:?}", back_half);
// Iteration
for item in &list {
print!("{} ", item);
}
println!();
// Front and back operations
list.push_front(0);
list.push_back(11);
if let Some(first) = list.front() {
println!("First: {}", first);
}
if let Some(last) = list.back() {
println!("Last: {}", last);
}
// Removing elements
while let Some(item) = list.pop_front() {
print!("{} ", item);
}
println!();
// Use cases: when you need frequent insertion/removal at both ends
// But for most cases, Vec or VecDeque is more efficient
}

2. Map Containers

HashMap - Hash-based Map

use std::collections::HashMap;
fn main() {
// Creating a HashMap
let mut scores = HashMap::new();
// Inserting values
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
scores.insert(String::from("Red"), 25);
// Accessing values
let team_name = String::from("Blue");
if let Some(score) = scores.get(&team_name) {
println!("Blue score: {}", score);
}
// Iteration
for (key, value) in &scores {
println!("{}: {}", key, value);
}
// Updating values
scores.insert(String::from("Blue"), 15); // Overwrites
// Entry API - insert if not exists
scores.entry(String::from("Green")).or_insert(30);
scores.entry(String::from("Blue")).or_insert(100); // Won't change
println!("{:?}", scores);
// Updating based on old value
let text = "hello world wonderful world";
let mut word_counts = HashMap::new();
for word in text.split_whitespace() {
let count = word_counts.entry(word).or_insert(0);
*count += 1;
}
println!("Word counts: {:?}", word_counts);
// From iterator
let teams = vec![String::from("Blue"), String::from("Yellow")];
let initial_scores = vec![10, 50];
let scores: HashMap<_, _> = teams.into_iter()
.zip(initial_scores.into_iter())
.collect();
// Capacity and load factor
let mut map = HashMap::with_capacity(100);
println!("Capacity: {}", map.capacity());
map.shrink_to_fit();
println!("Shrunk capacity: {}", map.capacity());
// Removing entries
scores.remove(&String::from("Blue"));
// Checking existence
if scores.contains_key(&String::from("Yellow")) {
println!("Yellow exists");
}
// Getting multiple entries
let mut map = HashMap::new();
map.insert(1, "a");
map.insert(2, "b");
map.insert(3, "c");
for key in [1, 2, 4].iter() {
match map.get(key) {
Some(value) => println!("Key {}: {}", key, value),
None => println!("Key {} not found", key),
}
}
}

BTreeMap - Sorted Map

use std::collections::BTreeMap;
fn main() {
// Creating a BTreeMap
let mut map = BTreeMap::new();
// Inserting values (automatically sorted by key)
map.insert(3, "c");
map.insert(1, "a");
map.insert(2, "b");
map.insert(5, "e");
map.insert(4, "d");
println!("{:?}", map); // Sorted by key: {1: "a", 2: "b", 3: "c", 4: "d", 5: "e"}
// Range queries
let range: Vec<_> = map.range(2..=4).collect();
println!("Range 2..=4: {:?}", range);
// First and last entries
if let Some((key, value)) = map.first_key_value() {
println!("First: {}: {}", key, value);
}
if let Some((key, value)) = map.last_key_value() {
println!("Last: {}: {}", key, value);
}
// Lower bound and upper bound
if let Some((key, value)) = map.lower_bound(std::ops::Bound::Included(&2)) {
println!("Lower bound (>=2): {}: {}", key, value);
}
if let Some((key, value)) = map.upper_bound(std::ops::Bound::Included(&3)) {
println!("Upper bound (<=3): {}: {}", key, value);
}
// Splitting
let mut map = BTreeMap::new();
for i in 1..=10 {
map.insert(i, i * 10);
}
let split_map = map.split_off(&6);
println!("Original (1-5): {:?}", map);
println!("Split (6-10): {:?}", split_map);
// Navigation
let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(3, "c");
map.insert(5, "e");
if let Some(mut entry) = map.range(2..).next() {
println!("Next entry after 2: {:?}", entry);
}
// Custom ordering with strings
let mut word_map = BTreeMap::new();
word_map.insert("apple", 3);
word_map.insert("banana", 2);
word_map.insert("cherry", 5);
word_map.insert("date", 1);
println!("Sorted words: {:?}", word_map);
// Complex keys
#[derive(Ord, PartialOrd, Eq, PartialEq)]
struct Person {
name: String,
age: u32,
}
let mut people = BTreeMap::new();
people.insert(Person { name: "Alice".to_string(), age: 30 }, "Engineer");
people.insert(Person { name: "Bob".to_string(), age: 25 }, "Designer");
for (person, job) in &people {
println!("{} ({}) is a {}", person.name, person.age, job);
}
}

3. Set Containers

HashSet - Hash-based Set

use std::collections::HashSet;
fn main() {
// Creating a HashSet
let mut set1 = HashSet::new();
// Inserting values
set1.insert(1);
set1.insert(2);
set1.insert(3);
set1.insert(2); // Duplicate, won't be added
println!("set1: {:?}", set1);
// Checking membership
if set1.contains(&3) {
println!("Contains 3");
}
// Removing
set1.remove(&2);
// Set operations
let set2: HashSet<_> = vec![2, 3, 4, 5].into_iter().collect();
// Union
let union: HashSet<_> = set1.union(&set2).copied().collect();
println!("Union: {:?}", union);
// Intersection
let intersection: HashSet<_> = set1.intersection(&set2).copied().collect();
println!("Intersection: {:?}", intersection);
// Difference (elements in set1 but not set2)
let diff1: HashSet<_> = set1.difference(&set2).copied().collect();
println!("set1 - set2: {:?}", diff1);
// Symmetric difference (elements in either but not both)
let sym_diff: HashSet<_> = set1.symmetric_difference(&set2).copied().collect();
println!("Symmetric difference: {:?}", sym_diff);
// Subset and superset
let set3: HashSet<_> = vec![1, 3].into_iter().collect();
println!("set3 is subset of set1: {}", set3.is_subset(&set1));
println!("set1 is superset of set3: {}", set1.is_superset(&set3));
// Disjoint (no common elements)
let set4: HashSet<_> = vec![10, 20].into_iter().collect();
println!("set1 and set4 are disjoint: {}", set1.is_disjoint(&set4));
// From iterator
let words = "the quick brown fox jumps over the lazy dog";
let unique_words: HashSet<_> = words.split_whitespace().collect();
println!("Unique words: {}: {:?}", unique_words.len(), unique_words);
// Capacity management
let mut set = HashSet::with_capacity(100);
println!("Capacity: {}", set.capacity());
for i in 0..50 {
set.insert(i);
}
set.shrink_to_fit();
println!("Shrunk capacity: {}", set.capacity());
}

BTreeSet - Sorted Set

use std::collections::BTreeSet;
fn main() {
// Creating a BTreeSet
let mut set = BTreeSet::new();
// Inserting values (automatically sorted)
set.insert(5);
set.insert(1);
set.insert(3);
set.insert(2);
set.insert(4);
println!("{:?}", set); // [1, 2, 3, 4, 5]
// Range queries
let range: Vec<_> = set.range(2..=4).collect();
println!("Range 2..=4: {:?}", range);
// First and last
if let Some(first) = set.first() {
println!("First: {}", first);
}
if let Some(last) = set.last() {
println!("Last: {}", last);
}
// Navigation
if let Some(prev) = set.range(..3).next_back() {
println!("Previous to 3: {}", prev);
}
if let Some(next) = set.range(3..).next() {
println!("Next after 3: {}", next);
}
// Splitting
let mut set = BTreeSet::new();
for i in 1..=10 {
set.insert(i);
}
let split_set = set.split_off(&6);
println!("Original (1-5): {:?}", set);
println!("Split (6-10): {:?}", split_set);
// Set operations (same as HashSet)
let set1: BTreeSet<_> = vec![1, 2, 3, 4].into_iter().collect();
let set2: BTreeSet<_> = vec![3, 4, 5, 6].into_iter().collect();
let union: BTreeSet<_> = set1.union(&set2).copied().collect();
println!("Union: {:?}", union);
// Custom ordering with custom types
#[derive(Ord, PartialOrd, Eq, PartialEq, Debug)]
struct Person {
name: String,
age: u32,
}
let mut people = BTreeSet::new();
people.insert(Person { name: "Alice".to_string(), age: 30 });
people.insert(Person { name: "Bob".to_string(), age: 25 });
people.insert(Person { name: "Charlie".to_string(), age: 35 });
println!("People sorted by age then name: {:?}", people);
}

4. Queue and Stack Structures

BinaryHeap - Priority Queue

use std::collections::BinaryHeap;
fn main() {
// BinaryHeap is a max-heap by default
let mut heap = BinaryHeap::new();
// Inserting elements
heap.push(3);
heap.push(5);
heap.push(1);
heap.push(4);
heap.push(2);
println!("Heap: {:?}", heap);
// Peek at largest element
if let Some(max) = heap.peek() {
println!("Max: {}", max);
}
// Pop largest elements
while let Some(item) = heap.pop() {
println!("Popped: {}", item);
}
// Min-heap using Reverse
use std::cmp::Reverse;
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(4));
min_heap.push(Reverse(2));
while let Some(Reverse(item)) = min_heap.pop() {
println!("Min popped: {}", item);
}
// From iterator
let heap: BinaryHeap<_> = vec![3, 1, 4, 1, 5, 9].into_iter().collect();
println!("Heap from vec: {:?}", heap);
// Custom types (must implement Ord)
#[derive(Debug, Eq, PartialEq)]
struct Task {
priority: u32,
name: String,
}
// Implement Ord so higher priority comes first
impl Ord for Task {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.priority.cmp(&other.priority)
}
}
impl PartialOrd for Task {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
let mut tasks = BinaryHeap::new();
tasks.push(Task { priority: 3, name: "Low".to_string() });
tasks.push(Task { priority: 5, name: "High".to_string() });
tasks.push(Task { priority: 4, name: "Medium".to_string() });
while let Some(task) = tasks.pop() {
println!("Task: {} (priority {})", task.name, task.priority);
}
// Heap operations
let mut heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
// Drain
let drained: Vec<_> = heap.drain().collect();
println!("Drained: {:?}", drained);
println!("Heap empty: {}", heap.is_empty());
}

Custom Stack Implementation

#[derive(Debug)]
struct Stack<T> {
elements: Vec<T>,
}
impl<T> Stack<T> {
fn new() -> Self {
Stack {
elements: Vec::new(),
}
}
fn push(&mut self, item: T) {
self.elements.push(item);
}
fn pop(&mut self) -> Option<T> {
self.elements.pop()
}
fn peek(&self) -> Option<&T> {
self.elements.last()
}
fn is_empty(&self) -> bool {
self.elements.is_empty()
}
fn size(&self) -> usize {
self.elements.len()
}
fn clear(&mut self) {
self.elements.clear();
}
fn into_iter(self) -> std::vec::IntoIter<T> {
self.elements.into_iter()
}
fn iter(&self) -> std::slice::Iter<T> {
self.elements.iter()
}
fn iter_mut(&mut self) -> std::slice::IterMut<T> {
self.elements.iter_mut()
}
}
impl<T> Extend<T> for Stack<T> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
self.elements.extend(iter);
}
}
fn main() {
let mut stack = Stack::new();
stack.push(1);
stack.push(2);
stack.push(3);
println!("Stack: {:?}", stack);
println!("Size: {}", stack.size());
if let Some(top) = stack.peek() {
println!("Top: {}", top);
}
while let Some(item) = stack.pop() {
println!("Popped: {}", item);
}
println!("Is empty: {}", stack.is_empty());
// Using Extend
stack.extend(vec![4, 5, 6]);
println!("After extend: {:?}", stack);
// Iteration
for item in stack.iter() {
println!("Item: {}", item);
}
// Consuming iteration
for item in stack.into_iter() {
println!("Consumed: {}", item);
}
// stack is moved, can't use anymore
}

5. Custom Data Structures

Linked List Implementation

use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug)]
struct Node<T> {
value: T,
next: Option<Rc<RefCell<Node<T>>>>,
prev: Option<Rc<RefCell<Node<T>>>>,
}
#[derive(Debug)]
struct DoublyLinkedList<T> {
head: Option<Rc<RefCell<Node<T>>>>,
tail: Option<Rc<RefCell<Node<T>>>>,
length: usize,
}
impl<T> DoublyLinkedList<T> {
fn new() -> Self {
DoublyLinkedList {
head: None,
tail: None,
length: 0,
}
}
fn push_front(&mut self, value: T) {
let new_node = Rc::new(RefCell::new(Node {
value,
next: self.head.clone(),
prev: None,
}));
if let Some(old_head) = &self.head {
old_head.borrow_mut().prev = Some(new_node.clone());
} else {
self.tail = Some(new_node.clone());
}
self.head = Some(new_node);
self.length += 1;
}
fn push_back(&mut self, value: T) {
let new_node = Rc::new(RefCell::new(Node {
value,
next: None,
prev: self.tail.clone(),
}));
if let Some(old_tail) = &self.tail {
old_tail.borrow_mut().next = Some(new_node.clone());
} else {
self.head = Some(new_node.clone());
}
self.tail = Some(new_node);
self.length += 1;
}
fn pop_front(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
let mut head_ref = old_head.borrow_mut();
self.head = head_ref.next.clone();
if let Some(new_head) = &self.head {
new_head.borrow_mut().prev = None;
} else {
self.tail = None;
}
self.length -= 1;
std::mem::replace(&mut head_ref.value, unsafe { std::mem::uninitialized() })
})
}
fn pop_back(&mut self) -> Option<T> {
self.tail.take().map(|old_tail| {
let mut tail_ref = old_tail.borrow_mut();
self.tail = tail_ref.prev.clone();
if let Some(new_tail) = &self.tail {
new_tail.borrow_mut().next = None;
} else {
self.head = None;
}
self.length -= 1;
std::mem::replace(&mut tail_ref.value, unsafe { std::mem::uninitialized() })
})
}
fn len(&self) -> usize {
self.length
}
fn is_empty(&self) -> bool {
self.length == 0
}
fn front(&self) -> Option<&T> {
self.head.as_ref().map(|node| unsafe {
&(*node.as_ptr()).value
})
}
fn back(&self) -> Option<&T> {
self.tail.as_ref().map(|node| unsafe {
&(*node.as_ptr()).value
})
}
}
impl<T> Drop for DoublyLinkedList<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
fn main() {
let mut list = DoublyLinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_front(0);
println!("List length: {}", list.len());
println!("Front: {:?}", list.front());
println!("Back: {:?}", list.back());
while let Some(value) = list.pop_front() {
println!("Popped: {}", value);
}
}

Binary Search Tree

use std::cmp::Ordering;
#[derive(Debug)]
struct TreeNode<T> {
value: T,
left: Option<Box<TreeNode<T>>>,
right: Option<Box<TreeNode<T>>>,
}
#[derive(Debug)]
struct BinarySearchTree<T> {
root: Option<Box<TreeNode<T>>>,
}
impl<T: Ord> BinarySearchTree<T> {
fn new() -> Self {
BinarySearchTree { root: None }
}
fn insert(&mut self, value: T) {
let mut current = &mut self.root;
while let Some(node) = current {
match value.cmp(&node.value) {
Ordering::Less => current = &mut node.left,
Ordering::Greater => current = &mut node.right,
Ordering::Equal => return, // No duplicates
}
}
*current = Some(Box::new(TreeNode {
value,
left: None,
right: None,
}));
}
fn contains(&self, value: &T) -> bool {
let mut current = &self.root;
while let Some(node) = current {
match value.cmp(&node.value) {
Ordering::Less => current = &node.left,
Ordering::Greater => current = &node.right,
Ordering::Equal => return true,
}
}
false
}
fn inorder_traversal(&self) -> Vec<&T> {
let mut result = Vec::new();
self.inorder_helper(&self.root, &mut result);
result
}
fn inorder_helper<'a>(&self, node: &'a Option<Box<TreeNode<T>>>, result: &mut Vec<&'a T>) {
if let Some(node) = node {
self.inorder_helper(&node.left, result);
result.push(&node.value);
self.inorder_helper(&node.right, result);
}
}
fn preorder_traversal(&self) -> Vec<&T> {
let mut result = Vec::new();
self.preorder_helper(&self.root, &mut result);
result
}
fn preorder_helper<'a>(&self, node: &'a Option<Box<TreeNode<T>>>, result: &mut Vec<&'a T>) {
if let Some(node) = node {
result.push(&node.value);
self.preorder_helper(&node.left, result);
self.preorder_helper(&node.right, result);
}
}
fn postorder_traversal(&self) -> Vec<&T> {
let mut result = Vec::new();
self.postorder_helper(&self.root, &mut result);
result
}
fn postorder_helper<'a>(&self, node: &'a Option<Box<TreeNode<T>>>, result: &mut Vec<&'a T>) {
if let Some(node) = node {
self.postorder_helper(&node.left, result);
self.postorder_helper(&node.right, result);
result.push(&node.value);
}
}
fn min(&self) -> Option<&T> {
let mut current = &self.root;
while let Some(node) = current {
if node.left.is_some() {
current = &node.left;
} else {
return Some(&node.value);
}
}
None
}
fn max(&self) -> Option<&T> {
let mut current = &self.root;
while let Some(node) = current {
if node.right.is_some() {
current = &node.right;
} else {
return Some(&node.value);
}
}
None
}
fn height(&self) -> usize {
self.height_helper(&self.root)
}
fn height_helper(&self, node: &Option<Box<TreeNode<T>>>) -> usize {
match node {
Some(node) => {
1 + std::cmp::max(
self.height_helper(&node.left),
self.height_helper(&node.right),
)
}
None => 0,
}
}
}
fn main() {
let mut bst = BinarySearchTree::new();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.insert(6);
bst.insert(8);
println!("Contains 4: {}", bst.contains(&4));
println!("Contains 9: {}", bst.contains(&9));
println!("Inorder: {:?}", bst.inorder_traversal());
println!("Preorder: {:?}", bst.preorder_traversal());
println!("Postorder: {:?}", bst.postorder_traversal());
println!("Min: {:?}", bst.min());
println!("Max: {:?}", bst.max());
println!("Height: {}", bst.height());
}

6. Graph Structures

Graph Implementation

use std::collections::{HashMap, HashSet, VecDeque};
#[derive(Debug)]
struct Graph<T> {
adjacency_list: HashMap<T, HashSet<T>>,
}
impl<T: std::hash::Hash + Eq + Clone + std::fmt::Debug> Graph<T> {
fn new() -> Self {
Graph {
adjacency_list: HashMap::new(),
}
}
fn add_vertex(&mut self, vertex: T) {
self.adjacency_list.entry(vertex).or_insert(HashSet::new());
}
fn add_edge(&mut self, from: T, to: T) {
self.adjacency_list.entry(from.clone()).or_insert(HashSet::new()).insert(to.clone());
self.adjacency_list.entry(to).or_insert(HashSet::new());
}
fn add_bidirectional_edge(&mut self, a: T, b: T) {
self.add_edge(a.clone(), b.clone());
self.add_edge(b, a);
}
fn get_neighbors(&self, vertex: &T) -> Option<&HashSet<T>> {
self.adjacency_list.get(vertex)
}
fn bfs(&self, start: T) -> Vec<T> {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
let mut result = Vec::new();
visited.insert(start.clone());
queue.push_back(start);
while let Some(vertex) = queue.pop_front() {
result.push(vertex.clone());
if let Some(neighbors) = self.adjacency_list.get(&vertex) {
for neighbor in neighbors {
if !visited.contains(neighbor) {
visited.insert(neighbor.clone());
queue.push_back(neighbor.clone());
}
}
}
}
result
}
fn dfs(&self, start: T) -> Vec<T> {
let mut visited = HashSet::new();
let mut result = Vec::new();
self.dfs_helper(start, &mut visited, &mut result);
result
}
fn dfs_helper(&self, vertex: T, visited: &mut HashSet<T>, result: &mut Vec<T>) {
visited.insert(vertex.clone());
result.push(vertex.clone());
if let Some(neighbors) = self.adjacency_list.get(&vertex) {
for neighbor in neighbors {
if !visited.contains(neighbor) {
self.dfs_helper(neighbor.clone(), visited, result);
}
}
}
}
fn has_cycle(&self) -> bool {
let mut visited = HashSet::new();
let mut recursion_stack = HashSet::new();
for vertex in self.adjacency_list.keys() {
if !visited.contains(vertex) {
if self.has_cycle_helper(vertex, &mut visited, &mut recursion_stack) {
return true;
}
}
}
false
}
fn has_cycle_helper(&self, vertex: &T, visited: &mut HashSet<T>, stack: &mut HashSet<T>) -> bool {
visited.insert(vertex.clone());
stack.insert(vertex.clone());
if let Some(neighbors) = self.adjacency_list.get(vertex) {
for neighbor in neighbors {
if !visited.contains(neighbor) {
if self.has_cycle_helper(neighbor, visited, stack) {
return true;
}
} else if stack.contains(neighbor) {
return true;
}
}
}
stack.remove(vertex);
false
}
fn shortest_path(&self, start: T, end: T) -> Option<Vec<T>> {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
let mut parent = HashMap::new();
visited.insert(start.clone());
queue.push_back(start.clone());
while let Some(vertex) = queue.pop_front() {
if vertex == end {
return Some(self.reconstruct_path(parent, start, end));
}
if let Some(neighbors) = self.adjacency_list.get(&vertex) {
for neighbor in neighbors {
if !visited.contains(neighbor) {
visited.insert(neighbor.clone());
parent.insert(neighbor.clone(), vertex.clone());
queue.push_back(neighbor.clone());
}
}
}
}
None
}
fn reconstruct_path(&self, parent: HashMap<T, T>, start: T, end: T) -> Vec<T> {
let mut path = Vec::new();
let mut current = end;
path.push(current.clone());
while current != start {
if let Some(prev) = parent.get(&current) {
path.push(prev.clone());
current = prev.clone();
} else {
break;
}
}
path.reverse();
path
}
fn vertices(&self) -> Vec<&T> {
self.adjacency_list.keys().collect()
}
fn edge_count(&self) -> usize {
self.adjacency_list.values().map(|neighbors| neighbors.len()).sum()
}
fn degree(&self, vertex: &T) -> Option<usize> {
self.adjacency_list.get(vertex).map(|neighbors| neighbors.len())
}
}
fn main() {
let mut graph = Graph::new();
graph.add_bidirectional_edge(1, 2);
graph.add_bidirectional_edge(1, 3);
graph.add_bidirectional_edge(2, 4);
graph.add_bidirectional_edge(3, 4);
graph.add_bidirectional_edge(4, 5);
println!("Graph: {:?}", graph);
println!("Vertices: {:?}", graph.vertices());
println!("Edge count: {}", graph.edge_count());
println!("Degree of 4: {:?}", graph.degree(&4));
println!("BFS from 1: {:?}", graph.bfs(1));
println!("DFS from 1: {:?}", graph.dfs(1));
println!("Has cycle: {}", graph.has_cycle());
if let Some(path) = graph.shortest_path(1, 5) {
println!("Shortest path from 1 to 5: {:?}", path);
}
// Directed graph with cycle
let mut directed = Graph::new();
directed.add_edge(1, 2);
directed.add_edge(2, 3);
directed.add_edge(3, 1);
println!("Directed has cycle: {}", directed.has_cycle());
}

7. Specialized Structures

BitVec - Efficient Boolean Storage

struct BitVec {
data: Vec<u64>,
len: usize,
}
impl BitVec {
fn new() -> Self {
BitVec {
data: Vec::new(),
len: 0,
}
}
fn with_capacity(capacity: usize) -> Self {
let data_capacity = (capacity + 63) / 64;
BitVec {
data: Vec::with_capacity(data_capacity),
len: 0,
}
}
fn push(&mut self, value: bool) {
let index = self.len;
self.len += 1;
let word_index = index / 64;
let bit_index = index % 64;
if word_index >= self.data.len() {
self.data.push(0);
}
if value {
self.data[word_index] |= 1 << bit_index;
} else {
self.data[word_index] &= !(1 << bit_index);
}
}
fn get(&self, index: usize) -> Option<bool> {
if index >= self.len {
return None;
}
let word_index = index / 64;
let bit_index = index % 64;
Some((self.data[word_index] & (1 << bit_index)) != 0)
}
fn set(&mut self, index: usize, value: bool) -> Option<()> {
if index >= self.len {
return None;
}
let word_index = index / 64;
let bit_index = index % 64;
if value {
self.data[word_index] |= 1 << bit_index;
} else {
self.data[word_index] &= !(1 << bit_index);
}
Some(())
}
fn len(&self) -> usize {
self.len
}
fn capacity(&self) -> usize {
self.data.len() * 64
}
fn iter(&self) -> BitVecIter {
BitVecIter {
bitvec: self,
index: 0,
}
}
fn and(&self, other: &BitVec) -> Option<BitVec> {
if self.len != other.len {
return None;
}
let mut result = BitVec::with_capacity(self.len);
for i in 0..self.data.len() {
result.data.push(self.data[i] & other.data[i]);
}
result.len = self.len;
Some(result)
}
fn or(&self, other: &BitVec) -> Option<BitVec> {
if self.len != other.len {
return None;
}
let mut result = BitVec::with_capacity(self.len);
for i in 0..self.data.len() {
result.data.push(self.data[i] | other.data[i]);
}
result.len = self.len;
Some(result)
}
fn xor(&self, other: &BitVec) -> Option<BitVec> {
if self.len != other.len {
return None;
}
let mut result = BitVec::with_capacity(self.len);
for i in 0..self.data.len() {
result.data.push(self.data[i] ^ other.data[i]);
}
result.len = self.len;
Some(result)
}
fn not(&self) -> BitVec {
let mut result = BitVec::with_capacity(self.len);
for i in 0..self.data.len() {
result.data.push(!self.data[i]);
}
result.len = self.len;
result
}
}
struct BitVecIter<'a> {
bitvec: &'a BitVec,
index: usize,
}
impl<'a> Iterator for BitVecIter<'a> {
type Item = bool;
fn next(&mut self) -> Option<Self::Item> {
if self.index < self.bitvec.len() {
let value = self.bitvec.get(self.index).unwrap();
self.index += 1;
Some(value)
} else {
None
}
}
}
fn main() {
let mut bits = BitVec::new();
bits.push(true);
bits.push(false);
bits.push(true);
bits.push(true);
bits.push(false);
println!("Length: {}", bits.len());
println!("Capacity: {}", bits.capacity());
for i in 0..bits.len() {
println!("bit[{}] = {}", i, bits.get(i).unwrap());
}
bits.set(1, true).unwrap();
println!("After setting bit 1: {:?}", bits.get(1).unwrap());
println!("Iterating:");
for bit in bits.iter() {
print!("{} ", bit as u8);
}
println!();
let mut bits2 = BitVec::new();
bits2.push(true);
bits2.push(true);
bits2.push(false);
bits2.push(false);
bits2.push(true);
let and_result = bits.and(&bits2).unwrap();
println!("AND: {:?}", and_result.iter().collect::<Vec<_>>());
let or_result = bits.or(&bits2).unwrap();
println!("OR: {:?}", or_result.iter().collect::<Vec<_>>());
let not_result = bits.not();
println!("NOT: {:?}", not_result.iter().collect::<Vec<_>>());
}

LRU Cache

use std::collections::HashMap;
use std::hash::Hash;
struct LRUCache<K, V> {
capacity: usize,
cache: HashMap<K, (V, usize)>,
usage: Vec<K>,
}
impl<K: Eq + Hash + Clone, V> LRUCache<K, V> {
fn new(capacity: usize) -> Self {
LRUCache {
capacity,
cache: HashMap::with_capacity(capacity),
usage: Vec::with_capacity(capacity),
}
}
fn get(&mut self, key: &K) -> Option<&V> {
if let Some((value, _)) = self.cache.get(key) {
// Update usage
if let Some(pos) = self.usage.iter().position(|k| k == key) {
self.usage.remove(pos);
}
self.usage.push(key.clone());
Some(value)
} else {
None
}
}
fn put(&mut self, key: K, value: V) {
if self.cache.contains_key(&key) {
// Update existing
if let Some(pos) = self.usage.iter().position(|k| k == &key) {
self.usage.remove(pos);
}
} else if self.cache.len() >= self.capacity {
// Evict least recently used
if let Some(least_used) = self.usage.first() {
self.cache.remove(least_used);
self.usage.remove(0);
}
}
self.cache.insert(key.clone(), (value, 0));
self.usage.push(key);
}
fn contains_key(&self, key: &K) -> bool {
self.cache.contains_key(key)
}
fn len(&self) -> usize {
self.cache.len()
}
fn is_empty(&self) -> bool {
self.cache.is_empty()
}
fn clear(&mut self) {
self.cache.clear();
self.usage.clear();
}
fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
self.cache.iter().map(|(k, (v, _))| (k, v))
}
}
fn main() {
let mut cache = LRUCache::new(3);
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
println!("Cache size: {}", cache.len());
println!("Get A: {:?}", cache.get(&"A"));
cache.put("D", 4); // Should evict B (least recently used)
println!("Contains B: {}", cache.contains_key(&"B"));
println!("Contains A: {}", cache.contains_key(&"A"));
println!("Contains C: {}", cache.contains_key(&"C"));
println!("Contains D: {}", cache.contains_key(&"D"));
println!("All items:");
for (key, value) in cache.iter() {
println!("  {}: {}", key, value);
}
}

Conclusion

Rust's data structures provide a solid foundation for building efficient and safe programs:

Key Takeaways

  1. Sequence Containers: Vec, VecDeque, LinkedList for ordered data
  2. Map Containers: HashMap, BTreeMap for key-value associations
  3. Set Containers: HashSet, BTreeSet for unique elements
  4. Priority Queues: BinaryHeap for priority-based processing
  5. Custom Structures: Ability to create tailored data structures
  6. Memory Efficiency: Control over memory layout and allocation
  7. Type Safety: Generic structures maintain type information

Best Practices

  1. Choose the right structure for your use case
  2. Consider performance characteristics (O(1) vs O(log n))
  3. Use appropriate capacity to avoid reallocations
  4. Leverage iterators for efficient traversal
  5. Implement custom structures when standard ones don't fit
  6. Consider memory overhead of different structures
  7. Use entry API for efficient HashMap operations

Performance Guidelines

  • Vec: Fast index access, slow insert/remove in middle
  • HashMap: Fast lookup, unordered, good for most cases
  • BTreeMap: Ordered, good for range queries
  • VecDeque: Good for queue/stack operations
  • BinaryHeap: Good for priority queues
  • LinkedList: Rarely needed, high overhead

Rust's standard library provides a rich set of data structures, and the language's ownership system ensures they are used safely and efficiently.

Category : RUST

Leave a Reply

Your email address will not be published. Required fields are marked *


Macro Nepal Helper