ADT List berbasis Array kontigu

Latihan membuat instruksi pembelajaran yang menjelaskan tentang dua pendekatan dalam implementasi ADT List berbasis Array kontigu, ada pendekatan eksplisit/implisit ada juga pendekatan rata-kiri/tidak-rata-kiri. Dengan implementasi bahasa pemrograman Rust.

Singkatnya mencoba dua pendekatan, detail akan dibahas selanjutnya:

• ArrayListFixed (alt-2a: eksplisit, rata kiri — menyimpan jumlah elemen efektif n_eff dan memakai Vec<T> dengan kapasitas tetap).

• CircularArrayList (alt-2b: eksplisit, tidak rata-kiri — menyimpan head + n_eff, array fisik dapat memiliki ruang kosong di depan/belakang; implementasi ringkas yang menulis ulang buffer saat insert/remove di tengah supaya kode mudah dipahami).

ADT List berbasis Array kontigu.

Tujuan pembelajaran

• Memahami empat alternatif implementasi list berbasis array kontigu: implisit/eksplisit × rata-kiri / tidak rata-kiri.

• Mengetahui trade-offs masing-masing alternatif (ruang, kemudahan operasi, biaya shifting).

• Mampu mengimplementasikan dua varian yang paling praktis secara langsung: array rata-kiri (eksplisit) dan array tidak rata-kiri (circular / kepala terpisah).

• Dapat menangani kasus batas (edge cases) seperti insert di luar kapasitas, delete pada list kosong, dan mapping indeks logis → indeks fisik.

Prasyarat

• Pengetahuan dasar Rust: variabel, Vec, Option, struct, impl, Result/Option.

• Pemahaman sederhana soal indeks, loop, dan kompleksitas (O(1) vs O(n)).

Ringkasan alternatif (konsep)

Dokumen materi ADT List dengan array kontigu, membahas 4 alternatif utama:

• alt-1 (implisit): menandai slot kosong dengan mark (sentinel). Untuk menghitung length dan traversal, lihat elemen sampai ditemukan mark. Biasanya memerlukan inisialisasi seluruh array dengan mark. Kekurangan: perlu sentinel yang unik; berbahaya bila tipe tidak punya sentinel.

  • alt-1a: implisit, rata-kiri: semua elemen terisi harus berada di sebelah kiri (0..nEff-1) dan sisanya mark.

  • alt-1b: implisit, tidak rata-kiri: mark dapat tersebar; perlu fungsi firstIdx/lastIdx untuk menemukan indeks fisik pertama/terakhir.

• alt-2 (eksplisit): simpan nEff (jumlah elemen efektif). Traversal logis dilakukan pada indeks logis 0..nEff-1.

  • alt-2a: eksplisit, rata-kiri: implementasi paling sederhana — elemen logis disimpan di physical indices 0..nEff-1.

  • alt-2b: eksplisit, tidak rata-kiri: simpan juga head (indeks fisik dari elemen pertama) sehingga elemen logis berada mulai dari head dan bisa melingkar; berguna untuk menghindari banyak pergeseran bila sering insert/pop di depan.

Penjelasan itu mengilustrasikan perbedaan algoritmik (mis. cara menghitung length, insertAt, delete) untuk masing-masing alternatif.

Mana yang dipakai dulu dalam hal ini sebagai saran pembelajaran

1. Pelajari alt-2a (eksplisit, rata-kiri) dulu — paling mudah dipahami dan implementasinya langsung map ke Vec<T> dengan n_eff = data.len().

2. Setelah paham, pelajari alt-2b (eksplisit, tidak rata-kiri) — ide head + n_eff akan mengantar pada circular buffer dan solusi efisien untuk insert/pop di depan tanpa selalu memindahkan semua data.

3. Alt-1 (implisit) berguna sebagai latihan konsep mark, tetapi di Rust kita lebih idiomatis pakai Option<T> atau n_eff daripada sentinel numerik.

Implementasi Rust mengenai dua varian yang mudah dibaca

1) ArrayListFixed — alt-2a (eksplisit, rata-kiri)

• Backing: Vec<T> (pre-reserved capacity).

• Invariant: elemen logis berada di data[0..n_eff-1] (rata kiri).

• Insert/remove di tengah melakukan shift elemen ke kanan/kiri (O(n)).

• Simpel untuk pemula.

// ArrayListFixed: explicit, left-packed (alt-2a)
use std::fmt::Debug;

#[derive(Debug, Clone)]
pub struct ArrayListFixed<T> {
    data: Vec<T>,     // penyimpanan logis (0..n_eff-1 valid)
    capacity: usize,  // kapasitas maksimum (fixed)
}

impl<T> ArrayListFixed<T>
where
    T: Clone + Debug,
{
    /// Buat list baru dengan kapasitas tetap
    pub fn new(capacity: usize) -> Self {
        ArrayListFixed {
            data: Vec::with_capacity(capacity),
            capacity,
        }
    }

    /// panjang efektif (nEff)
    pub fn len(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Dapatkan referensi ke elemen logis pada indeks i (0..len-1)
    pub fn get(&self, i: usize) -> Option<&T> {
        self.data.get(i)
    }

    /// Tambah di akhir (insertLast)
    pub fn push_back(&mut self, value: T) -> Result<(), String> {
        if self.data.len() < self.capacity {
            self.data.push(value);
            Ok(())
        } else {
            Err("List penuh: tidak bisa push_back".into())
        }
    }

    /// Tambah di awal (insertFirst) — perlu shift O(n)
    pub fn push_front(&mut self, value: T) -> Result<(), String> {
        if self.data.len() < self.capacity {
            self.data.insert(0, value); // insert memindahkan elemen kanan
            Ok(())
        } else {
            Err("List penuh: tidak bisa push_front".into())
        }
    }

    /// Sisipkan pada index (0..=len)
    pub fn insert_at(&mut self, index: usize, value: T) -> Result<(), String> {
        if self.data.len() >= self.capacity {
            return Err("List penuh".into());
        }
        if index > self.data.len() {
            return Err(format!("Index {} di luar jangkauan (len={})", index, self.data.len()));
        }
        self.data.insert(index, value); // insert memindahkan elemen jika perlu
        Ok(())
    }

    /// Hapus pada posisi index (deleteAt)
    pub fn remove_at(&mut self, index: usize) -> Option<T> {
        if index < self.data.len() {
            Some(self.data.remove(index)) // remove memindahkan elemen
        } else {
            None
        }
    }

    /// pop terakhir (deleteLast)
    pub fn pop_back(&mut self) -> Option<T> {
        self.data.pop()
    }

    /// pop pertama (deleteFirst) — O(n)
    pub fn pop_front(&mut self) -> Option<T> {
        if self.data.is_empty() {
            None
        } else {
            Some(self.data.remove(0))
        }
    }

    /// cari index of value (indexOf)
    pub fn index_of(&self, value: &T) -> Option<usize>
    where
        T: PartialEq,
    {
        self.data.iter().position(|x| x == value)
    }

    /// konkatenasi (concat) -> baru (memerlukan Clone)
    pub fn concat(&self, other: &ArrayListFixed<T>) -> ArrayListFixed<T> {
        let mut new = ArrayListFixed::new(self.capacity + other.capacity);
        new.data.extend_from_slice(&self.data);
        new.data.extend_from_slice(&other.data);
        new
    }
}

Penjelasan singkat

• new(capacity) membuat list kosong yang dapat menampung sampai capacity.

• push_back dan push_front: push_front akan memindahkan semua elemen ke kanan (biaya O(n)).

• insert_at memeriksa kapasitas dan memanggil Vec::insert — mudah dibaca untuk pemula.

• remove_at dan pop_front memindahkan elemen ke kiri setelah penghapusan.

Catatan: implementasi ini meniru alt-2a tetapi memanfaatkan Vec<T> agar kode ringkas. Vec::with_capacity tidak langsung mengisi nilai; kita menggunakan Vec<T> sehingga n_eff = data.len().

2) CircularArrayList — alt-2b (eksplisit, tidak rata-kiri)

• Backing: Vec<Option<T>> berukuran tetap capacity.

• Simpan head (indeks fisik elemen pertama) dan n_eff.

• Operasi push_front/push_back dan pop dapat dilakukan tanpa memindahkan seluruh elemen (O(1)).

• Untuk kemudahan pembelajaran, implementasi insert_at/remove_at menggunakan strategi rebuild buffer (baca semua elemen logis ke Vec sementara, ubah, lalu tulis ulang) — jelas dan sederhana walau tidak optimal.

// CircularArrayList: explicit, not left-packed (alt-2b)
// Implementasi sederhana: saat insert/remove di tengah, kita rebuild buffer agar kode mudah dimengerti.

use std::fmt::Debug;

#[derive(Debug, Clone)]
pub struct CircularArrayList<T> {
    data: Vec<Option<T>>, // physical buffer, length = capacity
    head: usize,          // indeks fisik dari elemen logis ke-0
    n_eff: usize,         // jumlah elemen efektif
    capacity: usize,
}

impl<T> CircularArrayList<T>
where
    T: Clone + Debug,
{
    /// Buat list circular baru dengan kapasitas tertentu
    pub fn new(capacity: usize) -> Self {
        CircularArrayList {
            data: vec![None; capacity],
            head: 0,
            n_eff: 0,
            capacity,
        }
    }

    pub fn len(&self) -> usize {
        self.n_eff
    }

    pub fn is_empty(&self) -> bool {
        self.n_eff == 0
    }

    /// helper: mapping indeks logis (0..n_eff-1) -> indeks fisik di buffer
    fn phys_idx(&self, logical_idx: usize) -> usize {
        (self.head + logical_idx) % self.capacity
    }

    /// get elemen logis pada i
    pub fn get(&self, i: usize) -> Option<&T> {
        if i < self.n_eff {
            self.data[self.phys_idx(i)].as_ref()
        } else {
            None
        }
    }

    /// push_back (append di akhir)
    pub fn push_back(&mut self, value: T) -> Result<(), String> {
        if self.n_eff >= self.capacity {
            return Err("List penuh".into());
        }
        let idx = self.phys_idx(self.n_eff);
        self.data[idx] = Some(value);
        self.n_eff += 1;
        Ok(())
    }

    /// push_front (masuk di depan)
    pub fn push_front(&mut self, value: T) -> Result<(), String> {
        if self.n_eff >= self.capacity {
            return Err("List penuh".into());
        }
        // geser head mundur (mod capacity)
        self.head = (self.head + self.capacity - 1) % self.capacity;
        self.data[self.head] = Some(value);
        self.n_eff += 1;
        Ok(())
    }

    /// pop_front
    pub fn pop_front(&mut self) -> Option<T> {
        if self.n_eff == 0 {
            return None;
        }
        let idx = self.head;
        let val = self.data[idx].take();
        self.head = (self.head + 1) % self.capacity;
        self.n_eff -= 1;
        val
    }

    /// pop_back
    pub fn pop_back(&mut self) -> Option<T> {
        if self.n_eff == 0 {
            return None;
        }
        let last_idx = self.phys_idx(self.n_eff - 1);
        let val = self.data[last_idx].take();
        self.n_eff -= 1;
        val
    }

    /// insert_at (0..=len). Untuk kemudahan pembelajaran, kita rebuild buffer:
    /// 1) baca semua elemen logis ke Vec<T>
    /// 2) insert value pada posisi yang diminta
    /// 3) tulis ulang data ke physical buffer mulai head=0
    pub fn insert_at(&mut self, index: usize, value: T) -> Result<(), String> {
        if self.n_eff >= self.capacity {
            return Err("List penuh".into());
        }
        if index > self.n_eff {
            return Err(format!("Index {} di luar jangkauan (len={})", index, self.n_eff));
        }

        // 1) kumpulkan semua elemen logis
        let mut tmp: Vec<T> = Vec::with_capacity(self.n_eff + 1);
        for i in 0..self.n_eff {
            tmp.push(self.get(i).unwrap().clone());
        }
        // 2) sisipkan value
        tmp.insert(index, value);
        // 3) tulis ulang ke buffer
        self.data = vec![None; self.capacity];
        self.head = 0;
        for (i, v) in tmp.into_iter().enumerate() {
            self.data[i] = Some(v);
        }
        self.n_eff += 1;
        Ok(())
    }

    /// remove_at: sama, rebuild buffer sederhana
    pub fn remove_at(&mut self, index: usize) -> Option<T> {
        if index >= self.n_eff {
            return None;
        }
        // kumpulkan semua elemen
        let mut tmp: Vec<T> = Vec::with_capacity(self.n_eff);
        for i in 0..self.n_eff {
            tmp.push(self.get(i).unwrap().clone());
        }
        // ambil elemen yang dihapus
        let removed = tmp.remove(index);
        // tulis ulang
        self.data = vec![None; self.capacity];
        self.head = 0;
        for (i, v) in tmp.into_iter().enumerate() {
            self.data[i] = Some(v);
        }
        self.n_eff -= 1;
        Some(removed)
    }

    /// index_of (cari nilai pertama)
    pub fn index_of(&self, value: &T) -> Option<usize>
    where
        T: PartialEq,
    {
        for i in 0..self.n_eff {
            if let Some(v) = self.get(i) {
                if v == value {
                    return Some(i);
                }
            }
        }
        None
    }
}

Penjelasan singkat

• data: Vec<Option<T>> mewakili slot fisik. head menunjuk indeks fisik elemen logis pertama. n_eff jumlah elemen.

• push_back menulis pada phys_idx(n_eff). push_front memundurkan head lalu menulis. Keduanya O(1).

• insert_at dan remove_at di sini diimplementasikan dengan rebuild buffer demi keterbacaan pada pemula; algoritma ini jelas tapi O(n). Versi optimal akan memindahkan sedikit elemen di sisi yang lebih kecil.

Perbandingan ringkas kedua implementasi

• ArrayListFixed (rata-kiri)

  • Implementasi ringkas, mudah dimengerti.

  • push_back O(1) amortized, insert_at(0) O(n).

  • Baik untuk aplikasi dengan banyak akses acak / append.

• CircularArrayList (tidak rata-kiri)

  • Mendukung push_front/pop_front O(1) tanpa shift.

  • insert_at/remove_at saat ini O(n) karena rebuild — implementasi real bisa memindahkan sebagian elemen untuk efisiensi.

  • Baik untuk pola queue/deque: banyak operasi di depan/belakang.

Edge cases yang harus diajarkan dan dites

• Insert ketika list penuh → harus return error (capacity reached).

• Insert pada index > len → invalid (return Err).

• Remove/pop pada list kosong → return None (aman).

• Mapping indeks logis → fisik untuk circular: periksa formula (head + i) % capacity.

• Rebuild semantics: setelah rebuild kita set head = 0 agar physical layout konsisten, penting untuk dipahami.

• Clone requirement: beberapa operasi (concat, rebuild) memerlukan T: Clone; diskusikan biaya kloning pada tipe besar.

• Pilih sentinel vs Option: dokumen membahas alt-1 (implisit) yang memakai sentinel/mark; di Rust lebih idiomatis pakai Option<T> alih-alih sentinel numeric yang rentan error.

Contoh penggunaan ADT List di proyek nyata

• Playlist lagu — urutan lagu dapat diinsert di tengah; jika sering insert di awal pertimbangkan circular variant atau linked list.

• Queue/event buffer — pattern FIFO: gunakan circular buffer (push_back/pop_front) yang efisien.

• History / undo list — array-backed baik untuk indexing snapshot.

• Cache sederhana — array + pointer head/tail bisa digunakan untuk implementasi ring buffer.

Latihan yang direkomendasikan dengan clue

1. Implementasikan insert_at optimal pada CircularArrayList tanpa membuat full rebuild — pilih sisi (kiri/kanan) yang melakukan pergeseran paling sedikit.

   • Clue: jika index dekat head, geser blok di kiri; jika dekat n_eff, geser blok kanan.

2. Implementasikan alt-1a (implisit, rata-kiri) menggunakan Vec<Option<T>> dan sentinel None sebagai mark. Pastikan invariant: tidak boleh ada None di antara Some.

   • Clue: sebelum insert, pastikan semua Some berada di sebelah kiri.

3. Uji invariants: tulis unit tests untuk kedua struktur yang memeriksa perilaku edge cases (insert penuh, remove kosong, mapping indeks).

Refleksi & pertanyaan dengan clue

• Mengapa menyimpan n_eff (alt-2) lebih aman/efisien dibanding sentinel (alt-1)? Clue: n_eff eksplisit menjelaskan jumlah elemen; sentinel membutuhkan nilai khusus yang mungkin tidak tersedia untuk semua tipe.

• Kapan memilih implementasi tidak-rata-kiri (circular) daripada rata-kiri? Clue: ketika banyak operasi di depan (push_front/pop_front) dan ingin menghindari O(n) shift terus-menerus.

• Apa biaya memakai rebuild buffer pada insert_at untuk CircularArrayList? Clue: implementasi rebuild jelas dan aman, tapi akan menyalin seluruh elemen → O(n). Untuk produksi sebaiknya implementasikan shift partial.

• Bagaimana memilih kapasitas awal? Apa trade-offnya? Clue: kapasitas kecil → sering gagal insert; kapasitas besar → memori teralokasi tapi tidak digunakan. Untuk Vec biasa, Anda bisa mulai dari kapasitas kecil dan gunakan reallocation. Untuk fixed-array, pertimbangkan kebutuhan aplikasi.

Referensi

• Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung. Implementasi ADT List dengan Array Kontigu — materi perkuliahan W03 (slide).

• The Rust Project. The Rust Programming Language (The Book) — bagian Collections & Ownership. URL: https://doc.rust-lang.org/book/

• The Rust Project. std::vec::Vec — dokumentasi. URL: https://doc.rust-lang.org/std/vec/struct.Vec.html