Jadi, Ceritakan Tentang Daftar Tertaut
Baru-baru ini lulus dari coding bootcamp, saya telah mempelajari struktur data dan algoritme untuk meningkatkan pengetahuan dasar saya. Daftar tertaut adalah struktur data yang relatif sederhana, tetapi merupakan dasar untuk struktur data yang lebih kompleks ke depannya. Artikel ini akan membahas daftar tertaut - kekuatan, kelemahan, dan cara menerapkannya.
Sederhananya, struktur data adalah cara untuk mengatur, dan menyimpan data secara efisien
Apa Itu Struktur Data?
Sederhananya, struktur data adalah cara untuk mengatur, dan menyimpan data secara efisien. Ini memungkinkan kami untuk menyimpan informasi sehingga kami dapat mengaksesnya untuk nanti - mencari item tertentu, atau menyortirnya untuk memiliki urutan tertentu atau bahkan mengelola kumpulan data besar. JavaScript memiliki struktur data yang mungkin Anda kenal - array dan objek. Ini adalah struktur data primitif yang asli dari bahasa tersebut. Struktur data non-primitif adalah struktur data yang didefinisikan oleh programmer. Contohnya termasuk tumpukan, antrian, pohon, grafik, dan tabel hash.
Apa Itu Daftar Tertaut?
Daftar tertaut adalah struktur data linier yang menyimpan elemen secara berurutan. Terdengar akrab? Mereka mirip dengan array tetapi tidak persis sama. Array memiliki indeks nol , yang berarti setiap indeks dipetakan ke sebuah nilai, dan elemen pertama dari array dimulai pada indeks 0. Anda dapat dengan mudah menarik elemen dari array, selama Anda mengetahui indeksnya.
Di sisi lain, daftar tertaut terdiri dari node yang mengarah ke node lain. Setiap node hanya mengetahui dirinya sendiri dan node berikutnya. Sebagai struktur data linier, item disusun secara berurutan. Anda dapat menganggapnya sebagai kereta - setiap gerbong kereta terhubung ke gerbong berikutnya, dan seterusnya. Daftar tertaut tidak diindeks , jadi Anda tidak dapat mengakses elemen ke-5 secara langsung. Anda harus mulai dari awal, ke depan, dan ke depan sampai Anda menemukan elemen ke-5. Node pertama disebut head, dan node terakhir disebut tail. Ada berbagai jenis daftar tertaut - daftar tertaut tunggal, daftar tertaut ganda, dan daftar tertaut melingkar. Demi artikel ini, saya akan berfokus pada daftar tertaut tunggal.
Mengakses elemen di seluruh larik lebih mudah, tetapi itu membutuhkan biaya.
Mengapa Menggunakan Daftar Tertaut Selama Array?
Anda mungkin bertanya-tanya - tetapi mengapa menggunakan ini jika saya dapat mengakses elemen secara langsung dengan array? Ini benar! Mengakses elemen di seluruh larik lebih mudah, tetapi itu membutuhkan biaya.
Array diindeks - jadi kapan pun Anda perlu menghapus elemen dari awal atau tengah, semua indeks berikut perlu digeser. Ini juga benar jika Anda perlu menyisipkan elemen - semua elemen berikut harus diindeks ulang. Saat menyisipkan atau menghapus elemen dari daftar tertaut, Anda tidak perlu mengindeks ulang - yang perlu diperhatikan hanyalah simpul yang dituju .
Menerapkan Daftar Tertaut Tunggal
Ada berbagai jenis daftar tertaut - tunggal, ganda, dan melingkar. Daftar tertaut tunggal adalah jenis daftar tertaut di mana setiap node memiliki nilai dan penunjuk ke node berikutnya (null jika itu node ekor). Di sisi lain, daftar tertaut ganda memiliki penunjuk tambahan ke simpul sebelumnya. Daftar terkait melingkar adalah tempat simpul ekor menunjuk kembali ke simpul kepala.
Catatan: Jika Anda seorang pelajar visual, VisuAlgo adalah tempat yang tepat untuk bermain-main dan melihat struktur data mengalami perubahan.
Jika Anda ingin melewatkan kode lengkapnya: periksa inti GitHub ini .
Membuat Node
Mari kita mulai dengan membuat node untuk digunakan. Ini akan memiliki nilai dan penunjuk berikutnya, yang akan menunjukkan tetangga berikutnya.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Kita akan mulai dengan membuat kelas yang disebut SinglyLinkedList dan memberinya dasar untuk kepala, ekor, dan panjang daftar.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Untuk menambahkan node di akhir, kami akan memeriksa apakah ada head yang sudah dideklarasikan di daftar. Jika tidak, atur head dan tail menjadi node yang baru dibuat. Jika sudah ada properti head, set properti next di tail ke simpul baru, dan properti tail menjadi simpul baru. Kami akan menambah panjang 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Untuk menghapus node di bagian akhir, pertama-tama kita harus memeriksa apakah ada node dalam daftar. Jika ada node, maka kita harus melakukan loop melalui list sampai kita mencapai tail. Kita akan menyetel properti berikutnya dari simpul kedua hingga terakhir menjadi nol, mengatur properti ekor ke simpul itu, mengurangi panjangnya 1, dan mengembalikan nilai simpul yang dihapus.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Untuk menghapus node dari awal, kami memeriksa apakah ada node dalam daftar. Kita akan menyimpan properti head saat ini dalam sebuah variabel, dan mengatur head menjadi simpul berikutnya dari head saat ini. Kurangi panjangnya dengan 1 dan kembalikan nilai node yang dihapus.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Untuk menambahkan node ke awal, pertama kita membuat node dan memeriksa apakah ada properti head pada daftar. Jika demikian, setel properti berikutnya dari simpul yang baru dibuat ke kepala saat ini, setel kepala ke simpul baru, dan tambahkan panjangnya.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Untuk mengakses sebuah node berdasarkan posisinya dalam daftar, pertama-tama kita akan memeriksa apakah indeksnya adalah indeks yang valid. Setelah itu, kita akan mengulang daftar, sambil mempertahankan variabel penghitung. Setelah variabel counter cocok dengan indeks, kami akan mengembalikan node yang ditemukan
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Untuk mengubah node berdasarkan posisinya, pertama-tama kita temukan node tersebut, menggunakan metode get dan setel nilainya ke nilai baru.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Untuk memasukkan node, pertama kita periksa indeksnya. Jika sama dengan 0, kami menggunakan metode unshift kami. Jika sama dengan panjangnya, kami mendorongnya ke dalam daftar. Jika tidak, kita akan mendapatkan node before dengan menggunakan metode get pada satu node kurang dari indeks. Pada dasarnya, kita perlu melacak node sebelum dan sesudah indeks yang dipilih untuk memastikan pointer kita diarahkan ke node yang benar.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Untuk menghapus node berdasarkan posisi, kami akan menggunakan metode get kami lagi, dan menggunakan prinsip yang sama yang kami gunakan untuk memasukkan node. Dengan melacak node sebelum indeks yang dipilih, kita dapat mengarahkan pointer kita.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Kekuatan Daftar Tertaut
Manfaat menggunakan daftar tertaut adalah kemampuan untuk memasukkan dan menghapus elemen dengan cepat. Karena daftar tertaut tidak diindeks, memasukkan elemen relatif cepat dan mudah.
Menambahkan ke akhir daftar tertaut hanya membutuhkan ekor lama untuk menunjuk ke simpul baru, dan properti tail harus disetel ke simpul baru. Menambahkan ke awal daftar tertaut adalah premis yang sama, tetapi simpul baru menunjuk ke kepala lama, dan properti kepala disetel ke simpul baru. Tindakan yang pada dasarnya sama, jadi penyisipannya adalah O (1).
Catatan: Memasukkan di tengah daftar tertaut, membutuhkan pencarian untuk menemukan node Anda (O (N)) dan kemudian memasukkan node (O (1)).
Menghapus node dari daftar tertaut bisa mudah… tetapi juga tidak. Ini tergantung dimana. Menghapus simpul dari awal daftar itu sederhana - simpul kedua menjadi kepala baru, dan kami mengatur penunjuk berikutnya dari kepala lama ke nol. Menghapus dari akhir lebih rumit karena ini membutuhkan seluruh daftar dan berhenti di simpul kedua hingga terakhir. Kasus terburuk O (N), dan kasus terbaik O (1).
Kelemahan dari Linked List
Kelemahan daftar tertaut disebabkan oleh kurangnya pengindeksan ulang. Karena Anda tidak dapat mengakses elemen secara langsung, pencarian dan pengaksesan elemen menjadi lebih sulit.
Mencari & Mengakses node dalam daftar tertaut membutuhkan mulai dari awal daftar dan mengikuti jejak runut tautan ke bawah daftar. Jika kita mencari simpul di akhir daftar, kita harus melalui seluruh daftar tertaut, secara efektif membuat kompleksitas waktu O (N). Seiring bertambahnya daftar, jumlah operasi bertambah. Dibandingkan dengan sebuah array yang memiliki akses acak - dibutuhkan waktu yang konstan untuk mengakses sebuah elemen.
Itu dia!
Daftar tertaut adalah alternatif yang bagus untuk larik saat penyisipan dan penghapusan di awal adalah tindakan utama. Array diindeks, sedangkan daftar tertaut tidak. Daftar tertaut juga merupakan struktur data dasar yang menyusun tumpukan dan antrian, yang akan saya bahas di artikel selanjutnya. Jika Anda berhasil sampai di sini, pujian untuk Anda dan saya harap Anda belajar sedikit bersama dengan perjalanan pemrograman Anda!
