List

List #

Ketika developer dari bahasa lain mencari “list” di Rust, jawabannya hampir selalu Vec<T>. Bukan LinkedList — meski namanya terdengar seperti apa yang dicari. Rust adalah bahasa yang sangat peduli dengan locality of reference: data yang tersimpan bersebelahan di memori diakses jauh lebih cepat daripada data yang terhubung via pointer, bahkan untuk operasi penyisipan di tengah. Artikel ini membahas Vec<T> secara mendalam — cara kerjanya di memori, operasi-operasi yang tersedia, dan teknik yang membuat kode Vec idiomatis. Kemudian membahas VecDeque untuk kasus antrian dua arah, dan terakhir LinkedList beserta penjelasan jujur kapan (dan kapan tidak) menggunakannya.

Vec<T> — Pilihan Utama untuk List #

Vec<T> adalah array dinamis yang dialokasikan di heap. Tiga angka mendefinisikan state-nya di memori: pointer ke data, panjang (jumlah elemen aktual), dan kapasitas (jumlah elemen yang bisa ditampung sebelum realokasi):

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

Saat push dilakukan dan len == cap, Vec mengalokasikan blok baru (biasanya dua kali lipat kapasitas sebelumnya), menyalin semua elemen, dan membebaskan memori lama. Proses ini mahal, tapi jarang terjadi — amortized cost per push tetap O(1).

Membuat Vec #

fn main() {
    // Kosong — tipe harus eksplisit karena belum ada elemen
    let mut v1: Vec<i32> = Vec::new();

    // Macro vec! — cara paling umum
    let v2 = vec![10, 20, 30, 40, 50];

    // Diisi nilai yang sama
    let v3 = vec![0u8; 1024];  // 1024 byte, semua nol

    // Dari iterator — paling fleksibel
    let v4: Vec<i32> = (1..=10).collect();
    let v5: Vec<i32> = (1..=10).filter(|n| n % 2 == 0).collect();

    // Dengan kapasitas awal — hindari realokasi jika jumlah elemen diketahui
    let mut v6: Vec<String> = Vec::with_capacity(100);

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

Menambah dan Menghapus Elemen #

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

    // Tambah di akhir — O(1) amortized
    v.push(4);
    v.push(5);
    println!("{:?}", v);  // [1, 2, 3, 4, 5]

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

    // Sisipkan di posisi tertentu — O(n) karena perlu geser elemen
    v.insert(1, 99);
    println!("{:?}", v);  // [1, 99, 2, 3, 4]

    // Hapus di posisi tertentu — O(n) karena perlu geser elemen
    let dihapus = v.remove(1);
    println!("Remove: {}", dihapus);  // 99
    println!("{:?}", v);              // [1, 2, 3, 4]

    // swap_remove — O(1) alternatif remove, tapi tidak jaga urutan
    let mut v2 = vec!["a", "b", "c", "d", "e"];
    v2.swap_remove(1);  // hapus "b", ganti dengan "e"
    println!("{:?}", v2);  // ["a", "e", "c", "d"]

    // Hapus semua elemen — tidak bebaskan kapasitas
    v.clear();
    println!("Setelah clear: {:?} (len={}, cap={})", v, v.len(), v.capacity());

    // Gabungkan dua Vec
    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]

    // Atau dengan append — memindahkan semua elemen dari b ke a, b jadi kosong
    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) menggeser semua elemen setelah i satu posisi ke kiri — O(n). Jika urutan tidak penting, gunakan swap_remove(i) yang O(1): ia menukar elemen yang dihapus dengan elemen terakhir lalu memperpendek Vec.

Mengakses Elemen #

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

    // Akses via indeks — panic jika out of bounds
    println!("Pertama: {}", v[0]);
    println!("Terakhir: {}", v[v.len() - 1]);

    // ANTI-PATTERN: akses tanpa validasi di kode produksi
    // let x = v[99];  // panic: index out of bounds

    // BENAR: gunakan .get() yang mengembalikan Option
    match v.get(2) {
        Some(&val) => println!("Indeks 2: {}", val),
        None => println!("Indeks 2 tidak ada"),
    }

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

    // first() dan last()
    println!("Pertama: {:?}", v.first());   // Some(10)
    println!("Terakhir: {:?}", v.last());   // Some(50)

    // contains() — cek keberadaan elemen
    println!("Ada 30: {}", v.contains(&30));   // true
    println!("Ada 99: {}", v.contains(&99));   // false

    // position() — cari indeks elemen pertama
    println!("Posisi 30: {:?}", v.iter().position(|&x| x == 30));  // Some(2)

    // binary_search() — O(log n) tapi butuh Vec sudah terurut
    let terurut = vec![1, 3, 5, 7, 9, 11];
    println!("{:?}", terurut.binary_search(&7));  // Ok(3)
    println!("{:?}", terurut.binary_search(&6));  // Err(3) — posisi jika diinsert
}

Pengurutan dan Dedup #

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

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

    // Hapus duplikat berurutan — hanya bekerja setelah sort
    v.dedup();
    println!("Dedup: {:?}", v);  // [1, 2, 3, 4, 5, 6, 9]

    // sort_by — urutan kustom
    let mut kata = vec!["pisang", "apel", "mangga", "jeruk"];
    kata.sort_by(|a, b| a.len().cmp(&b.len()));
    println!("Urut panjang: {:?}", kata);

    // sort_by_key — lebih ringkas
    kata.sort_by_key(|s| s.len());
    println!("Urut panjang: {:?}", kata);

    // sort_unstable — lebih cepat dari sort, tidak jaga urutan elemen sama
    let mut angka = vec![5, 2, 8, 1, 9, 3];
    angka.sort_unstable();
    println!("Unstable sort: {:?}", angka);

    // Balik urutan
    angka.reverse();
    println!("Reversed: {:?}", angka);
}

Slice — Pandangan ke Sebagian Vec #

Slice (&[T] atau &mut [T]) adalah pandangan ke bagian dari Vec tanpa menyalin data. Hampir semua fungsi yang menerima data sekuensial sebaiknya menerima slice, bukan &Vec<T>, karena lebih fleksibel:

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

// BENAR: &[T] lebih generik — menerima Vec, array, dan slice
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));         // dari Vec
    println!("{}", jumlahkan(&arr));       // dari array
    println!("{}", jumlahkan(&v[1..4]));   // slice [2, 3, 4]

    // windows() — iterasi jendela bergeser ukuran 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() — pecah menjadi potongan ukuran n
    for chunk in angka.chunks(2) {
        println!("{:?}", chunk);  // [1,2], [3,4], [5]
    }

    // split_at() — bagi menjadi dua slice
    let (kiri, kanan) = angka.split_at(2);
    println!("Kiri: {:?}, Kanan: {:?}", kiri, kanan);  // [1,2], [3,4,5]
}

Retain — Filter In-Place #

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

    // Pertahankan hanya elemen yang memenuhi kondisi
    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"),
    ];

    // Hapus string kosong
    nama.retain(|s| !s.is_empty());
    println!("{:?}", nama);  // ["Budi", "Sari", "Joko"]
}

Kapasitas dan Manajemen Memori #

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

    // Pantau kapasitas saat elemen ditambahkan
    for i in 0..20 {
        v.push(i);
        // kapasitas bertambah dua kali lipat saat habis: 0 → 1 → 2 → 4 → 8 → 16 → 32
    }
    println!("Len: {}, Cap: {}", v.len(), v.capacity());

    // with_capacity — alokasi di awal jika jumlah elemen diketahui
    let mut v2: Vec<i32> = Vec::with_capacity(100);
    for i in 0..100 {
        v2.push(i);  // tidak ada realokasi
    }
    println!("Len: {}, Cap: {}", v2.len(), v2.capacity());  // 100, 100

    // shrink_to_fit — bebaskan kapasitas berlebih
    v2.truncate(10);  // potong ke 10 elemen
    println!("Setelah truncate — Len: {}, Cap: {}", v2.len(), v2.capacity());
    v2.shrink_to_fit();
    println!("Setelah shrink — Len: {}, Cap: {}", v2.len(), v2.capacity());
}

VecDeque<T> — Antrian Dua Arah #

VecDeque<T> (double-ended queue) adalah koleksi yang dioptimalkan untuk penambahan dan penghapusan di kedua ujung secara efisien — keduanya O(1). Ini pilihan yang tepat untuk mengimplementasikan antrian (queue) atau deque:

use std::collections::VecDeque;

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

    // Tambah di belakang — push_back = push pada Vec
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);

    // Tambah di depan — O(1), lebih efisien dari Vec::insert(0, ...)
    deque.push_front(0);
    deque.push_front(-1);

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

    // Hapus dari depan — O(1), ini yang membuat VecDeque cocok untuk queue
    let depan = deque.pop_front();
    println!("Pop front: {:?}", depan);  // Some(-1)

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

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

    // Simulasi queue FIFO
    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!("Proses: {}", tugas);
    }

    // Konversi dari 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> — Dan Mengapa Jarang Digunakan #

LinkedList<T> adalah doubly-linked list di standard library. Secara teoritis, ia punya O(1) untuk insert/delete di posisi yang sudah diketahui. Tapi dalam praktik di Rust — dan bahasa modern umumnya — LinkedList hampir selalu lebih lambat dari Vec, bahkan untuk kasus yang secara teoritis menguntungkan linked list:

use std::collections::LinkedList;

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

    // Tambah di belakang
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    // Tambah di depan
    list.push_front(0);

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

    // Hapus dari depan dan belakang
    list.pop_front();
    list.pop_back();
    println!("{:?}", list);  // [1, 2]

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

    // Gabungkan dua LinkedList
    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 setelah append: {:?}", b);  // [] — b dikosongkan
}

Mengapa Vec Biasanya Lebih Cepat dari LinkedList #

Alasannya adalah cache locality. Semua elemen Vec berada dalam blok memori yang bersebelahan, sehingga cache CPU bisa memuat banyak elemen sekaligus. LinkedList mengalokasikan setiap node secara terpisah di heap — mengakses elemen berikutnya berarti mem-fetch dari alamat memori yang tidak bersebelahan, menyebabkan banyak cache miss.

Vec:         [1][2][3][4][5]  ← satu blok memori bersebelahan
LinkedList:  [1]→heap₁ [2]→heap₂ [3]→heap₃  ← pointer tersebar di memori

Benchmark nyata menunjukkan Vec lebih cepat untuk: iterasi, push, dan bahkan insert di tengah (untuk n yang wajar), karena overhead alokasi per-node dan cache miss dari LinkedList jauh melebihi O(n) geser elemen Vec.

Perbandingan Pilihan Koleksi List #

KoleksiAkses acakPush/pop belakangPush/pop depanInsert tengahKapan digunakan
Vec<T>O(1)O(1) amortizedO(n)O(n)Default — hampir semua kasus
VecDeque<T>O(1)O(1)O(1)O(n)Queue, buffer sliding window
LinkedList<T>O(n)O(1)O(1)O(1)*Hampir tidak pernah

*O(1) insert di tengah LinkedList hanya jika sudah punya iterator ke posisinya — mendapat iterator-nya sendiri butuh O(n).

Gunakan Vec jika:
  ✓ Default untuk semua kebutuhan list
  ✓ Perlu akses acak dengan indeks
  ✓ Ukuran koleksi tidak diketahui saat kompilasi
  ✓ Perlu sort, dedup, atau operasi slice

Gunakan VecDeque jika:
  ✓ Perlu push/pop efisien di kedua ujung
  ✓ Implementasi queue (FIFO) atau deque
  ✓ Sliding window buffer dengan ukuran tetap

Gunakan LinkedList jika:
  ✗ Hampir tidak ada kasus nyata yang membutuhkannya di Rust
  ✓ Satu-satunya kasus: perlu split/merge list dalam O(1) menggunakan cursor API

Ringkasan #

  • Vec<T> adalah pilihan default untuk semua kebutuhan list — lebih cepat dari LinkedList dalam hampir semua kasus nyata karena cache locality.
  • Alokasi kapasitas awal dengan Vec::with_capacity(n) jika jumlah elemen diperkirakan — menghindari realokasi berulang yang mahal.
  • Gunakan .get(i) bukan v[i] untuk akses yang aman — .get() mengembalikan Option, v[i] panic jika out of bounds.
  • swap_remove lebih cepat dari remove jika urutan tidak penting — remove O(n) karena menggeser elemen; swap_remove O(1) karena menukar dengan elemen terakhir.
  • Parameter fungsi sebaiknya &[T] bukan &Vec<T> — slice lebih generik, menerima Vec, array, dan slice sekaligus tanpa konversi.
  • windows(n) untuk analisis urutan tetangga, chunks(n) untuk memproses dalam batch — keduanya menghasilkan slice tanpa alokasi.
  • retain untuk filter in-place — lebih efisien dari filter + collect karena tidak mengalokasikan Vec baru.
  • VecDeque<T> untuk queue FIFO — push_back + pop_front keduanya O(1), berbeda dari Vec yang insert(0, x) adalah O(n).
  • LinkedList hampir tidak pernah tepat di Rust — cache miss dari alokasi per-node biasanya jauh lebih mahal dari O(n) geser elemen Vec.

← Sebelumnya: Eksepsi   Berikutnya: Map →

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