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.