ADT List dengan implementasi Array
Latihan membuat instruksi pembelajaran untuk ADT List, dengan harapan melanjutkan pembahasan ADT untuk yang lebih kompleks berupa List. Untuk implementasi dalam bahasa pemrograman Rust, sehingga meskipun sudah ada List (Vec), kita akan menggunakan untuk pembelajaran dengan membangun sendiri.
List (sering disebut sequence) adalah kumpulan elemen bertipe sama dengan keterurutan tertentu. Pada artikel ini kita membahas ADT List dari sudut implementasi menggunakan array dinamis (Vec
di Rust). Nanti, setelah paham konsep ini, baru kita akan pelajari implementasi lain (mis. linked list).
Tujuan Pembelajaran
Setelah mempelajari materi ini, Anda akan mampu:
Menjelaskan konsep ADT List: head, length, empty list, traversal.
Menyebutkan operasi utama ADT List (isEmpty, get, set, insert, delete, search, concat).
Mengimplementasikan ADT List sederhana di Rust menggunakan
Vec<T>
sebagai backing storage.Menangani kasus batas (edge cases) seperti insert/delete pada indeks tidak valid dan list kosong.
Memahami trade-off performa (kompleksitas waktu) untuk operasi list berbasis array.
Menyusun ide bagaimana ADT List digunakan dalam proyek nyata (mis. playlist, buffer, todo list).
Prasyarat
Pengetahuan dasar Rust: variabel, fungsi, struct, method (
impl
), generics ringan, traitPartialEq
/Clone
.Konsep dasar algoritma: apa itu indeks, O(1) vs O(n).
(Opsional) sedikit pengalaman memakai
Vec<T>
di Rust.
Konsep ADT List serta istilah penting
head: elemen pertama.
length: jumlah elemen.
empty list: list tanpa elemen.
traversal: proses mengunjungi elemen satu per satu.
Operasi standar:
is_empty
,length
,get(index)
,set(index, value)
,index_of(value)
/search,insert_front
,insert_back
,insert_at(index)
,delete_front
,delete_back
,delete_at(index)
,concat
,traverse
.
Desain implementasi: Array-backed, menggunakan Vec
Keputusan utama: gunakan Vec<T>
sebagai backing array karena:
Vec
mengalokasikan memory di heap, dapat berubah ukuran, dan sudah dioptimalkan di Rust.Implementasi menjadi sederhana dan mudah dipahami pemula.
Vec
memberi operasi indeks O(1) dan API praktis (push
,insert
,remove
,get
,len
).
Catatan: untuk kebutuhan lain (mis. insert/remove di depan yang sering), kita akan pelajari struktur lain nanti (LinkedList, Deque).
API yang akan kita buat secara ringkas
Implementasi akan menyediakan method:
new()
→ buat list kosongis_empty()
→ true/falselen()
→ panjang listindex_of(&value)
→ posisi pertama yang cocok (Option)get(index)
→ Option<&T>set(index, value)
→ Result<(), String> atau Optionpush_back(value)
→ append di akhirpush_front(value)
→ insert di awalinsert_at(index, value)
→ insert pada posisi (0..=len)pop_back()
→ Optionpop_front()
→ Optionremove_at(index)
→ Optionconcat(&other)
→ gabungkan dua list menjadi list baruiter()
→ traversal
Semua method dibuat sederhana, aman mengembalikan Option
/Result
untuk kasus salah.
Kompleksitas waktu secara ringkas
get(index)
: O(1)set(index)
: O(1)push_back
: amortized O(1)push_front
/insert_at(index)
/remove_at(index)
(kecuali di akhir): O(n) karena pergeseran elemenindex_of
/ search: O(n)concat
yang membuat salinan: O(n + m) jika kita membuat list baru
Implementasi Rust dengan kode yang mudah dibaca
Berikut implementasi ArrayList<T>
berbasis Vec<T>
. Kode ini dimaksudkan agar mudah diikuti pemula: dengan sedikit fitur, banyak komentar singkat.
// src/main.rs
// Implementasi ADT List sederhana menggunakan Vec sebagai backing storage.
use std::fmt::Debug;
#[derive(Debug, Clone)]
pub struct ArrayList<T> {
data: Vec<T>, // penyimpanan kontigu di heap
}
impl<T> ArrayList<T> {
/// Buat list kosong
pub fn new() -> Self {
ArrayList { data: Vec::new() }
}
/// Buat list dari Vec (helper)
pub fn from_vec(v: Vec<T>) -> Self {
ArrayList { data: v }
}
/// Apakah list kosong?
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
/// Panjang list
pub fn len(&self) -> usize {
self.data.len()
}
/// Dapatkan referensi ke elemen pada index (aman): mengembalikan Option<&T>
pub fn get(&self, index: usize) -> Option<&T> {
self.data.get(index)
}
/// Set elemen pada index, mengembalikan Err jika index out of bounds
pub fn set(&mut self, index: usize, value: T) -> Result<(), String> {
if index < self.data.len() {
self.data[index] = value;
Ok(())
} else {
Err(format!("Index {} di luar batas (len={})", index, self.len()))
}
}
/// Cari posisi pertama yang cocok dengan value (membutuhkan PartialEq)
pub fn index_of(&self, value: &T) -> Option<usize>
where
T: PartialEq,
{
self.data.iter().position(|x| x == value)
}
/// Tambah elemen di akhir (push_back)
pub fn push_back(&mut self, value: T) {
self.data.push(value);
}
/// Tambah elemen di awal (push_front) — O(n)
pub fn push_front(&mut self, value: T) {
self.data.insert(0, value);
}
/// Sisipkan pada posisi index (0..=len). Jika index > len => Err
pub fn insert_at(&mut self, index: usize, value: T) -> Result<(), String> {
if index <= self.data.len() {
self.data.insert(index, value);
Ok(())
} else {
Err(format!("Index {} di luar batas untuk insert (len={})", index, self.len()))
}
}
/// Hapus dan kembalikan elemen paling akhir (pop_back)
pub fn pop_back(&mut self) -> Option<T> {
self.data.pop()
}
/// Hapus dan kembalikan elemen paling depan (pop_front) — O(n)
pub fn pop_front(&mut self) -> Option<T> {
if self.data.is_empty() {
None
} else {
Some(self.data.remove(0))
}
}
/// Hapus pada posisi index dan kembalikan (remove_at)
pub fn remove_at(&mut self, index: usize) -> Option<T> {
if index < self.data.len() {
Some(self.data.remove(index))
} else {
None
}
}
/// Gabungkan dua list menjadi list baru (membuat salinan)
pub fn concat(&self, other: &ArrayList<T>) -> ArrayList<T>
where
T: Clone,
{
let mut v = self.data.clone();
v.extend_from_slice(&other.data);
ArrayList::from_vec(v)
}
/// Traversal: iterasi read-only
pub fn iter(&self) -> std::slice::Iter<'_, T> {
self.data.iter()
}
}
// Contoh penggunaan di main()
fn main() {
// Contoh dengan tipe i32
let mut l = ArrayList::new();
// tambahkan beberapa elemen
l.push_back(10); // [10]
l.push_back(20); // [10, 20]
l.push_front(5); // [5, 10, 20]
println!("List awal: {:?}", l); // debug print
// get dan len
println!("Panjang list: {}", l.len());
if let Some(v) = l.get(1) {
println!("Elemen indeks 1: {}", v);
}
// set
match l.set(1, 15) {
Ok(()) => println!("Set sukses"),
Err(e) => println!("Set error: {}", e),
}
println!("Set hasil: {:?}", l);
// index_of (cari)
if let Some(pos) = l.index_of(&20) {
println!("Nilai 20 ditemukan pada index {}", pos);
} else {
println!("Nilai 20 tidak ditemukan");
}
// insert_at
l.insert_at(2, 17).expect("insert_at gagal");
println!("Setelah insert_at(2,17): {:?}", l);
// remove_at
if let Some(removed) = l.remove_at(1) {
println!("Removed: {}", removed);
}
println!("Setelah remove_at(1): {:?}", l);
// concat
let mut other = ArrayList::new();
other.push_back(100);
other.push_back(200);
let combined = l.concat(&other);
println!("Gabungan list: {:?}", combined);
// traversal
for (i, val) in combined.iter().enumerate() {
println!("idx {} => {:?}", i, val);
}
// contoh pop
println!("pop_back => {:?}", combined.data.get(combined.len()-1)); // contoh lihat elemen terakhir
}
Penjelasan singkat kode:
ArrayList<T>
adalah pembungkus sederhana di atasVec<T>
.Metode yang mengubah posisi selain akhir (mis.
insert(0, ...)
atauremove(0)
) memerlukan pergeseran elemen — jadi O(n).Untuk safety, operasi yang raw (index di luar batas) mengembalikan
Err
atauOption
sehingga caller dapat menangani error.
Alternatif: fixed-capacity array dalam tulisan singkat
Kadang ADT List di kelas juga membahas array statis dengan slot kosong yang ditandai Option<T>
(mis. implementasi buffer ringkas). Contoh pendek (ide, bukan implementasi penuh):
// sketsa: fixed capacity list dengan Option<T>
struct FixedList<T> {
data: Box<[Option<T>]>, // array di heap dengan ukuran tetap
len: usize,
}
Kegunaan: cocok jika Anda butuh batas maksimum tetap dan ingin menghindari reallocation runtime. Option<T>
menandai slot kosong vs terisi.
Edge cases yang penting untuk diajarkan dan dites
Insert at invalid index: tentukan policy (return Err) dan jangan panic.
Remove from empty list:
pop_front
/pop_back
harus aman (mengembalikanNone
).Search for element not present:
index_of
mengembalikanNone
.Mutation saat traversal: jangan ubah list sembari memegang referensi iterator yang mem-borrow (Rust akan memblokir jika berpotensi unsafe).
Clone vs move:
concat
perluT: Clone
karena kita membuat salinan; diskusikan biaya kloning.Performansi: sisip di awal/ tengah mahal (O(n)); jelaskan kapan ini mungkin jadi masalah (lists besar, operasi banyak).
Kegunaan ADT List di proyek nyata
Beberapa contoh nyata di mana ADT List dipakai:
Daftar tugas (todo list): input user sekuensial, sering membutuhkan insert dan delete.
Playlist musik: urutan lagu, insert/remove di posisi tertentu.
History / Undo stack: menyimpan snapshot (meskipun stack dapat lebih cocok).
Buffer input: kumpulan pesan atau event sebelum diproses. Untuk sebagian besar aplikasi modern,
Vec
sudah cukup sebagai implementasi List.
Latihan yang direkomendasikan (berjenjang)
Implementasikan
ArrayList<String>
dan buat CLI kecil: acceptadd
,remove index
,list
,find value
.Ubah
concat
agar mengambil ownership (consume other list) supaya tidak perluClone
. Bandingkan performa.Implementasikan
FixedList<T>
berbasisBox<[Option<T>]>
dengan operasi insert/remove tanpa reallocation.Bandingkan waktu operasi
insert_front
padaArrayList
vsLinkedList
(nanti) untuk input berukuran besar.
Refleksi & pertanyaan dilengkapi dengan clue
Mengapa
Vec
sering menjadi backing storage untuk list di Rust? Clue: efisiensi cache dan API yang matang;Vec
menyimpan data kontigu di heap.Kapan sebaiknya Anda memilih implementasi berbasis array daripada linked list? Clue: ketika akses indeks cepat dan cache locality penting; ketika jumlah sisip/hapus di tengah tidak dominan.
Apa konsekuensi penggunaan
T: Clone
padaconcat
? Clue: perlu membuat salinan tiap elemen -> biaya memori & waktu. Pertimbangkan opsi mengambil ownership sebagai alternatif.Bagaimana Anda akan menangani error input (mis. user memasukkan index out-of-bound)? Clue: jangan panic; beri pesan error yang jelas dan gunakan
Option
/Result
.
Pengujian otomatis (unit tests)
Letakkan blok #[cfg(test)]
ini di akhir file src/main.rs
(atau di file library jika Anda memisahkannya menjadi crate lib). Untuk menjalankan tes: cargo test
(penjelasan singkat ada di akhir).
// --------------------
// Unit tests untuk ArrayList<T>
// --------------------
#[cfg(test)]
mod tests {
use super::ArrayList;
// Tes pembuatan dan operasi dasar push_back, len, is_empty
#[test]
fn test_new_and_push_len() {
// Buat list baru (kosong)
let mut list: ArrayList<i32> = ArrayList::new();
// Awalnya kosong
assert!(list.is_empty());
assert_eq!(list.len(), 0);
// Tambah elemen di akhir
list.push_back(10);
list.push_back(20);
// Sekarang tidak kosong dan panjang=2
assert!(!list.is_empty());
assert_eq!(list.len(), 2);
// Elemen di indeks 0 dan 1 sesuai yang dimasukkan
assert_eq!(list.get(0), Some(&10));
assert_eq!(list.get(1), Some(&20));
}
// Tes push_front, pop_front, pop_back
#[test]
fn test_push_front_and_pop() {
let mut list = ArrayList::new();
// push_front pada list kosong
list.push_front(1); // [1]
list.push_front(2); // [2,1]
list.push_back(3); // [2,1,3]
assert_eq!(list.len(), 3);
// pop_front mengembalikan 2 (elemen paling depan)
assert_eq!(list.pop_front(), Some(2));
// pop_back mengembalikan 3 (elemen paling belakang)
assert_eq!(list.pop_back(), Some(3));
// sisa [1]
assert_eq!(list.len(), 1);
assert_eq!(list.get(0), Some(&1));
}
// Tes set dan error handling untuk set out-of-bounds
#[test]
fn test_set_and_out_of_bounds() {
let mut list = ArrayList::new();
list.push_back(5);
list.push_back(6);
// set indeks 1 sukses
assert!(list.set(1, 60).is_ok());
assert_eq!(list.get(1), Some(&60));
// set indeks out of bounds mengembalikan Err
let result = list.set(5, 100);
assert!(result.is_err());
}
// Tes index_of (search) dan remove_at
#[test]
fn test_index_of_and_remove_at() {
let mut list = ArrayList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);
// index_of untuk nilai 20
assert_eq!(list.index_of(&20), Some(1));
// remove_at posisi 1 (menghapus 20)
assert_eq!(list.remove_at(1), Some(20));
// sekarang index_of 20 harus None
assert_eq!(list.index_of(&20), None);
// remove_at index invalid -> None
assert_eq!(list.remove_at(100), None);
}
// Tes insert_at valid dan invalid
#[test]
fn test_insert_at() {
let mut list = ArrayList::new();
list.push_back(1);
list.push_back(3);
// insert 2 pada index 1 -> [1,2,3]
assert!(list.insert_at(1, 2).is_ok());
assert_eq!(list.get(1), Some(&2));
// insert pada index > len -> Err
assert!(list.insert_at(10, 99).is_err());
}
// Tes concat: gabungkan dua list menjadi list baru
#[test]
fn test_concat() {
let mut a = ArrayList::new();
a.push_back(1);
a.push_back(2);
let mut b = ArrayList::new();
b.push_back(3);
b.push_back(4);
// concat mengembalikan list baru [1,2,3,4]
let c = a.concat(&b);
assert_eq!(c.len(), 4);
assert_eq!(c.get(0), Some(&1));
assert_eq!(c.get(3), Some(&4));
// Pastikan a dan b tidak berubah (concat menggunakan clone)
assert_eq!(a.len(), 2);
assert_eq!(b.len(), 2);
}
// Tes traversal iter() menghasilkan elemen dalam urutan yang benar
#[test]
fn test_iter_traversal() {
let mut list = ArrayList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);
let mut collected = vec![];
for v in list.iter() {
collected.push(*v);
}
assert_eq!(collected, vec![10, 20, 30]);
}
// Tes pop_front/pop_back pada list kosong -> None
#[test]
fn test_pop_empty() {
let mut list: ArrayList<i32> = ArrayList::new();
assert_eq!(list.pop_front(), None);
assert_eq!(list.pop_back(), None);
}
}
Penjelasan singkat tiap unit test
test_new_and_push_len
Memverifikasi pembuatan list kosong, operasipush_back
,len()
,is_empty()
danget()
. Pastikan kondisi dasar bekerja.test_push_front_and_pop
Mengetespush_front
,push_back
,pop_front
,pop_back
. Ini memvalidasi perilaku LIFO di depan dan belakang.test_set_and_out_of_bounds
Memastikanset()
bekerja untuk indeks valid dan menghasilkanErr
saat indeks tidak valid; ini menguji penanganan error tanpa panic.test_index_of_and_remove_at
Memeriksaindex_of()
(pencarian) danremove_at()
(hapus posisi tertentu), termasuk perilaku saat menghapus elemen dan ketika index tidak valid.test_insert_at
Mengujiinsert_at()
untuk posisi valid (menyisip) dan invalid (mengembalikanErr
).test_concat
Memastikanconcat()
membuat list baru yang merupakan gabungan dari dua list tanpa memodifikasi list asal (karena implementasi menggunakan clone).test_iter_traversal
Mengujiiter()
agar traversal menghasilkan urutan elemen yang benar.test_pop_empty
Mengecek bahwapop_front()
danpop_back()
aman pada list kosong (mengembalikanNone
).
Catatan implementasi & testing
Semua test memakai tipe
i32
yang memenuhi traitClone
/PartialEq
sehingga cocok untuk metode seperticoncat
danindex_of
.Pengujian ini fokus pada fungsi-fungsi publik dan perilaku safety-first (menggunakan
Option
/Result
alih-alih panic).Jika Anda mengubah API (mis. ubah
set
untuk panic daripada return Result), sesuaikan test.Tambahkan lebih banyak test untuk kasus performa atau stress (mis. berukuran besar) jika diinginkan.
Cara menjalankan tes
Jalankan di terminal pada root proyek:
cargo test
Perintah ini akan meng-compile crate dan menjalankan semua unit test, menampilkan ringkasan hasil (passed/failed).
Untuk mempelajari pemrograman Rust lebih lengkap bisa belajar di kelas Belajar Pemrograman Rust untuk Pemula di Dicoding.
Referensi
Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung. ADT List — IF2110/IF2111, materi perkuliahan.
The Rust Project. The Rust Programming Language (The Book). Available: https://doc.rust-lang.org/book/
The Rust Project. std::vec::Vec documentation. Available: https://doc.rust-lang.org/std/vec/struct.Vec.html