Doubly Linked List
Struktur Data - Pertemuan 13
"Doubly Linked List"
Pengertian double linked list
Double
linked list adalah linked list biasa, hanya saja setiap elemen list -nya memuat
dua macam pointer, yang satu menunjuk ke elemen sebelumnya dan yang lainya
menunjuk ke elemen sesudahnya atau selanjutnya. Double
Linked List adalah linked list dengan node yang memiliki data dan dua buah
reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum
dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked
list yaitu circular dan non-circular layaknya pada single linked list.
Ilustrasi inisialisasi double linked list :
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
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).
Daftar Pustaka
1. Esakov, Jeffrey, Tom Weiss, Data Structures An Advanced Approach Using C, Prentice-Hall, Inc. 1989
2. Hariyanto, Bambang, Struktur Data, Informatika Bandung, Pebruari 2000
3. Kadir, Abdul, Pemrograman Dasar Turbo C, Andi Offset, Yogyakarta, 1991
4. Kruse, Robert L. Data Structures & Program Design, Prentice-Hall, Inc. 1987
5. Standish, Thomas A. Data Structures, Algorithms & Software Principles In C, Addison Wesley, 1995
Komentar
Posting Komentar