Prepending to a Vec in Rust: What Are Your Options?

Rust’s Vec is a powerful and flexible collection type. It’s fast at pushing and popping at the end, but sometimes you need to add an element to the front. That’s where things get tricky: Vec is backed by a contiguous array, so prepending requires shifting or reallocating elements. There’s no O(1) way to do this.

In this post, we’ll walk through several ways to prepend to a Vec, compare their mechanics, and discuss when each is appropriate. 

---

The Problem

You have a vector:

let mut digits = vec![2, 3, 4];

You want to add 1 to the head, so that the result is [1, 2, 3, 4].

---

Option 1: Using insert(0, value)

The simplest and most idiomatic solution:

digits.insert(0, 1);

• Shifts all elements one place to the right.

• Uses ptr::copy under the hood (a single memmove).

• Complexity: O(n).

This is usually the best choice unless you need to squeeze out every last cycle.

---

Option 2: Build a New Vec With Capacity

If you’re fine creating a new vector:

let mut result = Vec::with_capacity(digits.len() + 1);
result.push(1);
result.extend(digits);

• Allocates a new buffer sized exactly for the result.

• Copies all elements once into the new buffer.

• Useful when you’re already constructing a fresh vector.

---

Option 3: Manual Shifting With copy_within

You can explicitly shift elements forward:

digits.push(0); // grow by one
let len = digits.len();
digits.copy_within(0..len-1, 1);
digits[0] = 1;

• Performs the same work as insert, but with more control.

• Complexity: O(n).

• Sometimes avoids an extra bounds check.

---

Option 4: Unsafe Pointer Manipulation

For maximum control, you can use raw pointers:

digits.reserve(1);
let len = digits.len();
unsafe {
    std::ptr::copy(
        digits.as_ptr(),
        digits.as_mut_ptr().add(1),
        len,
    );
    std::ptr::write(digits.as_mut_ptr(), 1);
    digits.set_len(len + 1);
}

• Essentially reimplements what insert does internally.

• No additional allocations if capacity is sufficient.

• Only worth it for performance-critical hot paths.

---

Option 5: Reverse, Push, Reverse

A creative trick:

digits.reverse();
digits.push(1);
digits.reverse();

• Two reversals = O(n).

• Works, but less idiomatic.

• Sometimes useful if you’re building vectors backwards.

---

Summary

• Use insert(0, value) if you just need to prepend occasionally. It’s clean and efficient enough.

• Use with_capacity + push + extend if you’re already making a new vector.

• Use manual shifting or unsafe pointer manipulation only if you’re in a hot loop and need the absolute fastest approach.

• Reverse, push, reverse is a neat trick, but rarely preferable.

At the end of the day, all these options are O(n). The right choice depends less on theoretical speed and more on code clarity and allocation patterns.