DOUBLY LINKED LIST

Bekerja dengan data yang besar tidak dapat dihindari lagi, dan tidak jarang pula, data besar tersebut memiliki hubungan yang erat. Sebagai contoh, ketika akan bekerja dengan file yang menyimpan sangat banyak record, di mana setiap record juga memiliki banyak field. Tidak hanya sekadar menampilkan setiap record-nya, melainkan harus pula menambahkan record, menghapus beberapa record sesuai keinginan pengguna, sampai mengurutkan record. 

Kondisi tersebut memungkinkan dimilikinya satu rantai data yang panjang dan saling berhubungan. Rantai data tersebut harus mampu menampung semua data yang dimiliki. Penggunaan array saja jelas tidak bisa, karena data berupa barisan data heterogen. Oleh karena itu, perlu menggunakan union ataupun struct. Namun, juga tidak dapat semena-mena menggunakan array pada struct dalam jumlah besar. Karena lokasi penampungan memori untuk alokasi konvensional tidak akan mempu mencukupi kebutuhan memori. dimungkinkan melakukan alokasi dan dealokasi beberapa kali di dalam program untuk mengoptimasi penggunaan memori. Solusi yang lebih baik adalah menggunakan linked list, baik singly (tunggal) linked list ataupun doubly (ganda) linked list. 

Apabila dalam singly linked list setiap node memiliki satu pointer yang menunjuk ke node sebelahnya, maka doubly linked list lebih serakah dengan membuat setiap node memiliki dua buah pointer: ke sebelah kiri (sebelum) dan ke sebelah kanan (setelah). Gambar 1 memperlihatkan sebuah node dari doubly linked list. Bertambah lagi komponen yang akan digunakan. Apabila dalam singly linked list hanya memiliki head, curr dan node, maka untuk doubly linked list, kita menambahkan satu penunjuk yang berfungsi sebagai akhir dari list: tail. Bagian kiri dari head akan menunjuk ke NULL. Demikian pula dengan bagian kanan dari tail. Setiap node saling terhubung dengan pointer kanan dan kiri.

Hubungan antar node pada doubly linked list.

Saling berpegangan tangan, kemudian membuat barisan. Setiap pemain memegang teman di sebelah kirinya dengan tangan kiri, dan memegang teman di sebelah kanannya dengan tangan kanan. Bagaimana dengan pemain-pemain paling ujung yang kesepian? Pemain paling kiri akan memegang udara dengan tangan kirinya, dan pemain paling kanan akan memegang udara dengan tangan kanannya.

ABSTRAKSI TIPE DATA DOUBLY LINKED LIST

Dimulai dengan pembuatan struct tnode. abstraksi tipe data singly linked list kini ditmbah pointer prev selain next.

Untuk mendeklarasikan beberapa node yang akan digunakan sebagai head, tail, node aktif (curr) dan node sementara (node).

Sama seperti pada pembuatan singly linked list, dalam pembuatan doubly linked list ini, akan membuat sebuah perulangan sebanyak 5 kali untuk mengisikan nilai 0 sampai 4 ke dalam field x untuk masing-masing node

Secara umum, kode yang dibuat hampir sama dengan pembuatan singly linked list. Hanya bedanya, pada doubly linked list, pointer kiri dan kanan dihubungkan dengan suatu node.

Pertama-tama, tentunya perlu diuji apakah head bernilai NULL yang artinya belum ada satu node pun yang tercipta. Apabila demikian, maka node yang dibuat akan menjadi head. Node aktif (curr) pun di set sesuai node yang dibuat. Dan sebagai konsekuensi dari doubly linked list, maka diatur pointer prev pada head menunjuk ke NULL. Bagaimana kalau head tidak NULL? Hal tersebut berarti telah dimiliki satu atau lebih node yang terhubungan secara double. Yang perlu dilakukan adalah membuat pointer next pada node aktif (curr) untuk menunjuk ke node yang baru saja dibuat. Dan tidak lupa, sebagai konsekuensi dari doubly linked list, juga dibuat pointer prev pada node yang baru saja dibuat untuk menunjuk kepada node aktif (curr). Setelah keduanya saling tahu kiri dan kanan masing-masing, sekarang memindahkan node aktif (curr) ke node yang baru saja dibuat.

 

Untuk menguji keberhasilan doubly linked, awal list sampai akhir list akan dicetak dengan deklarasi:

Dan karena apa yang dibentuk adalah doubly linked list, maka juga mencetak dari tail sampai head, dengan deklarasi:

Untuk membebaskan memori teralokasi, dilakukan dengan pemanggilan fungsi free(). Kode selengkapnya:

Operasi pada linked list tidak hanya pembuatan dan pencetakan. Suatu saat, Anda mungkin perlu untuk menghapus node yang terletak di tengah-tengah list. Atau bahkan Anda mungkin perlu menyelipkan node di tengah-tengah node. Sama seperti halnya permainan gandeng-menggandeng tangan tersebut, sangat mungkin apabila tiba- tiba ada pemain baru yang ingin menyelipkan dirinya di tengah-tengah barisan.