Bagaimana cara delete kanan pada singly circular linked list ?
Daftar Isi1. Circular Singly Linked List Show 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 ListHampir 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 simpulPenyisipan 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 depanSimpul 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:
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 belakangPenyisipan 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:
Baca Juga Struct pada C++ Pengertian dan Contoh Program 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 tengahDalam 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:
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) cout<<"List Kosong ............."<1.2. Penghapusan SimpulYang 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 depanMenghapus simpul yang ada pada posisi depan. Langkah-langkah penghapusan simpul pada posisi depan adalah sebagai berikut:
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) cout<<"Linked List Kosong ............"; else { bantu = CL; while(bantu->kanan != CL) bantu=bantu->kanan; Hapus = CL; CL = CL->kanan; bantu->kanan = CL; Hapus->kanan = Hapus; free(Hapus); } }b. Penghapusan simpul belakangMenghapus simpul yang ada pada posisi belakang. Langkah-langkah penghapusan simpul pada posisi belakang adalah sebagai berikut:
Baca Juga Double Linked List pada C++ Pengertian dan Contoh Program 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) cout<<"Linked List Kosong .............."; else { bantu = CL; while(bantu->kanan->kanan != CL) bantu= bantu->kanan; hapus = bantu->kanan; bantu->kanan = CL; hapus->kanan = hapus; free(hapus); } }c. Penghapusan simpul tengahYang 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:
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) cout<<"Linked List Kosong ..............."; else { bantu = CL; while(bantu->kanan->Isi != 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========== ======================================= */ #includeBaca Juga Pengertian dan Contoh Program Sorting pada C++ Deletion from a Circular Linked ListWe have already discussed circular linked list and traversal in a circular linked list in the below articles: 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 2:List is not empty
Struktur Data - Pertemuan 13"Doubly Linked List"Pengertian double linked listDouble 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 CilcularCircular 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 CilcularNon 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 :
1. Insert Simpul Depan (Kiri) Penyisipan simpul baru selalu berada di posisi paling depan. Penyisipan simpul depan dapat dilakukan dengan langkah berikut:
· 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
· 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
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:
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
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
Daftar Pustaka1. 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 6.https://pintarkom.com/double-linked-list-pada-c-plus/ 7.http://bocahngoding.blogspot.com/2017/12/gan-setia-bocah-ngoding-pada-pelajaran.html |