PERTEMUAN 13 DOUBLY LINKED LIST

Doubly Linked List

Pengertian Double Linked List. Salah satu kelemahan dari Singly Linked List adalah masing-masing simpul hanya memiliki satu pointer saja sehingga hanya dapat bergerak satu arah saja, yaitu: maju atau ke kanan. Untuk mengatasi kelemahan ini maka dibuat dengan Doubly Linked List.

Doubly Linked List merupakan Linked List dimana setiap simpul dibagi menjadi tiga bagian yaitu bagian isi, bagian pointer kiri, dan bagian pointer kanan. Bagian isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian pointer kiri merupakan bagian yang berisi alamat dari simpul sebelumnya dan bagian pointer kanan merupakan bagian yang berisi alamat dari simpul berikutnya. Gambar 1. merupakan simpul untuk Doubly Linked List.

Gambar 1. Simpul pada Doubly Linked List

Gambar 2. Doubly Linked List DL dengan 4 Simpul

Ada dua macam double linked list, yaitu :

a. Double Linked List Cilcular

Circular artinya pointer next dan prev-nya menunjuk ke dirinya sendiri. Jadi, double linked list circular (DLLC) adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta 1 field yang berisi data dengan pointer next dan prev nya menunjuk ke dirinya sendiri secara circular.

Gambar double linked list cilcular :

Deklarasi node :

class Node{int data;

Node next;

Node prev;

}

b. Double Linked List Non Cilcular

Non circular artinya pointer preview dan next-nya akan menunjuk padanull. Jadi double linked list non circular (DLLNC) adalah double linked linked list yang memiliki 2 buah pointer yaitu pointer next dan prev. Pointer next menunjuk pada node setelahnya dan pointer preview menunjuk pada node sebelumnya.

Gambar double linked list non cilcular :

Deklarasi node :

class Node {int data;

Node next;

Node prev;

}

Pada Operasi Double Linked List terdapat 6 Operasi, yaitu :

• Insert Kiri
• Insert Kanan
• Insert Tengah
• Delete Kiri
• Delete Kanan
• Delete Tengah.

1. Insert Simpul Depan (Kiri)

Penyisipan simpul baru selalu berada di posisi paling depan. Penyisipan simpul depan dapat dilakukan dengan langkah berikut:

• Ciptakan simpul baru.
• Jika Linked List (DL) belum ada maka simpul baru menjadi Linked List (DL=Baru).
• Tetapi jika Linked List (DL) sudah ada maka penyisipan dilakukan dengan:

·         Pointer kanan dari baru menunjuk DL (Baru->Kanan = DL).

·         Pointer kiri dari DL menunjuk baru (DL->Kiri = Baru).

·         Pointer DL dipindahkan menunjuk simpul baru (DL = Baru).

2. Insert Simpul Belakang (Kanan)

Penyisipan simpul baru selalu berada di posisi paling belakang. Penyisipan simpul belakang dapat dilakukan dengan dua cara, yaitu dengan menggunakan pointer bantu dan tanpa pointer bantu. Penyisipan simpul pada Doubly Linked List tidak mengharuskan menggunakan pointer bantu karena walaupun menggerakkan DL tidak mengakibatkan adanya simpul yang hilang. Hal ini dapat terjadi karena semua simpul saling menunjuk atau saling berhubungan.

Penyisipan dengan pointer bantu

• Ciptakan simpul baru.
• Jika Linked List (DL) belum ada maka simpul baru menjadi Linked List (DL=Baru).
• Tetapi jika Linked Lis (DL) sudah ada maka penyisipan dilakukan dengan:

·         Buat pointer bantu yang dapat digerakkan (Bantu=DL).

·         Gerakkan pointer bantu hingga simpul terakhir (while(Bantu->Kanan != NULL) Bantu=Bantu->Kanan).

·         Pointer kanan simpul bantu menunjuk baru (Bantu->Kanan = Baru).

·         Pointer kiri baru menunjuk bantu (Baru->Kiri = Bantu).

3. Insert Simpul Tengah

Menyisipkan suatu simpul Baru diantara dua simpul. Penyisipan simpul tengah hanya dapat dilakukan jika linked list (DL) tidak kosong. Misalkan kita mempunyai dobly linked list (DL) dengan 3 simpul yang masing-masing berisi informasi C, B dan A serta simpul Baru yang akan disisipkan ditengah yang berisi informasi D (karakter). Simpul Baru akan disisipkan setelah simpul yang berisi informasi B (elemen).

Penyisipan dengan pointer bantu

• Ciptakan simpul baru.
• Buat pointer bantu yang dapat digerakkan (Bantu=DL).
• Gerakkan pointer bantu hingga simpl yang berisi informasi karakter.
• Kanan simpul baru menunjuk kanan bantu (Baru->Kanan = Bantu->Kanan).
• Pointer kiri dari kanan bantu menunjuk baru (Bantu->Kanan->Kiri = Baru).
• Pointer kanan bantu menunjuk baru (bantu->Kanan = Baru).
• Pointer kiri baru menunjuk bantu (Baru->Kiri = Bantu).

4. Delete Simpul Depan (Kiri)

Simpul yang dihapus selalu yang berada pada posisi depan. Misalkan kita memiliki Linked List DL, akan dilakukan penghapusan simpul depan yaitu simpul yang berisi informasi C. Langkah-langkah penghapusan simpul depan adalah sebagai berikut:

• Simpul depan ditunjuk oleh pointer hapus (Hapus = DL).
• Pointer DL digerakkan satu simpul ke kanan (DL = DL->Kanan).
• Putuskan pointer Kiri DL dari hapus (DL->Kiri = NULL).
• Putuskan pointer kanan hapus dari Linked List DL (Hapus->Kanan=NULL).

5. Delete Simpul Belakang (Kanan)

Simpul yang dihapus selalu yang berada pada posisi belakang. Misalkan kita memiliki Linked List DL terdiri dari 4 simpul dengan masing-masing berisi informasi C, B, D, dan A, akan dilakukan penghapusan simpul belakang yaitu simpul yang berisi informasi A. Dalam menghapus simpul belakang, kita dapat lakukan dengan dua cara, yaitu dengan menggunakan pointer atau tanpa menggunakan pointer bantu. Langkah-langkah penghapusan simpul belakang dengan dan tanpa bantu dapat dilakukan seperti berikut.

Penghapusan Simpul Belakang dengan Pointer Bantu

• Buatlah pointer bantu yang menunjuk simpul pertama yang ditunjuk oleh pointer DL (Bantu = DL).
• Gerakkan pointer bantu hingga satu simpul sebelum simpul belakang (while(Bantu->Kanan->Kanan != NULL) Bantu = Bantu->Kanan).
• Simpul belakang yang ditunjuk pointer kanan bantuk ditunjuk juga oleh pointer hapus(Hapus = Bantu->Kanan).
• Putuskan pointer kanan bantu dari simpul yang ditunjuk pointer hapus (Bantu->Kanan=NULL).
• Putuskan pointer kiri hapus dari Linked List (Hapus->Kiri = NULL).

6. Delete Simpul Tengah

Berbeda dengan penghapusan simpul depan dan penghapusan simpul belakang, simpul yang akan dihapus adalah pasti yang ada di depan atau yang ada di belaakng dan hanya ada masing-masing satu. Tetapi karena simpul tengah mungkin lebih dari satu simpul maka harus diketahui simpul yang mana yang akan dihapus. Misalkan kita memiliki Linked List DL terdiri dari 4 simpul dengan masing-masing berisi informasi C, B, D, dan A, akan dilakukan penghapusan simpul yang ada di posisi tengah (simpul yang berisi informasi B atau D) yaitu simpul yang berisi informasi D (elemen). Dalam menghapus simpul belakang, kita dapat lakukan dengan dua cara juga, yaitu dengan menggunakan pointer bantu atau tanpa menggunakan pointer bantu. Langkah-langkah penghapusan simpul belakang dengan dan tanpa bantu dapat dilakukan seperti berikut.

Penghapusan Simpul Tengah dengan Pointer Bantu

• Buatlah pointer bantu yang menunjuk simpul pertama yang ditunjuk DL (Bantu = DL).
• Gerakkan pointer bantu satu simpul sebelum yang akan dihapus yaitu simpul yang berisi informasi “elemen” (while(Bantu->Kanan->Isi != “elemen”) Bantu=Bantu->Kanan).
• Simpul yang akan dihapus yaitu simpul yang ditunjuk pointer kanan bantu ditunjuk oleh pointer hapus (Hapus = Bantu->Kanan).
• Sambungkan pointer kanan bantu terhadap simpul yang ditunjuk pointer kanan hapus (Bantu->Kanan = Hapus->Kanan atau juga Bantu->Kanan = Bantu->Kanan->Kanan).
• Sambungkan pointer kiri dari simpul setelah hapus terhadap bantu (Bantu->Kanan->Kanan->Kiri = Bantu atau Hapus->Kanan->Kiri = Bantu).
• Putuskan pointer kanan hapus dari Linked List (Hapus->Kanan = NULL).
• Putuskan pointer kiri hapus dari Linked List (Hapus->Kiri = NULL).