Daftar Isi
1. Circular Singly Linked List
1.1. Penyisipan simpul
1.2. Penghapusan Simpul
2. Circular Doubly Linked List
2.1. Operasi pada Circular Doubly Linked List
1. Circular Singly Linked List
Hampir sama dengan Singly Linked List, hanya saja simpul terakhir akan dihubungkan ke simpul pertama sehingga berbentuk melingkar. Pendeklarasian dan operasi yang ada di Singly Linked List juga berlaku di Circular Singly Linked List, yang perlu dijaga adalah bahwa simpul terakhir harus selalu terhubung ke simpul pertama yang ditunjuk oleh CL seperti pada gambar 1.
Gambar 1. Circular Singly Linked List dengan 4 Simpul
Baca juga : Pengertian dan Contoh Program Pointer pada C++
1.1. Penyisipan simpul
Penyisipan simpul adalah operasi menyisipkan suatu simpul baru ke dalam suatu Linked List. Operasi penyisipan dapat dilakukan di posisi depan, posisi belakang, atau di posisi tengah.
a. Penyisipan simpul depan
Simpul yang disisipkan selalu berada di posisi depan dari Linked List [CL]. Misalkan kita memiliki suatu Linked List CL dengan empat simpul di mana masing-masing berisi informasi A, B, C, dan D, dan kita juga memiliki suatu simpul baru yang berisi informasi E yang akan disisipkan di posisi depan dari Linked List CL. Langkah-langkah penyisipan simpul baru dapat dilakukan sebagai berikut:
- Jika Linked List CL belum ada maka simpul baru menjadi awal Linked List CL [CL = Baru].
- Jika Linked List CL sudah ada maka penyisipan dilakukan:
- Pointer bantu menunjuk CL [Bantu = CL].
- Gerakkan bantu hingga ke simpul belakang [while[Bantu->Kanan != CL] Bantu = Bantu->Kanan].
- Kanan baru menunjuk CL [Baru->Kanan = CL].
- Kanan bantu menunjuk baru [Bantu->Kanan = Baru].
- Pindahkan CL ke simpul yang ditunjuk oleh baru [CL = Baru].
Skema penyisipan simpul depan dapat dilihat pada gambar 2.
Gambar 2. Penyisipan Simpul Depan pada Circular Singly Linked List
Fungsi penyisipan simpul depan dengan mengikuti langkah-langkah dan gambar 2 di atas dapat dilihat berikut ini.
void Sisip_Depan[simpul &CL, char elemen] { simpul bantu, baru; baru = [simpul] malloc[sizeof[simpul]]; baru->Isi = elemen; baru->kanan = baru; if[CL == NULL] CL=baru; else { bantu = CL; while[bantu->kanan != CL] bantu=bantu->kanan; baru->kanan = CL; bantu->kanan = baru; CL = baru; } }b. Penyisipan simpul belakang
Penyisipan belakang sebenarnya hampir sama dengan penyisipan depan. Yang membedakan hanyalah pemindahan CL ke simpul yang ditunjuk oleh baru untuk penyisipan belakang tidak ada. Walaupun dalam penyisipan depan juga tidak harus dilakukan pemindahan CL, karena dalam Circular semua simpul berhak menjadi depan.
Misalkan kita memiliki suatu Linked List CL dengan empat simpul dimana masing-masing berisi informasi A, B, C, dan D, dan kita juga memiliki suatu simpul baru yang berisi informasi E yang akan disisipkan di posisi belakang dari Linked List CL. Langkah-langkah penyisipan simpul baru dapat dilakukan sebagai berikut:
- Jika Linked List CL belum ada maka simpul baru menjadi awal Linked List CL [CL = Baru].
- Jika Linked List CL sudah ada maka penyisipan dilakukan.
- Pointer bantu menunjuk CL [Bantu = CL].
- Gerakkan bantu hingga ke simpul belakang [while[Bantu->Kanan != CL] Bantu = Bantu->Kanan].
- Pointer kanan bantu menunjuk baru [Bantu->Kanan = Baru].
- Pointer kanan baru menunjuk CL [Baru->Kanan = CL].
Skema penyisipan simpul belakang dapat dilihat pada Gambar 3.
Gambar 3. Penyisipan Simpul Belakang pada Circular Singly Linked List
Fungsi penyisipan simpul belakang dengan mengikuti langkah-langkah dan gambar 3 di atas dapat dilihat berikut ini.
void Sisip_Belakang[simpul &CL, char elemen] { simpul bantu, baru; baru = [simpul] malloc[sizeof[simpul]]; baru->Isi = elemen; baru->kanan = baru; if[CL == NULL] CL=baru; else { bantu = CL; while[bantu->kanan != CL] bantu=bantu->kanan; baru->kanan = CL; bantu->kanan = baru; } }c. Penyisipan simpul tengah
Dalam melakukan penyisipan simpul tengah, maka Linked List harus dijamin tidak boleh kosong. Penyisipan tengah dapat dilakukan pada sebelum atau setelah simpul tertentu. Yang akan dilakukan di sini adalah hanya penyisipan simpul setelah simpul tertentu. Penyisipan tengah dapat dilakukan dengan menggunakan pointer bantu atau tanpa menggunakan pointer bantu. Jika tidak menggunakan pointer bantu maka, yang harus digerakkan adalah CL dan CL dapat dikembalikan ke simpul semula ataupun tidak dikembalikan [karena prinsip semua simpul berhak menjadi simpul depan]. Yang dilakukan di sini adalah juga dengan menggunakan pointer bantu.
Misalkan kita memiliki suatu Circular Linked List yang terdiri dari 4 simpul dan masing-masing simpul berisi informasi A, B, C, dan D. Kita juga memiliki simpul baru yang berisi informasi ‘X’. Simpul baru akan disisipkan setelah simpul yang berisi informasi ‘C’. Adapun langkah-langkah penyisipan tengah tersebut adalah sebagai berikut:
- Pointer bantu menunjuk simpul depan [Bantu = CL].
- Gerakkan pointer bantu hingga simpul yang berisi informasi ‘C’ [while[Bantu->Isi !=’C’] Bantu = Bantu->Kanan].
- Pointer kanan baru menunjuk kanan bantu [Baru->Kanan = Bantu->Kanan].
- Pointer kanan bantu menunjuk baru [Bantu->Kanan = Baru].
Skema penyisipan simpul tengah dapat dilihat pada Gambar 4.
Gambar 4. Penyisipan Simpul Tengah pada Circular Singly Linked List
Fungsi penyisipan simpul tengah dengan mengikuti langkah-langkah dan gambar 4 di atas dapat dilihat berikut ini.
void Sisip_Tengah[simpul &CL, char elemen1, char elemen2] { simpul bantu, baru; baru = [simpul] malloc[sizeof[simpul]]; baru->Isi = elemen1; baru->kanan = baru; if[CL == NULL] coutkanan; bantu->kanan = baru; } }1.2. Penghapusan Simpul
Yang dimaksud dengan penghapusan simpul adalah operasi penghapusan simpul dari Linked List. Jika kita akan melakukan penghapusan simpul maka pastikan bahwa Linked List tidak boleh kosong. Penghapusan pada Circular Singly Linked List juga dapat dilakukan pada simpul yang berada di posisi depan, posisi tengah, maupun yang berada pada posisi belakang.
a. Penghapusan simpul depan
Menghapus simpul yang ada pada posisi depan. Langkah-langkah penghapusan simpul pada posisi depan adalah sebagai berikut:
- Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu [Bantu = CL].
- Gerakkan pointer bantu hingga simpul belakang [while[Bantu->Kanan != CL] Bantu = Bantu->Kanan].
- Simpul depan yang ditunjuk oleh CL juga ditunjuk oleh hapus [Hapus = CL].
- Pindahkan pointer CL ke simpul berikutnya [CL = CL->Kanan].
- Pointer kanan dari bantu menunjuk CL [Bantu->Kanan = CL].
- Pointer kanan hapus menunjuk hapus [Hapus->Kanan = Hapus].
Gambar 5. Penghapusan Simpul Depan Pada Circular Singly Linked List
Fungsi penghapusan simpul depan dengan mengikuti langkah-langkah dan gambar 5 di atas dapat dilihat berikut ini.
void Hapus_Depan[simpul &CL] { simpul bantu, Hapus; if[CL == NULL] coutkanan; Hapus = CL; CL = CL->kanan; bantu->kanan = CL; Hapus->kanan = Hapus; free[Hapus]; } }b. Penghapusan simpul belakang
Menghapus simpul yang ada pada posisi belakang. Langkah-langkah penghapusan simpul pada posisi belakang adalah sebagai berikut:
- Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu [Bantu = CL].
- Gerakkan pointer bantu hingga satu simpul sebelum simpul belakang [while[Bantu->Kanan->Kanan != CL] Bantu = Bantu->Kanan].
- Simpul belakang ditunjuk oleh pointer hapus [Hapus = Bantu->Kanan].
- Pointer kanan dari bantu menunjuk CL [Bantu->Kanan = CL].
- Pointer kanan hapus menunjuk hapus [Hapus->Kanan = Hapus].
Skema penghapusan simpul belakang dapat dilihat pada Gambar 6.
Gambar 6. Penghapusan Simpul Belakang pada Circular Singly Linked List
Fungsi penghapusan simpul belakang dengan mengikuti langkah-langkah dan gambar 6 di atas dapat dilihat berikut ini.
void Hapus_Belakang[simpul &CL] { simpul hapus, bantu; if[CL==NULL] coutkanan != CL] bantu= bantu->kanan; hapus = bantu->kanan; bantu->kanan = CL; hapus->kanan = hapus; free[hapus]; } }c. Penghapusan simpul tengah
Yang dimaksud dengan penghapusan simpul tengah adalah menghapus simpul tertentu yang ada pada posisi tengah. Misalkan kita memiliki suatu Circular Singly Linked List yang terdiri dari 5 simpul dan masing-masing simpul berisi informasi A, B, C, D, dan E. Kita akan menghapus simpul yang berada di posisi tengah, yaitu simpul yang berisi informasi D. Adapun langkah-langkah penghapusan tengah tersebut adalah sebagai berikut:
- Simpul depan yang ditunjuk oleh CL ditunjuk juga oleh pointer bantu [Bantu = CL].
- Gerakan pointer bantu hingga satu simpul sebelum simpul yang akan dihapus [while[Bantu->Kanan->Isi != ‘D’] Bantu = Bantu->Kanan].
- Simpul berikutnya ditunjuk pointer hapus [Hapus = Bantu->Kanan].
- Pointer kanan dari bantu menunjuk kanan hapus [Bantu->Kanan = Hapus->Kanan].
- Pointer kanan hapus menunjuk hapus [Hapus->Kanan = Hapus].
Skema penghapusan simpul tengah dapat dilihat pada Gambar 7.
Gambar 7. Penghapusan Simpul Tengah pada Circular Singly Linked List
Fungsi penghapusan simpul tengah dengan mengikuti langkah-langkah dan gambar 7 di atas dapat dilihat berikut ini.
void Hapus_Tengah[simpul &CL, char elemen] { simpul hapus, bantu; if[CL == NULL] coutIsi != elemen]bantu=bantu->kanan; hapus = bantu->kanan; bantu->kanan = hapus->kanan; hapus->kanan = hapus; free[hapus]; } }Berikut ini program lengkap untuk operasi pada Circular Singly Linked List yaitu operasi untuk penyisipan depan, penyisipan belakang, penyisipan tengah, penghapusan simpul depan, penghapusan simpul tengah, dan penghapusan simpul belakang, serta pencetakan elemen simpul.
/* ==PROGRAM CIRCULAR SINGLY LINKED LIST== ==========BY : lAMHOT SITORUS========== ======================================= */ #include #include #include typedef struct node *simpul; struct node { char Isi; simpul kanan; }; //====================== //==Prototype Function== //====================== void Sisip_Depan[simpul &CL, char elemen]; void Sisip_Belakang[simpul &CL, char elemen]; void Sisip_Tengah[simpul &&CL, char elemen1, char elemen2]; void Hapus_Depan[simpul &CL]; void Hapus_Belakang[simpul &CL]; void Hapus_Tengah[simpul &CL, char elemen]; void Cetak[simpul CL]; //================= //==Function Main== //================= main[] { char huruf, huruf2; simpul CL = NULL; //Pastikan bahwa DL kosong int i; coutkanan = hapus->kanan; hapus->kanan = hapus; free[hapus]; } } //====================eof====================Deletion from a Circular Linked List
We have already discussed circular linked list and traversal in a circular linked list in the below articles:
Introduction to circular linked list
Traversal in a circular linked list
In this article, we will learn about deleting a node from a circular linked list. Consider the linked list as shown below:
We will be given a node and our task is to delete that node from the circular linked list.
Examples:
Input : 2->5->7->8->10->[head node] data = 5 Output : 2->7->8->10->[head node] Input : 2->5->7->8->10->[head node] 7 Output : 2->5->8->10->[head node]Algorithm
Case 1: List is empty.
- If the list is empty we will simply return.
Case 2:List is not empty
- If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.
- Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.
- If the node is found, check if it is the only node in the list. If yes, set head = NULL and free[curr].
- If the list has more than one node, check if it is the first node of the list. Condition to check this[ curr == head]. If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.
- If curr is not the first node, we check if it is the last node in the list. Condition to check this is [curr -> next == head].
- If curr is the last node. Set prev -> next = head and delete the node curr by free[curr].
- If the node to be deleted is neither the first node nor the last node, then set prev -> next = curr -> next and delete curr.
Struktur Data - Pertemuan 13
"Doubly Linked List"
Pengertian double linked list
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.b. Double Linked List Non Cilcular
Pada Operasi Double Linked List terdapat 6 Operasi, yaitu :
- Insert Kiri
- Insert Kanan
- Insert Tengah
- Delete Kiri
- Delete Kanan
- Delete Tengah.
- 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:
- 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:
- 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].
- 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].
- 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].
- 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].