Struktur Data - Linked List

Selamat datang kembali dipembelajaran algoritma dan struktur data. Dua elemen dari dasar struktur data sudah kita bahas, Stack dan Queue, dan kali ini kita akan bahas tentang linked list (list tertaut). Linked list, baik itu tautannya, bisa dikatakan sebagai suatu elemen yang memiliki beberapa pengertian tentang elemen apa yang berikutnya atau penjelasan elemen terkait karena ia terhubung dengannya. Dalam struktur data, ini merupakan tempat objek disusun dalam urutan linear. Tidak seperti array, bagaimanapun, di mana urutan linear ditentukan oleh indeks array, urutan dalam linked list ditentukan oleh pointer di setiap objek. Linked list secara sederhana, ,merupakan representasi fleksibel untuk set dinamis, mendukung (meskipun tidak harus efisien) Operasi pada set dinamis

Tidak ada dalam satu elemen dari array yang menginformasikan inilah elemen penting selanjutnya. Anda tahu apa elemen selanjutnya adalah apa yang ter-indeks selanjutnya. Disitu anda akan mendapatkan lebih banyak informasi yang dibutuhkan karena Anda sudah tahu di mana elemen berikutnya yang anda butuh informasi. Menambahkan dan menghapus elemen dari linked list itu sangat mudah jika memang anda dapat benar-benar hanya mengeluarkan elemen atau menambahkannya.

Dalam bahasa pemrograman tingkat yang lebih tinggi sering tidak ada perbedaan antara linked list dan array (akan kita bahas nantinya). Hanya ada daftar yang memiliki sifat keduanya. Namun pertanyaan tentang dua struktur data ini cukup umum dalam wawancara, jadi penting untuk mengetahui perbedaannya. Sekali lagi, perbedaan utama adalah setiap elemen menyimpan informasi yang berbeda. Dalam kedua kasus, satu elemen akan menyimpan nilai atau informasi yang sebenarnya. Jadi jika Anda memiliki array atau nomor dari linked list, nilainya akan menjadi satu nomor.

Dalam linked list, kita menyimpan referensi ke elemen berikutnya dalam list. Dalam banyak bahasa, ini akan terlihat seperti menugaskan unsur berikutnya yang sebenarnya sebagai properti dari elemen ini. Seperti ditunjukkan pada Gambar dibawah ini, setiap elemen dari double linked list L adalah objek dengan key atribut dan dua atribut pointer lainnya: next dan prev. Objek mungkin juga mengandung data satelit lainnya. Diberikan sebuah elemen x dalam list, x.next menunjuk pada penerusnya dalam daftar tertaut, dan x.prev menunjuk ke pendahulunya. Jika x.prev = NIL, elemen x tidak memiliki pendahulunya dan karena itu merupakan elemen pertama, atau head, dari list. Jika x.next = NIL, elemen x tidak memiliki penerus dan karena itu merupakan elemen terakhir, atau tail, dari list. Unsur L.head menunjuk ke elemen pertama dari list. Jika L.head = NIL, daftarnya kosong.

box1

Double linked list L yang mewakili set dinamis {1; 4; 9; 16}. Setiap elemen dalam daftar adalah objek dengan atribut untuk kunci dan pointer (ditunjukkan oleh panah) ke objek berikutnya dan sebelumnya. Atribut tail yang berikutnya dan atribut prev dari head adalah NIL, ditunjukkan oleh garis miring diagonal. Atribut L.head menunjuk ke head.

box2

Mengikuti eksekusi LIST-INSERT (L, x), di mana x.key = 25, linked list memiliki objek baru dengan kunci 25 sebagai head baru. Objek baru ini menunjuk ke head lama dengan kunci 9.

box3

Hasil dari panggilan berikutnya LIST-DELETE (L, x) di mana x menunjuk ke objek dengan key 4.

List mungkin memiliki salah satu dari beberapa bentuk. Ini mungkin terhubung satu sama atau ditautkan dua kali, itu mungkin diurutkan atau tidak, dan mungkin melingkar atau tidak. Jika list terhubung secara tunggal, kita menghilangkan penunjuk prev di setiap elemen. Jika list diurutkan, urutan linier dari list sesuai dengan urutan linear dari key yang disimpan dalam elemen daftar; elemen minimum adalah head dari list, dan elemen maksimum adalah tail. Jika list tersebut disortir, elemen-elemen dapat muncul dalam urutan apa pun. Dalam list melingkar, penunjuk prev dari head list menunjuk ke tail, dan pointer berikutnya dari tail list menunjuk ke head. Kita bisa memikirkan list melingkar sebagai ring elemen. Di sisa bagian ini, kita menganggap bahwa list yang kita kerjakan tidak disortir dan ditautkan secara ganda.

Yang menyenangkan dari sistem linked list ini adalah cukup mudah untuk memasukkan dan menghapus elemen. Menambahkan elemen akan terlihat seperti gambar diatas, kita benar-benar hanya perlu mengubah referensi berikutnya untuk menunjuk ke objek baru dan selesai. Ada trik cepat yang perlu Anda ingat meskipun jika Anda menghapus referensi berikutnya dan menggantinya dengan objek baru.

Anda akan kehilangan referensi ke objek jika Anda harus selalu menugaskan penunjuk berikutnya untuk elemen yang satu sebelum Anda menetapkan penunjuk berikutnya untuk elemen lainya, jadi Anda tidak kehilangan referensi Anda untuk yang ini di sini. Perhatikan bahwa penyisipan membutuhkan waktu yang konstan dalam kasus ini karena Anda hanya menggeser pointer dan tidak melakukan iterasi atas setiap elemen dalam list.

Sekarang untuk Mencari list yang ditautkan, Prosedur LIST-SEARCH (L, k) menemukan elemen pertama dengan kunci k dalam daftar L dengan pencarian linier sederhana, mengembalikan pointer ke elemen ini. Jika tidak ada objek dengan k kunci muncul dalam list, maka prosedur mengembalikan NIL. Untuk linked list pada gambar (a), daftar LIST-SEARCH (L. 4) mengembalikan pointer ke elemen ketiga, dan daftar LIST-SEARCH (L.7) mengembalikan NIL.

LIST-SEARCH(L,k)
x = L.head
while x = NIL and x.key = k
    x = x.next
return x

Untuk mencari list n objek, prosedur LIST-SEARCH membutuhkan O(n) / waktu dalam kasus terburuk, karena mungkin harus mencari seluruh daftar.

Memasukkan ke list linked, Dengan elemen x atribut key yang telah ditetapkan, prosedur LIST-INSERT “splices” x ke bagian depan list linked, seperti yang ditunjukkan pada Gambar kedua.

LIST-INSERT(L,k)
x.next = L.head
if L.head = NIL
   L.head.prev = x
L.head = x
x.prev = NIL

(Ingat bahwa notasi atribut kita dapat menurun, sehingga L.head.prev menunjukkan atribut prev objek yang menunjuk L.head.) Running Time untuk LISTINSERT pada daftar n elemen adalah O(1)

Menghapus dari linked list., Prosedur LIST-DELETE menghapus elemen x dari lisked list L. Ini harus diberi penunjuk ke x, dan kemudian “splices” x keluar dari list dengan memperbarui pointer. Jika kami ingin menghapus elemen dengan key yang diberikan, pertama-tama kita harus memanggil LIST-SEARCH untuk mengambil penunjuk ke elemen.

LIST-DELETE(L,k)
if x.prev = NIL
   x.prev.next = x.next
else L.head = x.next
if x.next = NIL
   x.next.prev = x.prev

Gambar ketiga menunjukkan bagaimana suatu elemen dihapus dari linked list. LIST-DELETE berjalan di O(1) / waktu, tetapi jika kita ingin menghapus elemen dengan kunci tertentu, O( n)/ waktu diperlukan dalam kasus terburuk karena kita harus terlebih dahulu memanggil LIST-CARI untuk menemukan elemen.

Kode untuk LIST-DELETE akan lebih sederhana jika kita dapat mengabaikan kondisi batas di head dan tail list:

LIST-DELETE’(L,x)
x.prev.next = x.next
x.next.prev = x.prev

Ini yang disebut sentinel. Sentinel adalah objek tiruan yang memungkinkan kita menyederhanakan kondisi batas. Sebagai contoh, anggaplah bahwa kita menyediakan daftar L sebuah objek L.nil yang mewakili NIL tetapi memiliki semua atribut dari objek lain dalam daftar. Di mana pun kita memiliki referensi ke NIL dalam kode daftar, kami menggantinya dengan referensi ke sentinel L.nil.