Sequence Collections di Rust

Latihan membuat instruksi pembelajaran menggunakan library standard di Rust terkait collections, lebih detail lagi mengenai dua contoh sequence: Vec dan LinkedList.

Sequence Collections di Rust.

Rust menyediakan koleksi bawaan yang berguna untuk menyimpan data berurutan. Sebelum kita masuk ke latihan membuat ADT List atau LinkedList sendiri, ada baiknya memahami dulu pilihan-pilihan yang sudah disediakan bahasa, bagaimana mereka bekerja secara ringkas, dan apa konsekuensinya terhadap cara kita menulis kode yang aman dan efisien.

Artikel ini bukan panduan mendalam tentang semua struktur data, tujuannya adalah memberi konteks praktis bagi pembelajar pemula agar lebih mudah mengikuti implementasi ADT nanti.

Gambaran singkat: dua pendekatan umum untuk sequence

Dua pendekatan yang sering muncul saat memikirkan list adalah:

• menyimpan elemen dalam array dinamis (seperti Vec<T> di Rust), atau

• menyimpan elemen dalam node yang dihubungkan satu sama lain (linked list).

Secara singkat:

• Vec<T> menyimpan elemen berurutan di blok memori yang kontigu (heap). Ini membuat akses indeks cepat (O(1)) dan membuat seluruh struktur sangat ramah cache CPU. Operasi push di akhir efisien secara amortized, tapi sisip/hapus di tengah memerlukan pergeseran elemen (O(n)).

• LinkedList<T> terdiri dari node-node yang dialokasikan secara individual dan dihubungkan lewat pointer. Sisip/hapus pada posisi yang sudah diketahui bisa O(1), tetapi akses acak lambat karena membutuhkan traversal (O(n)). Selain itu, overhead pointer dan banyak alokasi membuat linked list seringkali kurang efisien dibanding Vec di banyak kasus nyata.

Intinya: Vec adalah pilihan default yang seringkali "cukup baik". Linked list cocok hanya pada kasus tertentu — misalnya, banyak operasi sisip di posisi yang sering diketahui tanpa perlu indexing acak.

Contoh penggunaan sederhana

Contoh ringkas Vec:

fn main() {
    let mut v: Vec<i32> = Vec::new();
    v.push(10);
    v.push(20);
    v.push(30);

    println!("v[1] = {}", v[1]); // akses langsung O(1)

    for (i, val) in v.iter().enumerate() {
        println!("index {}: {}", i, val);
    }

    // Akses aman menggunakan get
    if let Some(x) = v.get(5) {
        println!("value: {}", x);
    } else {
        println!("index 5 out of bounds");
    }
}

Contoh ringkas LinkedList dari pustaka standar:

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();
    list.push_back(10);
    list.push_back(20);
    list.push_front(5);

    for val in list.iter() {
        println!("{}", val);
    }

    list.pop_front();
    list.pop_back();
}

Keduanya mudah dipakai, tetapi perbedaan performa dan pola penggunaan harus jadi pertimbangan.

Jika ingin mengimplementasikan sendiri: Vec vs Box

Kalau tugas Anda nanti adalah mengimplementasikan ADT List/LinkedList:

• Cara paling cepat untuk memulai adalah membangun List di atas Vec<T> (array-backed list). Keuntungannya: implementasinya sederhana, dapat memanfaatkan API Vec untuk many operations, dan aman dari kompleksitas ownership yang menyusahkan pemula.

• Jika Anda ingin meniru representasi linked list dari buku teks, Anda akan membuat Node yang berisi elem dan next: Option<Box<Node>>. Box digunakan agar Node bisa memiliki ukuran tetap (Box adalah pointer ke heap) sehingga struktur rekursif menjadi mungkin.

Sketsa very-simple node:

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

struct SimpleLinkedList<T> {
    head: Link<T>,
}

impl<T> SimpleLinkedList<T> {
    fn new() -> Self { SimpleLinkedList { head: None } }

    fn push_front(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            next: self.head.take(), // memindahkan ownership head ke next
        });
        self.head = Some(new_node);
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|boxed_node| {
            let node = *boxed_node; // bongkar Box menjadi Node
            self.head = node.next;
            node.elem
        })
    }

    fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }
}

Potongan ini memperlihatkan idiom Rust yang sering dipakai pada struktur berantai: Option<Box<Node>>, take() untuk memindahkan ownership, dan map() untuk membongkar Option.

Ownership dan borrowing: inti pengelolaan memori di Rust

Sekilas aturan yang paling penting:

• Setiap value di Rust punya satu owner; ketika owner keluar scope, value di-drop otomatis (RAII).

• Peminjaman (&T atau &mut T) memungkinkan melihat/mengubah value tanpa mengambil ownership.

• Aturan dasar borrow:

  • Boleh banyak &T (immutable borrow) bersamaan.

  • Hanya satu &mut T (mutable borrow) pada suatu waktu.

  • Tidak boleh ada &T saat ada &mut T.

Alasan aturan ini konkret: mencegah pointer menggantung (dangling) dan race kondisi pada concurrent code. Contoh kecil:

let mut v = vec![1,2,3];
let r = &v[0];   // immutable borrow
// v.push(4);   // error: cannot borrow `v` as mutable while immutable borrow exists
println!("{}", r);

Compiler Rust menolak modifikasi yang bisa membuat referensi lama menjadi tidak valid (mis. re-allocation oleh push).

Diimplementasi linked list, Anda akan sering melihat take() untuk memindahkan ownership node, dan referensi hanya dipakai untuk melihat isi tanpa memindahkan.

Edge cases yang sering muncul bagi pemula

• Akses indeks di luar rentang (v[100]) → panic. Gunakan get() untuk mengembalikan Option.

• Modifikasi koleksi saat ada borrow aktif → error kompilasi. Pahami lifetimes (jangka hidup borrow) dasar untuk mengatasinya.

• Pada implementasi linked list manual, jangan lupa tangani None (kosong) dengan benar; Option<Box<Node>> membuat kasus kosong menjadi eksplisit.

• Jika memakai Rc/RefCell untuk shared ownership / interior mutability, hati-hati terhadap siklus referensi yang menyebabkan memory leak (gunakan Weak untuk memecah siklus).

• Performa: meski analisis kompleksitas penting (big-O), biaya riil tergantung faktor seperti cache locality — Vec sering menang karena memori kontigu.

Refleksi

• Untuk banyak kasus sehari-hari, gunakan Vec. Implementasi manual berguna untuk belajar konsep dan untuk kasus domain khusus.

• Ketika mulai mengimplementasikan ADT sendiri, pikirkan dulu: apakah kebutuhan utama akses indeks cepat, atau banyak operasi sisip/hapus di tengah? Pilihan ini akan memandu apakah Anda memilih array-backed atau linked structure.

• Belajar ownership & borrowing adalah kunci agar implementasi ADT di Rust aman dan bebas undefined behavior.

Referensi

• The Rust Programming Language. Steve Klabnik and Carol Nichols (editors). "The Rust Book", Chapter on Ownership and Chapters on Collections. 2024. URL: https://doc.rust-lang.org/book/

• Rust Standard Library — Collections documentation. The Rust Project (official). 2024. URL: https://doc.rust-lang.org/std/collections/

• Rust by Example — Vec examples. The Rust Project (official). URL: https://doc.rust-lang.org/rust-by-example/std/vec.html

• Too Many Linked Lists. Learning resource (tutorial series). Rust Unofficial. URL: https://rust-unofficial.github.io/too-many-lists/