4.4 · VecDeque, LinkedList, and BinaryHeap

Domain 4 — Collections Deep Dive Duration: ~15 minutes Library components: std::collections::VecDeque, std::collections::LinkedList, std::collections::BinaryHeap

Introduction

Vec is the most common sequence collection in Rust. The standard library has three more sequence collections, and each one has a specific use:

• VecDeque is a growable ring buffer in one contiguous allocation. Push and pop are amortized O(1) at both ends. In a Vec, an operation at the front is O(n).
• LinkedList is a doubly-linked list. Push and pop are O(1) at both ends, and the join of two lists is O(1). It is almost never the correct selection, because each node is a separate heap allocation. Separate allocations remove CPU cache locality.
• BinaryHeap is a max-heap that you can use as a priority queue. push and pop are O(log n), and peek is O(1). The heap invariant keeps the largest element at the top.

This tutorial shows:

• How to create and change a VecDeque: push_front, push_back, pop_front, pop_back, and the push_front_mut/push_back_mut/insert_mut variants (stabilized in 1.95).
• How to keep only the newest elements with retain_back (stabilized in 1.99).
• How to examine the internal layout of the ring buffer with as_slices, and how to make it contiguous with make_contiguous.
• How to use a VecDeque for a sliding window.
• Why LinkedList is rarely the correct selection, and the few cases where it is.
• BinaryHeap as a max-heap priority queue: peek, push, pop, into_sorted_vec.
• How to make a min-heap with the Reverse wrapper.
• The relaxed T: Ord bounds of some BinaryHeap methods in Rust 1.94.

VecDeque: A Growable Ring Buffer

VecDeque<T> keeps its elements in one heap allocation. It uses a head pointer and a tail pointer, so the two ends of the buffer are accessible in amortized O(1) time. Internally, the buffer is circular. When the tail goes past the end of the allocation, it continues at the start.

Figure: VecDeque Ring Buffer Layout

Creation

use std::collections::VecDeque;

// An empty deque of string slices.
let mut deque: VecDeque<&str> = VecDeque::new();
// An empty deque with space for at least 64 elements.
let prealloc: VecDeque<i32> = VecDeque::with_capacity(64);

with_capacity allocates space for at least the specified number of elements. Use it when you know the expected size, to prevent reallocations.

Push and Pop at Both Ends

The four basic operations are push_front, push_back, pop_front, and pop_back. Each one is amortized O(1):

// `deque` is the empty VecDeque<&str> from the previous snippet.
deque.push_back("middle");
deque.push_front("first");   // goes before "middle"
deque.push_back("last");     // goes after "middle"
// deque is now ["first", "middle", "last"]

deque.pop_front(); // returns Some("first")
deque.pop_back();  // returns Some("last")
// deque is now ["middle"]

Thus VecDeque is the usual selection for a FIFO queue (push at the back, pop from the front) and for access at both ends. A Vec does these operations efficiently only at the back. insert(0, _) on a Vec moves each element.

To remove many elements in one call, use truncate or retain_back. truncate(n) keeps the first n elements and drops the remainder from the back. retain_back(n) (stabilized in 1.99) keeps the last n elements and drops the remainder from the front. The capacity does not change. If n is not smaller than the length, the call does nothing:

use std::collections::VecDeque;

let mut oldest: VecDeque<u32> = (1..=6).collect();   // [1, 2, 3, 4, 5, 6]
oldest.truncate(2);                                  // keep the FIRST 2
assert_eq!(oldest, [1, 2]);

let mut newest: VecDeque<u32> = (1..=6).collect();   // [1, 2, 3, 4, 5, 6]
newest.retain_back(2);                               // keep the LAST 2
assert_eq!(newest, [5, 6]);

A log buffer that must keep only the most recent entries is the usual application. 04_19_vecdeque_retain_back.rs prints:

truncate(2):    [1, 2]
retain_back(2): [5, 6]
retain_back(10) on 2 elements: [5, 6]
recent log entries: ["event 6", "event 7", "event 8"]
drain(..len - 2) gives the same result: [5, 6]

All assertions passed.

The *_mut Variants: a Reference to the New Element

Since Rust 1.95, push_front_mut, push_back_mut, and insert_mut insert an element and return &mut T to that element. Vec::push_mut does the same for Vec. You do not need front_mut().unwrap() to change the new element immediately:

let mut scores: VecDeque<i32> = VecDeque::from([5]);
let front = scores.push_front_mut(1);   // front: &mut i32, points to the new 1
*front += 100;                          // the front element is now 101
let back = scores.push_back_mut(9);     // back: &mut i32, points to the new 9
*back *= 2;                             // the back element is now 18
let mid = scores.insert_mut(1, 42);     // inserts 42 at index 1
*mid += 1;                              // the element at index 1 is now 43
assert_eq!(scores, [101, 43, 5, 18]);

Indexing and Safe Access

VecDeque implements Index<usize>, so buf[i] is valid. get(i) is the checked form and returns Option<&T>. front() and back() return a reference to the element at each end:

let buf: VecDeque<i32> = VecDeque::from([10, 20, 30, 40, 50]);
assert_eq!(buf[0], 10);             // an index that is out of bounds panics
assert_eq!(buf.get(99), None);      // get returns None, it does not panic
assert_eq!(buf.front(), Some(&10)); // the first element
assert_eq!(buf.back(), Some(&50));  // the last element

Sliding Window Pattern

A common use of VecDeque is a sliding window with a constant size on a data stream. Push each new element at the back. When the window is full, pop the oldest element from the front:

let data_stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let window_size = 4;
let mut window: VecDeque<i32> = VecDeque::with_capacity(window_size);

for &val in &data_stream {
    // The window is full: remove the oldest value before the push.
    if window.len() == window_size {
        window.pop_front();
    }
    window.push_back(val);
    // Print only complete windows (the first 3 iterations print nothing).
    if window.len() == window_size {
        let sum: i32 = window.iter().sum();
        println!("  window={window:?}, sum={sum}");
    }
}

Each iteration does a maximum of one pop and one push, and each is O(1). With a Vec, the removal of the front element is O(n).

as_slices: Viewing the Ring Buffer

VecDeque is a circular buffer, so its elements are not always contiguous in memory. After some pushes and pops, the head pointer can be at a later position. Then the logical sequence continues from the end of the allocation to its start. as_slices() returns two &[T] slices, front and back. Together they contain all the elements in order:

let mut ring: VecDeque<u8> = VecDeque::with_capacity(4);
ring.push_back(1);
ring.push_back(2);
ring.push_back(3);
ring.pop_front();       // removes 1: the head moves forward
ring.push_back(4);
ring.push_back(5);      // the buffer can wrap to the start of the allocation

let (front, back) = ring.as_slices();
// front and back together contain [2, 3, 4, 5] in order

Use as_slices when an API needs slices, or when you do not want to copy the elements into a Vec.

make_contiguous: Linearizing the Buffer

If you need one contiguous &mut [T] slice (for example, to sort the elements in place), call make_contiguous(). It moves the elements in the internal buffer until they are in one sequence:

let mut buf: VecDeque<i32> = VecDeque::from([10, 20, 30, 40, 50]);
buf.push_front(0);    // [0, 10, 20, 30, 40, 50]
buf.push_front(-1);   // [-1, 0, 10, 20, 30, 40, 50]
let contiguous = buf.make_contiguous();
// contiguous is &mut [-1, 0, 10, 20, 30, 40, 50]

After make_contiguous, the second slice from as_slices() is empty.

Converting Between Vec and VecDeque

VecDeque implements From<Vec<T>>, and Vec<T> implements From<VecDeque<T>>. Thus each conversion is one call:

let v = vec![1, 2, 3, 4, 5];
let d: VecDeque<i32> = VecDeque::from(v);      // moves the Vec, no copy
let back_to_vec: Vec<i32> = Vec::from(d);      // moves the VecDeque

The conversion from Vec to VecDeque is O(1), because it uses the same allocation. The opposite conversion can need to move the elements of the ring buffer until they are contiguous. Then it gives the allocation to the Vec.

04_12_vecdeque.rs prints:

empty: len=0, with_capacity(64): cap≥64=true

after pushes: ["first", "middle", "last"]
after pops: ["middle"]

push_*_mut/insert_mut: [101, 43, 5, 18]

front=Some(10), back=Some(50)

sliding window (size 4):
  window=[1, 2, 3, 4], sum=10
  window=[2, 3, 4, 5], sum=14
  window=[3, 4, 5, 6], sum=18
  window=[4, 5, 6, 7], sum=22
  window=[5, 6, 7, 8], sum=26
  window=[6, 7, 8, 9], sum=30
  window=[7, 8, 9, 10], sum=34

as_slices: front=[2, 3, 4], back=[5]

make_contiguous: [-1, 0, 10, 20, 30, 40, 50]

round-trip Vec→VecDeque→Vec: [1, 2, 3, 4, 5]
uppercased: ['A', 'B', 'C']

All assertions passed.

LinkedList: Almost Never the Correct Selection

LinkedList<T> is a doubly-linked list. Each element is in its own heap allocation. A forward pointer and a backward pointer connect it to the adjacent elements. The API has the usual operations: push_front, push_back, pop_front, pop_back, front, back, contains, clear, and iteration.

Basic Operations

use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_front(0);
// list is [0, 1, 2, 3]

list.pop_front(); // returns Some(0)
list.pop_back();  // returns Some(3)
// list is [1, 2]

You can also collect an iterator into a list:

let from_iter: LinkedList<&str> = ["hello", "world"].into_iter().collect();

As for VecDeque, Rust 1.95 added push_front_mut and push_back_mut to LinkedList. They insert a node and return &mut T to its element, so you can change the new element in place:

let mut log: LinkedList<String> = LinkedList::new();
let entry = log.push_back_mut(String::from("mid"));    // entry: &mut String
entry.push_str("dle");                                 // "mid" becomes "middle"
let first = log.push_front_mut(String::from("sta"));   // first: &mut String
first.push_str("rt");                                  // "sta" becomes "start"
// log is ["start", "middle"]

The One Operation Where LinkedList Is Best: O(1) Append

The append method moves all the elements of one list to the end of a different list in O(1) time. It only changes the head and tail pointers. It does not copy or reallocate elements:

let mut a: LinkedList<i32> = LinkedList::from([1, 2, 3]);
let mut b: LinkedList<i32> = LinkedList::from([4, 5, 6]);

a.append(&mut b);   // takes all the nodes of b
// a is [1, 2, 3, 4, 5, 6], b is []

For Vec, the equivalent extend operation is O(m), where m is the length of the second collection, because it must copy each element. The same is true for VecDeque. If your program mostly joins and divides large sequences, LinkedList could be the correct selection.

Why LinkedList Is Slower for Almost All Other Work

Modern CPUs use a hierarchy of caches. When you iterate a Vec or a VecDeque, the processor loads the subsequent elements before you use them, because they are contiguous in memory. One cache line (typically 64 bytes) can contain several elements. In a LinkedList, each node is a separate heap allocation that could be at any address. The access to the subsequent node through its pointer is almost always a cache miss.

The practical effect is large. For a sum of 1000 elements in a loop, Vec can be 10 to 50 times faster than LinkedList because of cache effects only. Each node also has an allocation overhead: two pointers and the allocator metadata.

The general rule:

Iteration and Mutation

LinkedList has iter(), iter_mut(), and into_iter(), so the standard iterator methods are available. But access by index is O(n), and there is no Index implementation. You cannot write list[2].

let mut list: LinkedList<i32> = LinkedList::from([1, 2, 3, 4, 5, 6]);
let sum: i32 = list.iter().sum();   // 21

// `&mut list` iterates by mutable reference: val is &mut i32.
for val in &mut list {
    *val *= 10;
}
// list is [10, 20, 30, 40, 50, 60]

04_13_linkedlist.rs prints:

list: [0, 1, 2, 3]
from_iter: ["hello", "world"]

push_*_mut: ["start", "middle"]

after popping both ends: [1, 2]

before append: a=[1, 2, 3], b=[4, 5, 6]
after append:  a=[1, 2, 3, 4, 5, 6], b=[]

sum = 21
after *10: [10, 20, 30, 40, 50, 60]

after clear: len=0

--- Performance comparison (conceptual) ---
• Vec/VecDeque: contiguous memory → CPU cache-friendly
• LinkedList: each node is a separate heap allocation
• For n=1000, iterating Vec can be 10–50x faster due to cache lines
• LinkedList wins only for O(1) append/split of two lists
• If you need a queue: use VecDeque
• If you need a stack: use Vec
• If you need fast insert/remove in the middle: consider Vec::splice

Both produce the same sum: 49995000

All assertions passed.

BinaryHeap: A Max-Heap Priority Queue

BinaryHeap<T> is a binary max-heap in a Vec<T>. It keeps the heap property: the largest element (by T: Ord) is always at the root. Use it for priority queues, top-k queries, and each task that needs the maximum element again and again.

Figure: BinaryHeap as a Max-Heap

Core Operations

use std::collections::BinaryHeap;

let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(5);
heap.push(1);
heap.push(10);
heap.push(3);

assert_eq!(heap.peek(), Some(&10));       // O(1): the maximum, not removed

assert_eq!(heap.pop(), Some(10));          // removes the maximum
assert_eq!(heap.pop(), Some(5));           // then the next largest
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);              // the heap is empty

The Debug output of a BinaryHeap shows the elements in the internal storage order, not in sorted order. Only peek and pop are sure to give you the maximum.

Building a Heap from a Collection

BinaryHeap implements From<Vec<T>>, and you can collect an iterator into it. The construction of a heap from n elements is O(n). n separate push calls are O(n log n):

// One O(n) heap construction from the Vec.
let heap: BinaryHeap<i32> = BinaryHeap::from(vec![8, 3, 6, 1, 9, 4]);
assert_eq!(heap.peek(), Some(&9));   // 9 is the largest value

into_sorted_vec: Heapsort in One Call

into_sorted_vec() consumes the heap and returns a Vec<T> in ascending order. This operation is, in effect, a heapsort:

let heap: BinaryHeap<i32> = BinaryHeap::from(vec![8, 3, 6, 1, 9, 4]);
let sorted = heap.into_sorted_vec();   // `heap` is moved and cannot be used again
assert_eq!(sorted, [1, 3, 4, 6, 8, 9]);

Min-Heap via Reverse

BinaryHeap is always a max-heap. For a min-heap, put each element in a std::cmp::Reverse wrapper:

use std::cmp::Reverse;

let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(10));
min_heap.push(Reverse(3));

// Reverse(1) compares as the largest element, so pop returns it first.
assert_eq!(min_heap.pop(), Some(Reverse(1)));  // the minimum
assert_eq!(min_heap.pop(), Some(Reverse(3)));  // the next smallest

Reverse<T> reverses the Ord implementation, so the "maximum" in the heap is the smallest value. The wrapper has no runtime cost. It compiles to the same code as a comparison that you reverse manually.

Custom Priority: Implementing Ord

For your own types, implement Ord to define "highest priority". The heap compares elements with cmp, so only the fields that your Ord implementation reads have an effect on the order:

#[derive(Debug, Eq, PartialEq)]
struct Task {
    priority: u32,
    name: String,
}

// Compare tasks by `priority` only. `name` has no effect on the order.
impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&other.priority)
    }
}
// PartialOrd must agree with Ord, so it calls `cmp`.
impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

let mut scheduler: BinaryHeap<Task> = BinaryHeap::new();
scheduler.push(Task { priority: 1,  name: "cleanup logs".into() });
scheduler.push(Task { priority: 10, name: "fix security bug".into() });
scheduler.push(Task { priority: 5,  name: "update docs".into() });
scheduler.push(Task { priority: 8,  name: "deploy hotfix".into() });

// `scheduler.pop()` returns the tasks in priority order: 10, 8, 5, 1

Capacity Management and Drain

As Vec does, BinaryHeap has with_capacity, reserve, and shrink_to_fit. The drain() method removes all the elements and returns an iterator. The iteration order is not sorted. The iterator gives the elements in the internal storage order:

let mut h = BinaryHeap::from([3, 1, 4, 1, 5]);
let drained: Vec<i32> = h.drain().collect();
// drained has all 5 elements, but in arbitrary order
assert!(h.is_empty());   // drain removed each element

If you need the elements in sorted order, use a while let Some(val) = heap.pop() loop.

Relaxed T: Ord Bounds in Rust 1.94

Before Rust 1.94, many BinaryHeap methods required T: Ord, although they do not compare elements. Examples are len(), is_empty(), capacity(), clear(), drain(), and into_vec(). Since Rust 1.94, these methods have relaxed bounds. They accept each T, with or without an Ord implementation. Thus you can use a BinaryHeap in more generic code, without trait bounds that are not necessary.

04_14_binaryheap.rs prints:

heap (Debug shows internal order, not sorted): [10, 3, 5, 1]
peek (max) = Some(10)

popped in descending order: 10, 5, 3, 1

from vec: peek = Some(9)
into_sorted_vec: [1, 3, 4, 6, 8, 9]

min-heap pops: 1, 3, ...

task processing order:
  [priority=10] fix security bug
  [priority=8] deploy hotfix
  [priority=5] update docs
  [priority=1] cleanup logs

after shrink_to_fit: len=10, cap=10

drained (arbitrary order): [5, 3, 4, 1, 1]

collected heap, max = Some(99)

All assertions passed.

Summary

Code Examples