VecDeque, LinkedList and their cost

A Vec is fast at the end and slow at the front, because an insert at index zero moves everything. Two other sequence types cover the cases it does not: VecDeque is a ring buffer that pushes and pops at both ends, and LinkedList is a doubly linked list that splices without moving elements.

The deque is the one used in practice, as a queue or a sliding window. The list is rarely the right choice, and the lesson shows why: one allocation per node and a pointer chase on every step. The last section reads the error for asking a vector for a method that belongs to the deque.

VecDeque

push_back and push_front add at either end, and pop_front and pop_back remove and return an Option. All four are constant time, which is the point of the ring buffer.

The program builds a small deque, pops from both ends and prints what is left. The first value comes out of the front and the second out of the back.

use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); queue.push_back("first"); queue.push_back("second"); queue.push_front("zero"); println!("{:?}", queue.pop_front()); println!("{:?}", queue.pop_back()); println!("{:?}", queue); }

rustc --edition 2024 deque.rs
./deque

Some("zero")
Some("second")
["first"]

The debug form prints the deque in order, which is the reading order of the queue. The lesson on Vec explains when the extra machinery is unnecessary.

Rotating

rotate_left and rotate_right move the elements without reallocating, which is the operation a ring buffer is built for. The count is taken modulo the length, so a rotation larger than the length is allowed.

The program fills a deque with one to five, rotates left twice and right once. The two outputs show the window moving and coming back by one.

use std::collections::VecDeque; fn main() { let mut values: VecDeque<i32> = (1..=5).collect(); values.rotate_left(2); println!("{values:?}"); values.rotate_right(1); println!("{values:?}"); }

rustc --edition 2024 rotate.rs
./rotate

[3, 4, 5, 1, 2]
[2, 3, 4, 5, 1]

The same method exists on a slice, where it rotates in place without a deque. The type matters for the push and pop ends, not for the rotation itself.

LinkedList

A LinkedList stores each element in its own allocation with a pointer to the next and the previous one. Push and pop at a known node are constant time, but reaching a position is linear and the cache misses are worse than a vector's.

The program pushes at both ends and prints the length, the front and the contents. The output is the three values in order.

use std::collections::LinkedList; fn main() { let mut list = LinkedList::new(); list.push_back(2); list.push_front(1); list.push_back(3); println!("{} {}", list.len(), list.front().unwrap()); println!("{:?}", list.iter().copied().collect::<Vec<i32>>()); }

rustc --edition 2024 list.rs
./list

3 1
[1, 2, 3]

The list also stores two pointers per element, which is the memory the vector does not spend, and every node is a separate allocation that the allocator has to find. In safe Rust the list cannot offer the splicing that makes a linked list interesting, so the standard one is mostly a teaching type. The next sections use the deque for the queue.

A queue in use

A queue takes from the front and adds at the back, which is exactly pop_front and push_back. while let drains it until the pop returns None.

The program queues three tasks and prints them in the order they were added. The loop is the shape of a work queue, and the lesson on thread pools uses the same drain from another thread.

use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); for task in ["build", "test", "ship"] { queue.push_back(task); } while let Some(task) = queue.pop_front() { println!("doing {task}"); } }

rustc --edition 2024 queue_use.rs
./queue_use

doing build
doing test
doing ship

Removing from the front of a vector with remove(0) would shift every task, which is why a queue is not built on a vector. The lesson on vectors shows what that shift costs.

A method a Vec does not have

push_front belongs to the deque, not to the vector. Calling it on a Vec is E0599, and the help suggests a method with a similar name that has nothing to do with the problem.

The program tries to push at the front of a vector. The fix is a VecDeque, or an insert(0, value) when the cost is acceptable.

fn main() { let mut values = vec![1, 2, 3]; values.push_front(0); println!("{values:?}"); }

rustc --edition 2024 push_front_err.rs

error[E0599]: no method named `push_front` found for struct `Vec<{integer}>` in the current scope
--> push_front_err.rs:3:12
|
3 | values.push_front(0);
| ^^^^^^^^^^
|
help: there is a method `push_mut` with a similar name
|
3 - values.push_front(0);
3 + values.push_mut(0);
|

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0599`.

The compiler compares methods by name, not by intent, which is why the suggestion is unhelpful here. The lesson on heaps continues with the other adaptor-like containers.

Exercises

  1. Build a deque of five numbers, pop two from each end and print what remains.
  2. Rotate a deque of five values left by seven and explain the result.
  3. Replace the queue program's deque with a vector and read the cost warning in the lesson.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is a VecDeque good at?

    Answer

    Pushing and popping at both ends in constant time

    The ring buffer makes both ends cheap, which a vector cannot do at the front.

  2. What does pop_front return on an empty deque?

    Answer

    None

    The pop methods return an Option, so the empty case is a value.

  3. What does rotate_left(2) do to the deque [1, 2, 3, 4, 5]?

    Answer

    It moves to [3, 4, 5, 1, 2]

    The first two values go to the back, and the rest move forward.

  4. What is the cost of a LinkedList compared with a Vec?

    Answer

    One allocation per node and poor cache locality

    Each node is separate, so a walk follows pointers instead of a contiguous buffer.

  5. What does this program print? use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); queue.push_back("first"); queue.push_back("second"); queue.push_front("zero"); println!("{:?}", queue.pop_front()); println!("{:?}", queue.pop_back()); println!("{:?}", queue); }

    Answer

    Some("zero") / Some("second") / ["first"]

    The front is zero, the back is second, and first remains in the middle.

  6. What does this program print? use std::collections::VecDeque; fn main() { let mut values: VecDeque<i32> = (1..=5).collect(); values.rotate_left(2); println!("{values:?}"); values.rotate_right(1); println!("{values:?}"); }

    Answer

    [3, 4, 5, 1, 2] / [2, 3, 4, 5, 1]

    A left rotation by two moves the first two to the back, and a right rotation by one moves the last to the front.

  7. What does this program print? use std::collections::LinkedList; fn main() { let mut list = LinkedList::new(); list.push_back(2); list.push_front(1); list.push_back(3); println!("{} {}", list.len(), list.front().unwrap()); }

    Answer

    3 1

    The list holds three values, and the front is the one pushed first.

  8. What does this program print? use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); for task in ["build", "test"] { queue.push_back(task); } while let Some(task) = queue.pop_front() { println!("doing {task}"); } }

    Answer

    doing build / doing test

    The queue is drained in insertion order, and the loop stops when the pop returns None.

  9. What is the first line of the compiler output for this program? fn main() { let mut values = vec![1, 2, 3]; values.push_front(0); println!("{values:?}"); }

    Answer

    error[E0599]: no method named push_front found for struct Vec<{integer}> in the current scope

    The method belongs to VecDeque, and a Vec has no front to push onto.

  10. What does this program print? use std::collections::VecDeque; fn main() { let mut values: VecDeque<i32> = VecDeque::new(); values.push_back(1); values.push_front(0); println!("{} {:?}", values.len(), values.front()); }

    Answer

    2 Some(0)

    Both values are stored, and the front is the zero pushed last.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image