Struktur Data dan Algoritma - Daftar Tertaut
Daftar tertaut adalah urutan struktur data, yang dihubungkan bersama melalui tautan.
Linked List adalah urutan link yang berisi item. Setiap tautan berisi koneksi ke tautan lain. Daftar tertaut adalah struktur data yang paling banyak digunakan kedua setelah larik. Berikut adalah istilah-istilah penting untuk memahami konsep Linked List.
Link - Setiap tautan dari daftar tertaut dapat menyimpan data yang disebut elemen.
Next - Setiap tautan dari daftar tertaut berisi tautan ke tautan berikutnya yang disebut Berikutnya.
LinkedList - Sebuah Daftar Tertaut berisi tautan koneksi ke tautan pertama yang disebut Pertama.
Representasi Daftar Tertaut
Daftar tertaut dapat divisualisasikan sebagai rangkaian node, di mana setiap node mengarah ke node berikutnya.
Sesuai ilustrasi di atas, berikut adalah poin-poin penting yang harus diperhatikan.
Daftar Tertaut berisi elemen tautan yang disebut pertama.
Setiap tautan membawa bidang data dan bidang tautan disebut berikutnya.
Setiap tautan ditautkan dengan tautan berikutnya menggunakan tautan berikutnya.
Tautan terakhir membawa tautan sebagai null untuk menandai akhir dari daftar.
Jenis Daftar Tertaut
Berikut adalah berbagai jenis daftar tertaut.
Simple Linked List - Navigasi item hanya untuk maju.
Doubly Linked List - Item dapat dinavigasi maju dan mundur.
Circular Linked List - Item terakhir berisi tautan dari elemen pertama sebagai elemen berikutnya dan elemen pertama memiliki tautan ke elemen terakhir seperti sebelumnya.
Operasi Dasar
Berikut adalah operasi dasar yang didukung oleh daftar.
Insertion - Menambahkan elemen di awal daftar.
Deletion - Menghapus elemen di awal daftar.
Display - Menampilkan daftar lengkap.
Search - Mencari elemen menggunakan kunci yang diberikan.
Delete - Menghapus elemen menggunakan kunci yang diberikan.
Operasi Penyisipan
Menambahkan node baru dalam daftar tertaut adalah aktivitas lebih dari satu langkah. Kita akan mempelajari ini dengan diagram di sini. Pertama, buat node menggunakan struktur yang sama dan temukan lokasi tempat node tersebut harus disisipkan.
Bayangkan kita memasukkan sebuah node B (NewNode), di antara A (LeftNode) dan C(RightNode). Kemudian titik B. di sebelah C -
NewNode.next −> RightNode;Ini akan terlihat seperti ini -
Sekarang, simpul berikutnya di kiri harus mengarah ke simpul baru.
LeftNode.next −> NewNode;
Ini akan menempatkan simpul baru di tengah keduanya. Daftar baru akan terlihat seperti ini -
Langkah serupa harus diambil jika node disisipkan di awal daftar. Saat memasukkannya di akhir, simpul terakhir kedua dari daftar harus mengarah ke simpul baru dan simpul baru akan mengarah ke NULL.
Operasi Penghapusan
Penghapusan juga merupakan proses lebih dari satu langkah. Kita akan belajar dengan representasi gambar. Pertama, temukan node target yang akan dihapus, dengan menggunakan algoritma pencarian.
Node kiri (sebelumnya) dari node target sekarang harus mengarah ke node berikutnya dari node target -
LeftNode.next −> TargetNode.next;
Ini akan menghapus link yang mengarah ke node target. Sekarang, dengan menggunakan kode berikut, kami akan menghapus apa yang ditunjuk oleh node target.
TargetNode.next −> NULL;
Kita perlu menggunakan node yang dihapus. Kita dapat menyimpannya di memori jika tidak kita dapat membatalkan alokasi memori dan menghapus node target sepenuhnya.
Operasi Terbalik
Operasi ini menyeluruh. Kita perlu membuat simpul terakhir untuk diarahkan oleh simpul kepala dan membalikkan seluruh daftar tertaut.
Pertama, kami menelusuri akhir daftar. Ini harus mengarah ke NULL. Sekarang, kita akan membuatnya menunjuk ke simpul sebelumnya -
Kita harus memastikan bahwa simpul terakhir bukanlah simpul terakhir. Jadi kita akan memiliki beberapa node temp, yang terlihat seperti node kepala yang menunjuk ke node terakhir. Sekarang, kita akan membuat semua node sisi kiri mengarah ke node sebelumnya satu per satu.
Kecuali node (node pertama) yang ditunjukkan oleh node kepala, semua node harus mengarah ke pendahulunya, menjadikannya penerus baru. Node pertama akan mengarah ke NULL.
Kita akan membuat simpul kepala mengarah ke simpul pertama yang baru dengan menggunakan simpul temp.
Daftar terkait sekarang dibalik. Untuk melihat implementasi linked list dalam bahasa pemrograman C, silakan klik di sini .