List #

When developers from other languages look for “list” in Rust, the answer is almost always Vec<T>. Not LinkedList — despite the name sounding like what they’re looking for. Rust is a language deeply concerned with locality of reference: data stored contiguously in memory is accessed far faster than data connected via pointers, even for insertions in the middle. This article covers Vec<T> in depth — how it works in memory, the operations available, and the techniques that make Vec code idiomatic. Then it covers VecDeque for two-way queue cases, and finally LinkedList along with an honest explanation of when (and when not) to use it.

Vec<T> — The Primary Choice for Lists #

Vec<T> is a dynamic array allocated on the heap. Three numbers define its state in memory: a pointer to the data, the length (actual number of elements), and the capacity (how many elements it can hold before reallocation):

flowchart LR
    subgraph Stack
        V["Vec\nptr → ...\nlen: 3\ncap: 4"]
    end
    subgraph Heap
        D["[10 | 20 | 30 | _ ]"]
    end
    V -- ptr --> D

When a push happens and len == cap, the Vec allocates a new block (usually twice the previous capacity), copies all elements, and frees the old memory. This process is expensive, but it happens rarely — the amortized cost per push stays O(1).

Creating a Vec #

fn main() {
    // Empty — the type must be explicit because there are no elements yet
    let mut v1: Vec<i32> = Vec::new();

    // The vec! macro — the most common way
    let v2 = vec![10, 20, 30, 40, 50];

    // Filled with the same value
    let v3 = vec![0u8; 1024];  // 1024 bytes, all zero

    // From an iterator — the most flexible
    let v4: Vec<i32> = (1..=10).collect();
    let v5: Vec<i32> = (1..=10).filter(|n| n % 2 == 0).collect();

    // With initial capacity — avoid reallocation if the element count is known
    let mut v6: Vec<String> = Vec::with_capacity(100);

    println!("{:?}", v2);
    println!("{:?}", v4);
    println!("{:?}", v5);
    println!("Capacity of v6: {}", v6.capacity()); // 100
}

Adding and Removing Elements #

fn main() {
    let mut v = vec![1, 2, 3];

    // Add at the end — O(1) amortized
    v.push(4);
    v.push(5);
    println!("{:?}", v);  // [1, 2, 3, 4, 5]

    // Remove from the end — O(1)
    let terakhir = v.pop();
    println!("Pop: {:?}", terakhir);  // Some(5)
    println!("{:?}", v);              // [1, 2, 3, 4]

    // Insert at a specific position — O(n) because elements must be shifted
    v.insert(1, 99);
    println!("{:?}", v);  // [1, 99, 2, 3, 4]

    // Remove at a specific position — O(n) because elements must be shifted
    let dihapus = v.remove(1);
    println!("Remove: {}", dihapus);  // 99
    println!("{:?}", v);              // [1, 2, 3, 4]

    // swap_remove — O(1) alternative to remove, but doesn't preserve order
    let mut v2 = vec!["a", "b", "c", "d", "e"];
    v2.swap_remove(1);  // removes "b", replaced by "e"
    println!("{:?}", v2);  // ["a", "e", "c", "d"]

    // Remove all elements — doesn't free the capacity
    v.clear();
    println!("After clear: {:?} (len={}, cap={})", v, v.len(), v.capacity());

    // Combine two Vecs
    let mut a = vec![1, 2, 3];
    let b = vec![4, 5, 6];
    a.extend(b.iter());
    println!("{:?}", a);  // [1, 2, 3, 4, 5, 6]

    // Or with append — moves all elements from b to a, b becomes empty
    let mut c = vec![1, 2, 3];
    let mut d = vec![4, 5, 6];
    c.append(&mut d);
    println!("c: {:?}, d: {:?}", c, d);  // c: [1..6], d: []
}
remove(i) shifts all elements after i one position to the left — O(n). If order doesn’t matter, use swap_remove(i) which is O(1): it swaps the removed element with the last one, then shortens the Vec.

Accessing Elements #

fn main() {
    let v = vec![10, 20, 30, 40, 50];

    // Access via index — panics if out of bounds
    println!("First: {}", v[0]);
    println!("Last: {}", v[v.len() - 1]);

    // ANTI-PATTERN: unchecked access in production code
    // let x = v[99];  // panic: index out of bounds

    // CORRECT: use .get() which returns an Option
    match v.get(2) {
        Some(&val) => println!("Index 2: {}", val),
        None => println!("Index 2 doesn't exist"),
    }

    println!("{:?}", v.get(10));  // None — no panic

    // first() and last()
    println!("First: {:?}", v.first());   // Some(10)
    println!("Last: {:?}", v.last());   // Some(50)

    // contains() — check element existence
    println!("Has 30: {}", v.contains(&30));   // true
    println!("Has 99: {}", v.contains(&99));   // false

    // position() — find the index of the first element
    println!("Position of 30: {:?}", v.iter().position(|&x| x == 30));  // Some(2)

    // binary_search() — O(log n) but requires a sorted Vec
    let terurut = vec![1, 3, 5, 7, 9, 11];
    println!("{:?}", terurut.binary_search(&7));  // Ok(3)
    println!("{:?}", terurut.binary_search(&6));  // Err(3) — insertion position
}

Sorting and Dedup #

fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

    // Sort — O(n log n)
    v.sort();
    println!("Sorted: {:?}", v);

    // Remove consecutive duplicates — only works after sorting
    v.dedup();
    println!("Dedup: {:?}", v);  // [1, 2, 3, 4, 5, 6, 9]

    // sort_by — custom ordering
    let mut kata = vec!["pisang", "apel", "mangga", "jeruk"];
    kata.sort_by(|a, b| a.len().cmp(&b.len()));
    println!("Sorted by length: {:?}", kata);

    // sort_by_key — more concise
    kata.sort_by_key(|s| s.len());
    println!("Sorted by length: {:?}", kata);

    // sort_unstable — faster than sort, doesn't preserve the order of equal elements
    let mut angka = vec![5, 2, 8, 1, 9, 3];
    angka.sort_unstable();
    println!("Unstable sort: {:?}", angka);

    // Reverse the order
    angka.reverse();
    println!("Reversed: {:?}", angka);
}

Slices — Views into Part of a Vec #

A slice (&[T] or &mut [T]) is a view into part of a Vec without copying data. Almost every function that accepts sequential data should accept a slice, not &Vec<T>, because it’s more flexible:

// ANTI-PATTERN: &Vec<T> parameter is too specific
fn jumlahkan_vec(v: &Vec<i32>) -> i32 {
    v.iter().sum()
}

// CORRECT: &[T] is more generic — accepts Vecs, arrays, and slices
fn jumlahkan(data: &[i32]) -> i32 {
    data.iter().sum()
}

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let arr = [10, 20, 30];

    println!("{}", jumlahkan(&v));         // from a Vec
    println!("{}", jumlahkan(&arr));       // from an array
    println!("{}", jumlahkan(&v[1..4]));   // slice [2, 3, 4]

    // windows() — iterate sliding windows of size n
    let angka = vec![1, 2, 3, 4, 5];
    for window in angka.windows(3) {
        println!("{:?}", window);  // [1,2,3], [2,3,4], [3,4,5]
    }

    // chunks() — split into chunks of size n
    for chunk in angka.chunks(2) {
        println!("{:?}", chunk);  // [1,2], [3,4], [5]
    }

    // split_at() — split into two slices
    let (kiri, kanan) = angka.split_at(2);
    println!("Left: {:?}, Right: {:?}", kiri, kanan);  // [1,2], [3,4,5]
}

Retain — In-Place Filtering #

fn main() {
    let mut v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    // Keep only the elements satisfying the condition
    v.retain(|&x| x % 2 == 0);
    println!("{:?}", v);  // [2, 4, 6, 8, 10]

    let mut nama = vec![
        String::from("Budi"),
        String::from(""),
        String::from("Sari"),
        String::from(""),
        String::from("Joko"),
    ];

    // Remove empty strings
    nama.retain(|s| !s.is_empty());
    println!("{:?}", nama);  // ["Budi", "Sari", "Joko"]
}

Capacity and Memory Management #

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

    // Watch the capacity grow as elements are added
    for i in 0..20 {
        v.push(i);
        // capacity doubles when exhausted: 0 → 1 → 2 → 4 → 8 → 16 → 32
    }
    println!("Len: {}, Cap: {}", v.len(), v.capacity());

    // with_capacity — allocate upfront if the element count is known
    let mut v2: Vec<i32> = Vec::with_capacity(100);
    for i in 0..100 {
        v2.push(i);  // no reallocation
    }
    println!("Len: {}, Cap: {}", v2.len(), v2.capacity());  // 100, 100

    // shrink_to_fit — free excess capacity
    v2.truncate(10);  // cut down to 10 elements
    println!("After truncate — Len: {}, Cap: {}", v2.len(), v2.capacity());
    v2.shrink_to_fit();
    println!("After shrink — Len: {}, Cap: {}", v2.len(), v2.capacity());
}

VecDeque<T> — Double-Ended Queue #

VecDeque<T> (double-ended queue) is a collection optimized for adding and removing at both ends efficiently — both are O(1). It’s the right choice for implementing a queue or deque:

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();

    // Add at the back — push_back = push on a Vec
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);

    // Add at the front — O(1), more efficient than Vec::insert(0, ...)
    deque.push_front(0);
    deque.push_front(-1);

    println!("{:?}", deque);  // [-1, 0, 1, 2, 3]

    // Remove from the front — O(1), this is what makes VecDeque suitable for queues
    let depan = deque.pop_front();
    println!("Pop front: {:?}", depan);  // Some(-1)

    // Remove from the back — O(1)
    let belakang = deque.pop_back();
    println!("Pop back: {:?}", belakang);  // Some(3)

    println!("{:?}", deque);  // [0, 1, 2]

    // Simulate a FIFO queue
    let mut antrian: VecDeque<String> = VecDeque::new();
    antrian.push_back(String::from("tugas-1"));
    antrian.push_back(String::from("tugas-2"));
    antrian.push_back(String::from("tugas-3"));

    while let Some(tugas) = antrian.pop_front() {
        println!("Process: {}", tugas);
    }

    // Conversion from a Vec
    let v = vec![1, 2, 3, 4, 5];
    let mut deque2: VecDeque<i32> = v.into();
    deque2.push_front(0);
    println!("{:?}", deque2);  // [0, 1, 2, 3, 4, 5]
}

LinkedList<T> — And Why It’s Rarely Used #

LinkedList<T> is the doubly-linked list in the standard library. Theoretically, it has O(1) insert/delete at positions that are already known. But in practice in Rust — and in modern languages generally — LinkedList is almost always slower than Vec, even for cases that theoretically favor linked lists:

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();

    // Add at the back
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    // Add at the front
    list.push_front(0);

    println!("{:?}", list);  // [0, 1, 2, 3]

    // Remove from the front and back
    list.pop_front();
    list.pop_back();
    println!("{:?}", list);  // [1, 2]

    // Iteration
    for val in &list {
        print!("{} ", val);
    }
    println!();

    // Combine two LinkedLists
    let mut a: LinkedList<i32> = (1..=3).collect();
    let mut b: LinkedList<i32> = (4..=6).collect();
    a.append(&mut b);
    println!("{:?}", a);  // [1, 2, 3, 4, 5, 6]
    println!("b after append: {:?}", b);  // [] — b is emptied
}

Why Vec Is Usually Faster than LinkedList #

The reason is cache locality. All elements of a Vec sit in a contiguous memory block, so the CPU cache can load many elements at once. A LinkedList allocates each node separately on the heap — accessing the next element means fetching from a non-contiguous memory address, causing many cache misses.

Vec:         [1][2][3][4][5]  ← one contiguous memory block
LinkedList:  [1]→heap₁ [2]→heap₂ [3]→heap₃  ← pointers scattered in memory

Real-world benchmarks show Vec is faster for: iteration, push, and even middle insertion (for reasonable n), because the per-node allocation overhead and cache misses of LinkedList far exceed the O(n) element shifting of Vec.

Comparing List Collection Choices #

CollectionRandom accessPush/pop backPush/pop frontMiddle insertWhen to use
Vec<T>O(1)O(1) amortizedO(n)O(n)Default — almost every case
VecDeque<T>O(1)O(1)O(1)O(n)Queues, sliding window buffers
LinkedList<T>O(n)O(1)O(1)O(1)*Almost never

*O(1) middle insert in a LinkedList only applies if you already have an iterator to the position — getting that iterator itself costs O(n).

Use Vec if:
  ✓ Default for all list needs
  ✓ Need random access by index
  ✓ Collection size unknown at compile time
  ✓ Need sort, dedup, or slice operations

Use VecDeque if:
  ✓ Need efficient push/pop at both ends
  ✓ Implementing a queue (FIFO) or deque
  ✓ Sliding window buffer with a fixed size

Use LinkedList if:
  ✗ Almost no real-world case needs it in Rust
  ✓ Only case: need O(1) list split/merge using the cursor API

Summary #

  • Vec<T> is the default choice for all list needs — faster than LinkedList in almost every real case thanks to cache locality.
  • Allocate initial capacity with Vec::with_capacity(n) if the element count is estimated — avoids expensive repeated reallocations.
  • Use .get(i) instead of v[i] for safe access — .get() returns an Option, v[i] panics if out of bounds.
  • swap_remove is faster than remove if order doesn’t matter — remove is O(n) because it shifts elements; swap_remove is O(1) because it swaps with the last element.
  • Function parameters should be &[T], not &Vec<T> — slices are more generic, accepting Vecs, arrays, and slices at once without conversion.
  • windows(n) for neighbor-sequence analysis, chunks(n) for batch processing — both produce slices without allocation.
  • retain for in-place filtering — more efficient than filter + collect because it doesn’t allocate a new Vec.
  • VecDeque<T> for FIFO queues — push_back + pop_front are both O(1), unlike Vec where insert(0, x) is O(n).
  • LinkedList is almost never the right choice in Rust — the cache misses from per-node allocation usually cost far more than the O(n) element shifting of a Vec.

← Previous: Error Handling   Next: Map →

About | Author | Content Scope | Editorial Policy | Privacy Policy | Disclaimer | Contact