Linked list

Menambahkan nilai di depan linked list mengubah dua pointer, entah list itu berisi 4 nilai atau 4 juta.

Nilai yang menunjuk ke nilai berikutnya

Array menyimpan nilai-nilainya berdampingan, dan karena itulah bagian depannya mahal untuk diubah. Linked list membuang aturan itu. Setiap nilai tinggal dalam catatan kecilnya sendiri yang disebut node (simpul), dan node-node itu bisa berada di mana saja di memori. Catatan 6.006 MIT menggambarkan node dengan dua bagian: item, dan next, yaitu pointer (penunjuk) ke node berikutnya. List itu sendiri hanya mengingat node pertama, yang disebut head. Next milik node terakhir bernilai null, yang menandai ujungnya.

Untuk membaca list, kamu mulai dari head lalu mengikuti pointer next satu per satu, seperti mengikuti rangkaian catatan yang masing-masing memberi tahu di mana catatan berikutnya disembunyikan. Itu ada biayanya. Tidak ada rumus untuk alamat node keempat, jadi mengambil nilai di posisi i berarti mengunjungi i + 1 node. MIT mencantumkan get at(i) untuk linked list sebagai O(n), padahal array melakukannya dalam satu langkah.

// satu node per nilai: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// telusuri list
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Mengubah list dengan menyambung ulang

Keuntungannya muncul saat kamu mengubah list. Untuk menaruh nilai baru di depan, buat node yang next-nya adalah head saat ini, lalu arahkan head ke node baru itu. Dua perubahan pointer, dan tidak ada yang lain yang bergeser. Menghapus node depan cukup satu perubahan: arahkan head ke head.next. Bandingkan dengan array, yang untuk operasi yang sama harus menggeser setiap nilai.

Di tengah list, pekerjaannya adalah mencari tempatnya. Untuk menyisipkan di posisi i, kamu berjalan ke node tepat sebelumnya (i kunjungan), lalu melakukan dua perubahan pointer yang sama: new.next = prev.next, lalu prev.next = new. Urutannya penting. Kalau prev.next diubah lebih dulu, sisa list hilang, karena tidak ada lagi yang menunjuk ke sana. Di laboratorium, satu langkah adalah satu node dikunjungi atau satu pointer diubah, jadi menyisipkan di posisi 2 pada list 4 node memakan 2 kunjungan ditambah 2 perubahan, 4 langkah.

Kapan memakainya

Linked list cocok kalau sebagian besar perubahan terjadi di tempat yang pointer-nya sudah kamu pegang, seperti bagian depan, dan kamu jarang butuh posisi i. Antrean dan tumpukan bisa dibangun dari linked list, begitu pula rantai di dalam tabel hash pada unit berikutnya. Ada beberapa variasinya. Doubly linked list memberi setiap node pointer prev juga, sehingga kamu bisa berjalan mundur dan menghapus sebuah node dalam satu langkah begitu node itu kamu pegang. Menyimpan pointer tail selain head membuat penambahan di ujung menjadi murah.

Dalam JavaScript sehari-hari kamu jarang menulis linked list, karena array sudah dioptimalkan dengan baik dan cache pada prosesor modern lebih menyukai nilai yang disimpan berdampingan. Meski begitu, gagasannya tetap penting: pohon, graf, dan banyak struktur pustaka dibangun dari node dan pointer persis dengan cara ini.