Langsung ke konten utama

Tugas Pertemuan 16

Circular Linked List pada C++. Semua Linked List baik Singly maupun Doubly selalu berisi pointer NULL yaitu pointer Next simpul terakhir dari Singly Linked List dan pointer kiri simpul pertama dan pointer kanan simpul terakhir Doubly Linked List. Dengan demikian untuk membaca isi Linked List selalu dilakukan dari simpul pertama ke kanan. Ada kalanya kita membaca isi Linked List mulai dari posisi tertentu tanpa harus mundur dan kembali ke posisi semula. Maka untuk itu kita buat dengan Linked List Melingkar (Circular Linked List).

Circular Linked List dapat dilakukan terhadap Singly Linked List maupun Doubly Linked List. Dalam Circular Linked List tidak terdapat suatu simpul yang bernilai NULL. Hal ini terjadi karena simpul terakhir dihubungkan terhadap simpul pertama untuk Singly Linked List dan simpul pertama dengan simpul terakhir saling terhubung untuk Doubly Linked List. Semua simpul berhak diperlakukan sebagai simpul depan.

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

 

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).

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).

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 ............."<<endl;
  else
  {
    bantu = CL;
    while(bantu->Isi != elemen2) bantu=bantu->kanan;
    baru->kanan = bantu->kanan;
    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)
    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 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)
    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 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)
    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==========
  ======================================= */
  
#include
#include
using namespace std;
//mendeklarasikan struct yang mendefinisikan satu nodes
struct node
{
 int data;
 node *next; };
//kelas untuk menangani node berisi penunjuk head dan tail
class list
{
  private:
  node *head, *tail;
  public:
  list()
  {
   head=NULL;
   tail=NULL;
  }   void createnode(int value)
  {
//buat pointer untuk memasukkan nilai
   node *temp=new node;
   temp->data=value;
   temp->next=NULL;
//jika head berisi null berarti berarti data yang ditaut kosong
   if(head==NULL)
   {
    head=temp;
    tail=temp;
    temp=NULL;
   }
   else
   {     tail->next=temp;
    tail=temp;
   }
  }
// untuk menampilkan daftar node dari data yang tertaut/linked
  void display()
  {
   node *temp=new node;
   temp=head;
   while(temp!=NULL)
   {
    cout<data<<"\t";
    temp=temp->next;
   }
  }
//fungsi untuk memasukkan node di awal=head
  void insert_start(int value)
  {
   node *temp=new node;
   temp->data=value;
   temp->next=head;
   head=temp;
  }
//fungsi untuk memasukkan node pada posisi tertentu
  void insert_position(int pos, int value)
  {
   node *pre=new node;
   node *cur=new node;
   node *temp=new node;
   cur=head;
//melakukan loop untuk mencapai node tertentu
   for(int i=1;inext;
   }
   temp->data=value;
   pre->next=temp;    temp->next=cur;
  }
//fungsi untuk menghapus node pertama dimana temp=head
  void delete_first()
  {
   node *temp=new node;
   temp=head;
   head=head->next;
   delete temp;
  }
//fungsi untuk menghapus node terakhir
  void delete_last()
  {
   node *current=new node;
   node *previous=new node;
   current=head;
//mencari node terakhir hingga mencapai null/kosong untuk menentukan tail
   while(current->next!=NULL)
   {
    previous=current;
    current=current->next;    }
   tail=previous;
//jika sudah mencapai akhir , hapus
   previous->next=NULL;
   delete current;
  }
//fungsi untuk menghapus node pada posisi tertentu
  void delete_position(int pos)
  {
   node *current=new node;
   node *previous=new node;
   current=head;
//cari posisi yang ingin dihapus kalau sudah ketemu hapus dan lanjutkan pada node berikutnya
   for(int i=1;inext;
   }
   previous->next=current->next;
  }
};
int main()
{
 //memasukkan nilai node
 list obj;
 obj.createnode(20);
 obj.createnode(30);
 obj.createnode(40);
 obj.createnode(50);
 obj.createnode(60);
 cout<<"http://voltemlibrary.blogspot.com\n";
 cout<<"\n";
 cout<<"---------------Tampilkan semua nodes---------------";
 cout<<"\n--------------------------------------------------\n";
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"-----------------Insert diakhir-----------------";
 cout<<"\n--------------------------------------------------\n";
 obj.createnode(70);
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"----------------Insert diawal----------------";
 cout<<"\n--------------------------------------------------\n";
 obj.insert_start(80);
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"-------------Insert pada posisi 5--------------";
 cout<<"\n--------------------------------------------------\n";
 obj.insert_position(5,90);
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"----------------Delete awal-----------------";
 cout<<"\n--------------------------------------------------\n";
 obj.delete_first();
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"-----------------Delete akhir-------------------";
 cout<<"\n--------------------------------------------------\n";
 obj.delete_last();
 obj.display();
 cout<<"\n--------------------------------------------------\n";
 cout<<"--------------Delete posisi ke-4--------------";
 cout<<"\n--------------------------------------------------\n";
 obj.delete_position(4);
 obj.display();
 cout<<"\n--------------------------------------------------\n";
  getch();
}

 

Label:

Komentar

Posting Komentar

Postingan populer dari blog ini

Tugas Pertemuan 6

SOAL 1. Buatlah suatu program Animasi Antrian dengan 4 buah pilihan : INSERT, DELETE, CETAK ANTRIAN, QUIT. Jika dipilih INSERT : program akan meminta user untuk menginput sebuah karakter yang akan dimasukan kedalam antrian Jika dipilih DELETE : maka karakter pertama masuk akan dikeluarkan dari antrian Jika dipilih CETAK ANTRIAN : komputer menampilkan karakter yang ada pada antrian Jika dipilih QUIT : program keluar   Jawaban #include<stdio.h> #include #include #include #define n 10 using namespace std; void INSERT(); void DELETE(); void CETAKLAYAR(); void Inisialisasi(); void RESET(); int PIL,F,R; char PILIHAN [1],HURUF; char Q[n]; void main ( ) { Inisialisasi(); do { cout >PILIHAN; PIL=atoi(PILIHAN); switch (PIL) { case 1: INSERT (); break; case 2: DELETE(); break; case 3: CETAKLAYAR (); break; default: cout >HURUF; Q[++R]=HURUF; } else cout
Posting Komentar
Baca selengkapnya
Digital marketing dalam perspektif seorang pengusaha atau pebisnis lebih kepada sistem pemasaran dengan menggunakan media internet. Sudah pasti, di dalamnya termasuk mobile phone hingga beberapa situs jejaring sosial lainnya. Hanya saja, agar Teknik ini lebih mengena kepada sasaran, sepertinya Teknik promosi lebih dikesampingkan dan mengutamakan komunikasi. Menjalin hubungan secara personal dengan konsumen dengan cara mendengar keluhan atau saran akan membuat pelanggan lebih merasa dihargai. Yang pada akhirnya akan memberikan nilai tambah terhadap perkembangan bisnis terutama brand perusahaan. Terlihat sederhana namun sulit untuk dipastikan terlebih bagi mereka yang kurang memahami akan pengertian digital marketing sebenarnya. (Daengs, Achmad, Andi Farouq, 2016 : 287-293). Menurut Urban (2004:2) Digital Marketing menggunakan internet dan teknologi informasi untuk memperluas dan meningkatkan fungsi marketing tradisional. Definisi ini berkonsentrasi pada seluruh marketing tradisi...
Posting Komentar
Baca selengkapnya

Tugas Pertemuan 14

  Latihan  Pohon dengan jumlah simpul=273 merupakan Full atau atau Complete tree  Berapa kedalamannya?  Nomor berapa simpul terkiri dari level tersebut?  Berapa jumlah maksimum simpul pada level 7  Nomor berapa anak kanan dari simpul ke 180? Ada dilevel berapa anak tersebut  Nomor berapa orang tua dari simpul ke 83? Ada di level berapa orang tua tertsebut?  Jawaban : Complete tree 9 level Nomor 256 64 Simpul tidak ada, karena rumus anak kanan adalah 2n+1, maka 2(180)+1=361. sementara jumlah simpul sebanyak 273. orang tua dari simpul ke 83 adalah 41, berada pada level 6. Kirimkan Ini lewat Email BlogThis! Berbagi ke Twitter Berbagi ke Facebook
Posting Komentar
Baca selengkapnya