PERTEMUAN 17 CIRCULAR DOUBLE LINKED LIST

Circular Double Linked List
Circular Double Linked List  adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.
Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.
Semua sel yang terdapat pada list disambungkan dengan pointer, sedangkan tiap sel memiliki tiga komponen yaitu value, pointer ke sel sebelumnya dan pointer ke sel berikutnya. Dengan memiliki dua buah pointer ini, maka doubly-linked list dapat diakses dengan dua arah, ke arah depan dan ke belakang.
Dibutuhkan dua buah variabel pointer yaitu head dan tail. Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.
1. Inisialiasasi Node
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:
TNode *head, *tail;
2. Fungsi Inisialisasi Double Linked List Circular
void init()
{
head = NULL;
tail = NULL;
}
3. Function isEmpty
Fungsi isEmpty digunakan untuk mengetahui kosong tidaknya DLLC. Berikut ini adalah pendeklarasian fungsi isEmpty :
int isEmpty()
{
if(head == NULL) return 1;
else return 0;
}
4. Penambahan Data di Depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya dan node baru ini menempati posisi sebagai head dan tail.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu. Berikut ini contoh syntax untuk menambahkan node atau data di depan.
void insertDepan (int databaru)
{
…….
…….
}
5. Penambahan Node di Belakang
Penambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian node baru tersebut akan menjadi tail. Berikut ini contoh syntax untuk menambahkan node dari belakang.
Syntax :
void insertBelakang(int databaru)
{
...........
...........
}
6. Function Untuk Menampilkan Isi Linked List
Fungsi ini berfungsi untuk menampilkan data atau isi dari linked list sesuai dengan data yang telah diinputkan. Dibutuhkan variabel bantu untuk menampung data, kemudian dilakukan perulangan yang menampilkan data. Syntax :
void tampil(){
………
………
}
7. Function Untuk Menghapus Node Terdepan
Menghapus data terdepan berarti menghapus head. Kemudian head akan berpindah ke node di belakangnya. Dan tail akan menunjuk ke head yang baru itu. Untuk menghapus data terdepan membutuhkan pointer bantu yang menunjuk kepada head.
Syntax :
void hapusDepan(){
………
………
}
8. Function Untuk Menghapus Node Terbelakang
Pointer hapus tidak perlu di loop untuk mencari node terakhir. Pointer hapus hanya perlu menunjuk pada pointer tail saja. Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya. Kemudian pointer tail akan berpindah ke node sebelumnya.
Syntax :
void hapusBelakang()
{
………
………
}
9. Function Untuk Menghapus Semua Elemen Linked List
Menggunakan pointer bantu yang digunakan untuk bergerak sepanjang list, dan menggunakan pointer hapus yang digunakan untuk menunjuk node-node yang akan dihapus. Pada saat pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan didelete.
Syntax :
void clear()
{
………
………
}

TUGAS.

Program :

Buat program animasi Circular Doubly Linked List untuk mengelola data mahasiswa dengan struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI . Data terurut naik berdasarkan NIM. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA, HAPUS DATA, CETAK DATA, EXIT.

Ket :

INSER DATA : menambah data

HAPUS DATA : menghapus satu data berdasarkan kriteria NIM

CETAK DATA : mencetak seluruh isi linked list

EXIT : Keluar/selesai

Tampilan menu :

CIRCULAR DOUBLY LINKED LIST

==========================

1. INSERT DATA

2. HAPUS DATA

3. CETAK DATA

4. EXIT

Pilihan (1 – 4) :

Source Code :

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <windows.h>//mendukung format system("CLS") sebagai peganti clrscr()

using namespace std;

int pilih; void pilihan();

void insert_data();

void hapus_data();

void cetak_data();

struct node

{

 int nomorinduk;

 char nama [40];

 char gender [20];

 float nilai;

 node *prev, *next;

};

node *baru, *head=NULL, *tail=NULL,*help,*del;

main()//interface monitor

{

 do

 {

  system("cls");

  cout<<"\tLIN. DOUBLY LINKED LIST"<<endl;

  cout<<"\t=========================="<<endl;

  cout<<"\t1. INSERT DATA"<<endl;

  cout<<"\t2. HAPUS DATA"<<endl;

  cout<<"\t3. CETAK DATA"<<endl;

  cout<<"\t4. EXIT"<<endl;

  cout<<"\tPilihan (1 - 4) : ";

  cin>>pilih;

  cout<<endl<<endl;

  pilihan();

  cout<<"==============================="<<endl;

 }

 while(pilih!=4);

}

void pilihan()//fungsi "pilihan" untuk pemrosesan

{

 if(pilih==1)

 insert_data();

 else if(pilih==2)

 hapus_data();

 else if(pilih==3)

 cetak_data();

 else

 {

  cout<<"EXIT";

  cout<<"\nSampai Jumpa lagi"<<endl;

 }

}

void buat_baru()//fungsi membuat data baru

{

 baru = new(node);

 cout<<"Masukkan Nomor Induk : ";cin>>baru->nomorinduk;

 cout<<"Masukkan Nama : ";cin>>baru->nama;

 cout<<"Masukkan Gender : ";cin>>baru->gender;

 cout<<"Masukkan Nilai : ";cin>>baru->nilai;

 cout<<"\n\t---Data telah dimasukkan---";

 cout<<"\n\nPRESS ENTER TO CONTINUE...";

 getch();

 baru->prev=NULL;

 baru->next=NULL;

}

void insert_data()

{

 buat_baru();

 if(head==NULL)

 {

  head=baru;

  tail=baru;

 }

 else

 {

  baru->next=head;

  head->prev=baru;

  head=baru;

 }

 cout<<endl<<endl;

}

void hapus_data()//fungsi penghapusan data

{

 int hapus,nomorinduk;

 if(head==NULL)

 {

  cout<<"\nLinked List kosong, \nPenghapusan tidak dapat dilakukan"<<endl;//data yang habis maka tampilannya

 }

 else

 {

  hapus=head->nomorinduk;

  cout<<"\nData yang dihapus adalah ";//pemilihan data yang akan dihapus

  cin>>nomorinduk;

  del = head;

  head = head->next;

  delete del;

 }

}

void cetak_data()

{

 if (head==NULL)

 cout<<"\nData tidak dapat ditemukan!"<<endl;//data yang kosong

 else

 {

  help=head;

  while(help!=NULL)

  {

   cout<<" Nomor Induk : "<<help->nomorinduk;//data akan muncul dengan tampilan

   cout<<" Nama : "<<help->nama;

   cout<<" Gender : "<<help->gender;

   cout<<" Nilai : "<<help->nilai<<endl;

   help=help->next;

  }

 }

getch();

}

Maka outputnya seperti ini.

PERTEMUAN 16 CIRCULAR LINKED LIST

Circular Linked List
Circular Linked List adalah struktur data tertaut yang sedikit lebih rumit. Dalam daftar tertaut melingkar, kita dapat menyisipkan elemen di mana saja dalam daftar, sedangkan dalam array kita tidak dapat menyisipkan elemen di mana pun dalam daftar karena berada dalam memori yang berdekatan. Dalam daftar tertaut melingkar, elemen sebelumnya menyimpan alamat elemen berikutnya dan elemen terakhir menyimpan alamat elemen awal. Unsur-unsur menunjuk satu sama lain dengan cara melingkar yang membentuk rantai melingkar. Daftar tertaut melingkar memiliki ukuran dinamis yang berarti memori dapat dialokasikan ketika diperlukan.

Aplikasi Circular Linked List

• Aplikasi kehidupan nyata di mana daftar tertaut melingkar digunakan adalah Komputer Pribadi kami, tempat beberapa aplikasi berjalan. Semua aplikasi yang berjalan disimpan dalam daftar tertaut melingkar dan OS memberikan slot waktu tetap untuk semua untuk menjalankan. Sistem Operasi terus mengulangi daftar yang ditautkan hingga semua aplikasi selesai.
• Contoh lain bisa berupa permainan Multi Pemain. Semua Pemain disimpan dalam Circular Linked List dan pointer terus bergerak maju saat peluang pemain berakhir.
• Circular Linked List juga dapat digunakan untuk membuat Circular Queue. Dalam Antrian kita harus menyimpan dua pointer, FRONT dan REAR dalam memori sepanjang waktu, di mana seperti dalam Circular Linked List, hanya satu pointer yang diperlukan.

Menerapkan Circular Linked List

Menerapkan daftar tertaut melingkar sangat mudah dan hampir mirip dengan penerapan daftar tertaut linier, dengan satu-satunya perbedaan adalah bahwa, dalam daftar tertaut melingkar, Node terakhir akan memiliki titik berikutnya ke Kepala Daftar. Dalam daftar tertaut Linear, Node terakhir cukup menahan NULL di pointer berikutnya.

Jadi ini akan menjadi kelas Node, seperti yang telah kita pelajari dalam pelajaran, ini akan digunakan untuk membentuk Daftar.

class Node {
  public:
  int data;
  //pointer to the next node
  node* next;
  
  node() {
    data = 0;
    next = NULL;
  }
  
  node(int x) {
    data = x;
    next = NULL;
  }
} 

Circular Linked List

Kelas Circular Linked List akan hampir sama dengan kelas Linked List yang kami pelajari dalam pelajaran sebelumnya, dengan sedikit perbedaan dalam implementasi metode kelas.

class CircularLinkedList {
  public:
  node *head;
  //declaring the functions
  
  //function to add Node at front
  int addAtFront(node *n);
  //function to check whether Linked list is empty
  int isEmpty();
  //function to add Node at the End of list
  int addAtEnd(node *n);
  //function to search a value
  node* search(int k);
  //function to delete any Node
  node* deleteNode(int x);
  
  CircularLinkedList() {
    head = NULL;
  }
}

Penyisipan di Awal

Langkah-langkah untuk memasukkan Node di awal:

1. Node pertama adalah Head untuk setiap Linked List.
2. Ketika Daftar Tertaut yang baru dipakai, itu hanya memiliki Kepala, yaitu Null.
3. Lain, Kepala memegang pointer ke Node Pertama Daftar.
4. Ketika kita ingin menambahkan Node di bagian depan, kita harus membuat titik kepala ke sana.
5. Dan pointer Selanjutnya dari Node yang baru ditambahkan, harus menunjuk ke Head sebelumnya, apakah itu NULL (dalam hal Daftar baru) atau pointer ke Node pertama dari Daftar.
6. Head Node sebelumnya sekarang menjadi Node kedua dari Linked List, karena Node baru ditambahkan di bagian depan.

int CircularLinkedList :: addAtFront(node *n) {
  int i = 0;
  /* If the list is empty */
  if(head == NULL) {
    n->next = head;
    //making the new Node as Head
    head = n;
    i++;
  }
  else {
    n->next = head;
    //get the Last Node and make its next point to new Node
    Node* last = getLastNode();
    last->next = n;
    //also make the head point to the new first Node
    head = n;
    i++;
  }
  //returning the position where Node is added
  return i;
}

Penyisipan di Akhir

Langkah-langkah untuk memasukkan Node di akhir:

1. Jika Daftar Tertaut kosong maka kita cukup, tambahkan Node baru sebagai Kepala Daftar Tertaut.

2. Jika Daftar Tertaut tidak kosong maka kita menemukan simpul terakhir, dan membuatnya 'di sebelah Node baru, dan membuat berikutnya dari titik Node yang baru ditambahkan ke Kepala Daftar.

int CircularLinkedList :: addAtEnd(node *n) {
  //If list is empty
  if(head == NULL) {
    //making the new Node as Head
    head = n;
    //making the next pointer of the new Node as Null
    n->next = NULL;
  }
  else {
    //getting the last node
    node *last = getLastNode();
    last->next = n;
    //making the next pointer of new node point to head
    n->next = head;
  } 
}

Mencari Elemen dalam Daftar

Dalam searhing kita tidak perlu berbuat banyak, kita hanya perlu melintasi seperti yang kita lakukan saat mendapatkan node terakhir, dalam hal ini kita juga akan membandingkan data dari Node. Jika kita mendapatkan Node dengan data yang sama, kita akan mengembalikannya, jika tidak, kita akan mengarahkan pointer kita ke Node berikutnya, dan seterusnya.

node* CircularLinkedList :: search(int x) {
  node *ptr = head;
  while(ptr != NULL && ptr->data != x) {
    //until we reach the end or we find a Node with data x, we keep moving
    ptr = ptr->next;
  }
  return ptr;
}

Menghapus Node dari Daftar

Menghapus sebuah simpul dapat dilakukan dengan banyak cara, seperti kita pertama-tama mencari Node dengan data yang ingin kita hapus dan kemudian kita menghapusnya. Dalam pendekatan kami, kami akan mendefinisikan metode yang akan mengambil data yang akan dihapus sebagai argumen, akan menggunakan metode pencarian untuk menemukannya dan kemudian akan menghapus Node dari Daftar.

Untuk menghapus Node dari daftar, kita perlu melakukan hal berikut:

• Jika Node yang akan dihapus adalah node pertama, maka cukup atur pointer Next Head untuk menunjuk ke elemen berikutnya dari Node yang akan dihapus. Dan perbarui pointer Node Terakhir berikutnya juga.

• Jika Node berada di tengah-tengah suatu tempat, kemudian cari Node di depannya, dan buat Node sebelum itu menunjuk ke Node di sebelahnya.

• Jika Node di bagian akhir, maka lepaskan dan buat titik simpul terakhir yang baru ke kepala.

node* CircularLinkedList :: deleteNode(int x) {
  //searching the Node with data x
  node *n = search(x);
  node *ptr = head;
  if(ptr == NULL) {
    cout << "List is empty";
    return NULL;
  }
  else if(ptr == n) {
    ptr->next = n->next;
    return n;
  }
  else {
    while(ptr->next != n) {
      ptr = ptr->next;
    }
    ptr->next = n->next;
    return n;
  }
}

---