Tugas Latihan 17

Circular Doubly Linked List

Circular Doubly Linked List adalah sederetan elemen yang saling berhubungan satu dengan yang lain, dimana pointer kiri simpul pertama menunjuk simpul terakhir dan pointer kanan simpul terakhi menunjuk simpul pertama. Semua simpul berhak menjadi simpul pertama. Jika suatu simpul dibuat menjadi simpul depan maka simpul yang ada di sebelah kiri merupakan simpul belakang.

Pendeklarasian simpul untuk Circular Doubly Linked List sama dengan pendeklarasian pada Doubly Linked List. Operasi yang ada pada Doubly Linked List juga berlaku pada Circular Doubly Linked List, hanya saja pada Circular tidak mengandung NULL, perhatikan gambar 8.

Gambar 8. Circular Doubly Linked List dengan 3 Simpul

 

2.1. Operasi pada Circular Doubly Linked List

Operasi pada Circular Doubly Linked List juga dapat dilakukan penyisipan dan penghapusan simpul.

a. Operasi Penyisipan Simpul

Operasi penyisipan simpul ke suatu Linked List juga ada tiga, yaitu penyisipan simpul di depan, penyisipan simpul di belakang, dan penyisipan simpul di tengah. Karena semua simpul berhak menjadi simpul depan maka pointer penunjuk Linked List (CDL) dapat digerakkan ke seluruh simpul pada Linked List. Tetapi supaya kita tetap mempertahankan simpul yang ditunjuk CDL merupakan simpul depan maka kita dapat menggunakan suatu pointer bantu. Pointer bantu dapat digerakkan ke semua simpul pada Linked List. Di sini, simpul yang ditunjuk oleh CDL pertama sekali akan tetap dipertahankan sebagai simpul pertama atau simpul depan.

1. Penyisipan simpul depan

Langkah-langkah penyisipan simpul depan dapat dilakukan seperti berikut ini:

• Jika Linked List belum ada (NULL) maka simpul baru menjadi awal Linked List (CDL = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan:
  • Pointer kanan simpul baru menunjuk CDL (Baru->Kanan = CDL).
  • Pointer kiri simpul baru menunjuk yang ditunjuk pointer kiri CDL (Baru->Kiri = CDL->Kiri).
  • Pointer kanan dari simpul yang ditunjuk pointer kiri CDL menunjuk simpul baru (CDL->Kiri->Kanan = Baru).
  • Pointer kiri CDL menunjuk simpul baru (CDL->Kiri = Baru).
  • Pointer CDL menunjuk simpul baru (CDL = Baru).

Misalkan kita memiliki Linked List yang terdiri dari tiga simpul dengan berisi masing-masing informasi A, B, dan C. Juga memiliki suatu simpul baru yang berisi informasi D. Simpul baru yang akan disisipkan di bagian depan Linked List. Skema penyisipan simpul depan dapat dilihat pada Gambar 9.

Gambar 9. Penyisipan Simpul Depan pada Circular Doubly Linked List

Fungsi penyisipan simpul depan dengan mengikuti langkah-langkah dan gambar 9 di atas dapat dilihat berikut ini.

1. void Sisip_Depan(simpul &CDL, char elemen)
2. {
3. simpul baru;
4. baru = (simpul) malloc(sizeof(simpul));
5. baru->Isi = elemen;
6. baru->kanan = baru;
7. baru->kiri = baru;
8. if(CDL == NULL) CDL=baru;
9. else
10. {
11. baru->kanan = CDL;
12. baru->kiri = CDL->kiri;
13. CDL->kiri->kanan = baru;
14. CDL->kiri = baru;
15. }
16. }

2. Penyisipan simpul belakang

Langkah-langkah penyisipan simpul baru pada Linked List di posisi belakang dapat dilakukan seperti berikut ini:

• Jika Linked List belum ada (NULL) maka simpul baru menjadi awal Linked List (CDL = Baru).
• Jika Linked List sudah ada maka penyisipan dilakukan dengan:
  • Pointer kanan simpul baru menunjuk CDL (Baru->Kanan =CDL).
  • Pointer kiri simpul baru menunjuk yang ditunjuk pointer kiri CDL (Baru->Kiri = CDL->Kiri).
  • Pointer kanan dari simpul yang ditunjuk pointer Kiri CDL menunjuk simpul baru (CDL->Kiri->Kanan = Baru).
  • Pointer kiri CDL menunjuk simpul baru (CDL->Kiri = Baru).

Misalkan kita memiliki Linked List yang terdiri dari tiga simpul dengan berisi masing-masing informasi A, B, dan C, juga memiliki suatu simpul baru yang berisi informasi D. Simpul Baru akan disisipkan di bagian belakang Linked List. Skema penyisipan simpul belakang dapat dilihat pada Gambar 9.