Comprehensive Guide to Data Structures

& Data Types in Rust

Table of Contents

1. Overview
2. Core Data Structures in Rust
Arrays & Slices
Vectors ( Vec )
Tuples
HashMap and HashSet
BTreeMap and BTreeSet
LinkedList
VecDeque
BinaryHeap
Op!on and Result
Rc, Arc, Cell, RefCell
3. Data Types and Memory Usage Table
4. Summary Table: Data Structure Pros/Cons
5. References

Overview

Rust provides a rich set of standard library data structures designed for safety,
concurrency, and performance. Choosing the correct data structure is crucial for
wri!ng efficient and maintainable code. This guide covers the main structures, their
use cases, advantages, disadvantages, and memory characteris!cs.
Core Data Structures in Rust

Arrays & Slices

Defini!on: Fixed-size collec!ons of elements of the same type.

Syntax:

let arr: [i32; 4] = [1, 2, 3, 4];

let slice: &[i32] = &arr[1..3];

Use Case: Known, constant size at compile !me (e.g., coordinates, color values).
Pros: Fast O(1) indexing, stack-allocated, no heap alloca!on.
Cons: Size is fixed; cannot grow or shrink.

Vectors ( Vec )

Defini!on: Growable, heap-allocated arrays.

Syntax:

let mut v: Vec<i32> = Vec::new();

[Link](10);

Use Case: Dynamic lists, buffers, collec!ons where size changes.

Pros: Flexible size, O(1) push/pop (amor!zed), random access.
Cons: Occasional realloca!ons, not thread-safe by default.

Tuples

Defini!on: Fixed-size collec!ons of elements of poten!ally different types.

Syntax:

let t: (i32, f64, char) = (42, 3.14, 'x');

Use Case: Returning mul!ple values, grouping heterogeneous data.

 Pros: Heterogeneous storage, pa$ern matching.
Cons: Fixed size, can be unwieldy for large collec!ons.

HashMap and HashSet

Defini!on: Unordered key-value store and unique value set (hash-based).

Syntax:

use std::collections::HashMap;
let mut map = HashMap::new();
[Link]("key", 42);

Use Case: Fast lookup, dic!onaries, caches, deduplica!on.

Pros: O(1) average insert/get/remove, flexible key types.
Cons: O(n) worst-case (rare), keys/values must implement Hash , Eq .

BTreeMap and BTreeSet

Defini!on: Ordered key-value store and ordered unique value set (tree-based).
Syntax:

use std::collections::BTreeMap;
let mut map = BTreeMap::new();
[Link]("key", 42);

Use Case: Sorted maps, range queries, ordered itera!on.

Pros: O(log n) opera!ons, ordered keys, efficient range queries.
Cons: Slightly slower than HashMap for single lookups, more memory per node.

LinkedList

Defini!on: Doubly linked list.

Syntax:
 use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);

Use Case: Frequent inser!ons/removals at both ends, queue/deque pa$erns.

Pros: O(1) inser!on/removal at ends.
Cons: O(n) traversal, cache-unfriendly, high memory overhead.

VecDeque

Defini!on: Double-ended queue using a ring buffer.

Syntax:

use std::collections::VecDeque;
let mut deque = VecDeque::new();
deque.push_front(1);
deque.push_back(2);

Use Case: Queues, deques, sliding windows.

Pros: O(1) push/pop at both ends, cache-friendly.
Cons: Uses more memory than Vec for small collec!ons.

BinaryHeap

Defini!on: Priority queue based on a binary heap.

Syntax:

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
[Link](7);

Use Case: Scheduling, finding largest/smallest elements efficiently.

Pros: O(log n) push/pop, O(1) peek.
Cons: No random access, not sorted a%er inser!on.
Op!on and Result

Defini!on: Enums for op!onal values and error handling.

Syntax:

let o: Option<i32> = Some(5);

let r: Result<i32, &str> = Ok(10);

Use Case: Safe error handling, absence/presence of values.

Pros: Enforces correctness, pa$ern matching.
Cons: Requires explicit handling of None / Err .

Rc, Arc, Cell, RefCell

Defini!on: Smart pointers and interior mutability types.

Rc : Reference-counted single-threaded shared ownership.
Arc : Atomic reference-counted, thread-safe.
Cell / RefCell : Interior mutability for single-threaded use.
Use Case: Shared ownership, run!me-checked mutability, concurrency.
Pros: Safe shared mutability, run!me checks, thread safety ( Arc ).
Cons: Overhead of coun!ng/locking, run!me panics on viola!ons.

Data Types and Memory Usage Table

Typical Size
Rust Type Descrip!on Example
(x86_64)

8-bit unsigned
u8 1 byte let a: u8 = 255;
integer

8-bit signed
i8 1 byte let a: i8 = -128;
integer

16-bit unsigned
u16 integer 2 bytes let b: u16 = 65535;

16-bit signed
i16 2 bytes let b: i16 = -32768;
integer

32-bit unsigned let c: u32 =

u32 4 bytes
integer 4294967295;

32-bit signed let c: i32 =

i32 4 bytes
integer -2147483648;

64-bit unsigned let d: u64 =

u64 8 bytes
integer 18446744073709551615;

64-bit signed let d: i64 =

i64 8 bytes
integer -9223372036854775808;

Pointer-sized let p: usize =

usize 8 bytes
unsigned int 0x7fff_ffff;

Pointer-sized
isize 8 bytes let p: isize = -1;
signed int

f32 32-bit float 4 bytes let e: f32 = 3.14;

f64 64-bit float 8 bytes let f: f64 = 2.718;

Unicode scalar
char 4 bytes let g: char = ' ';
value

bool Boolean 1 byte let h: bool = true;

Heap-allocated let s: String =

String 24 bytes*
string "hi".into();

&str String slice (ref) 16 bytes* let s: &str = "hi";

[T; N] Array N * size_of::() [1, 2, 3]

24 bytes +
Vec<T> Dynamic array Vec::new()
data*
 Option<T> Op!onal value size_of::() Option<i32>

* String and Vec store data on the heap; the stack part holds pointer, length, capacity.

Summary Table: Data Structure Pros/Cons

Data
Use Case Pros Cons
Structure

Fixed-size data, Fast, cache- Fixed size, no

Array/Slice
stack alloc friendly grow/shrink

Dynamic Flexible, fast Occasional realloc,

Vec
list/buffer random access heap alloc

Frequent
Slow traversal, high
LinkedList insert/remove O(1) at ends
overhead
ends

Double-ended O(1) ends, cache- More memory than

VecDeque
queue friendly Vec

O(n) worst-case, hash

HashMap Fast lookup by key O(1) average ops
needed

Sorted map, range Ordered, O(log n) Slightly slower than

BTreeMap
queries ops HashMap

Unique, unordered O(n) worst-case, hash

HashSet O(1) average ops
collec!on needed

Unique, ordered Ordered, O(log n) Slightly slower than

BTreeSet
collec!on ops HashSet

BinaryHeap Priority queue O(log n) push/pop No random access

Overhead, possible
Rc/Arc Shared ownership Safe, flexible
 cycles

Mutability in Run!me panics on

Cell/RefCell Interior mutability
immutable ctx borrow errors

References

Rust Standard Library Documenta!on

The Rust Book
std::collec!ons module
std::mem::size_of