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;
  }
}

---