Circular Linked List, Doubly Linked list, and Circular Doubly Linked List


Single Linked List Circular

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
·      Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
·      Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi Single Linked List Circular
-    Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
-    Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.



Dalam Single Linked List Circular, kami melakukan operasi berikut:
·      Insertion
·      Deletion
·      Display

Dalam daftar tertaut melingkar, operasi penyisipan dapat dilakukan dengan tiga cara. Mereka adalah sebagai berikut ...
o  Memasukkan Di Awal Daftar
o  Memasukkan Di Akhir daftar
o  Memasukkan Di Lokasi Tertentu dalam daftar

Memasukkan Di Awal Daftar
Kita dapat menggunakan langkah-langkah berikut untuk menyisipkan simpul baru di awal daftar tertaut melingkar ...
             Langkah 1 - Buat newNode dengan nilai yang diberikan.
Langkah 2 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 3 - Jika itu Kosong , atur head = newNode dan newNode → next = head .
Langkah 4 - Jika Tidak Kosong maka, tentukan Node pointer ' temp ' dan inisialisasi dengan ' head '.
Langkah 5 - Terus gerakkan ' temp ' ke node berikutnya hingga mencapai ke node terakhir (sampai ' temp → next == head ').
Langkah 6 - Set ' newNode → next = head ', ' head = newNode ' dan ' temp → next = head '.

Memasukkan Di Akhir daftar
Kita dapat menggunakan langkah-langkah berikut untuk menyisipkan simpul baru di akhir daftar tertaut melingkar ...
Langkah 1 - Buat newNode dengan nilai yang diberikan.
Langkah 2 - Periksa apakah daftar itu Kosong ( kepala == NULL ).
Langkah 3 - Jika itu Kosong , atur head = newNode dan newNode → next = head .
Langkah 4 - Jika Tidak Kosong maka, tentukan temp penunjuk simpul dan inisialisasi dengan kepala .
Langkah 5 - Terus pindahkan temp ke simpul berikutnya hingga mencapai ke simpul terakhir dalam daftar (hingga temp → berikutnya == kepala ).
Langkah 6 - Tetapkan temp → selanjutnya = newNode dan newNode → next = head .

Memasukkan Di Lokasi Tertentu dalam daftar (Setelah Node)
Kita dapat menggunakan langkah-langkah berikut untuk menyisipkan simpul baru setelah simpul dalam daftar tertaut melingkar ...
Langkah 1 - Buat newNode dengan nilai yang diberikan.
Langkah 2 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 3 - Jika itu Kosong , atur head = newNode dan newNode → next = head .
Langkah 4 - Jika Tidak Kosong maka, tentukan temp penunjuk simpul dan inisialisasi dengan kepala .
Langkah 5 - Terus pindahkan temp ke simpul berikutnya hingga mencapai ke simpul setelah itu kami ingin memasukkan newNode (sampai temp1 → data sama dengan lokasi , di sini lokasi adalah nilai simpul setelah itu kami ingin memasukkan newNode) .
Langkah 6 - Setiap kali periksa apakah temp dicapai ke node terakhir atau tidak. Jika sudah mencapai simpul terakhir maka tampilkan 'Diberikan simpul tidak ditemukan dalam daftar !!! Penyisipan tidak dimungkinkan !!! ' dan menghentikan fungsinya. Kalau tidak, pindahkan temp ke node berikutnya.
Langkah 7 - Jika temp dicapai ke simpul yang tepat setelah itu kami ingin memasukkan newNode kemudian periksa apakah itu simpul terakhir (temp → berikutnya == kepala).
Langkah 8 - Jika temp adalah node terakhir maka atur temp → next = newNode dan newNode → next = head .
Langkah 8 - Jika temp bukan node terakhir maka atur newNode → next = temp → berikutnya dan temp → next = newNode .

Dalam daftar tertaut melingkar, operasi penghapusan dapat dilakukan dengan tiga cara yaitu sebagai berikut ...

  •          Menghapus dari Awal daftar
  •          Menghapus dari Akhir daftar
  •        Menghapus Node Tertentu

Menghapus dari Awal daftar
Kita dapat menggunakan langkah-langkah berikut untuk menghapus simpul dari awal daftar tertaut melingkar ...
Langkah 1 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 2 - Jika itu Kosong maka, tampilkan 'Daftar Kosong !!! Penghapusan tidak dimungkinkan ' dan menghentikan fungsinya.
Langkah 3 - Jika Tidak Kosong maka, tentukan dua pointer Node 'temp1' dan ' temp2 ' dan inisialisasi keduanya ' temp1 ' dan ' temp2 ' dengan kepala .
Langkah 4 - Periksa apakah daftar hanya memiliki satu simpul ( temp1 → berikutnya == kepala )
Langkah 5 - Jika BENAR maka atur head = NULL dan hapus temp1 (Mengatur kondisi daftar kosong )
Langkah 6 - Jika FALSE pindahkan temp1 hingga mencapai ke node terakhir. (sampai temp1 → selanjutnya == kepala )
Langkah 7 - Kemudian atur head = temp2 → selanjutnya , temp1 → berikutnya = kepala dan hapus temp2 .

Menghapus dari Akhir daftar
Kita dapat menggunakan langkah-langkah berikut untuk menghapus simpul dari ujung daftar tertaut melingkar ...
Langkah 1 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 2 - Jika itu Kosong maka, tampilkan 'Daftar Kosong !!! Penghapusan tidak dimungkinkan ' dan menghentikan fungsinya.
Langkah 3 - Jika Tidak Kosong maka, tentukan dua pointer Node 'temp1' dan ' temp2' dan inisialisasi ' temp1 ' dengan kepala .
Langkah 4 - Periksa apakah daftar hanya memiliki satu Node ( temp1 → berikutnya == kepala )
Langkah 5 - Jika BENAR . Kemudian, atur head = NULL dan hapus temp1 . Dan berakhir dari fungsinya. (Pengaturan kondisi daftar kosong )
Langkah 6 - Jika itu SALAH . Kemudian, atur ' temp2 = temp1 ' dan pindahkan temp1 ke simpul berikutnya. Ulangi hal yang sama hingga temp1 mencapai ke simpul terakhir dalam daftar. (sampai temp1 → selanjutnya == kepala )
Langkah 7 - Set temp2 → selanjutnya = kepala dan hapus temp1 .

Menghapus Node Tertentu dari daftar
Kita dapat menggunakan langkah-langkah berikut untuk menghapus simpul tertentu dari daftar tertaut melingkar ...
Langkah 1 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 2 - Jika itu Kosong maka, tampilkan 'Daftar Kosong !!! Penghapusan tidak dimungkinkan ' dan menghentikan fungsinya.
Langkah 3 - Jika Tidak Kosong maka, tentukan dua pointer Node 'temp1' dan ' temp2 ' dan inisialisasi ' temp1 ' dengan kepala .
Langkah 4 - Terus gerakkan temp1 hingga mencapai ke simpul yang tepat untuk dihapus atau ke simpul terakhir. Dan setiap kali atur ' temp2 = temp1 ' sebelum memindahkan ' temp1 ' ke simpul berikutnya.
Langkah 5 - Jika sudah mencapai node terakhir maka tampilkan 'Diberikan node tidak ditemukan dalam daftar! Penghapusan tidak mungkin !!! ' . Dan mengakhiri fungsinya.
Langkah 6 - Jika tercapai ke simpul persis yang ingin kita hapus, maka periksa apakah daftar hanya memiliki satu simpul ( temp1 → berikutnya == kepala )
Langkah 7 - Jika daftar hanya memiliki satu simpul dan itu adalah simpul yang akan dihapus maka atur head = NULL dan hapus temp1 ( gratis (temp1) ).
Langkah 8 - Jika daftar berisi beberapa node kemudian periksa apakah temp1 adalah simpul pertama dalam daftar ( temp1 == head ).
Langkah 9 - Jika temp1 adalah simpul pertama maka atur temp2 = kepala dan terus gerakkan temp2 ke simpul berikutnya sampai temp2 mencapai ke simpul terakhir. Kemudian atur head = head → selanjutnya , temp2 → nex t = head dan hapus temp1 .
Langkah 10 - Jika temp1 bukan simpul pertama maka periksa apakah simpul terakhir dalam daftar ( temp1 → berikutnya == kepala ).
Langkah 1 1- Jika temp1 adalah simpul terakhir maka atur temp2 → berikutnya = kepala dan hapus temp1 ( gratis (temp1) ).
Langkah 12 - Jika temp1 bukan node pertama dan bukan node lalu setel temp2 → berikutnya = temp1 → berikutnya dan hapus temp1 ( gratis (temp1) ).

Menampilkan Daftar Tertaut melingkar
Kita dapat menggunakan langkah-langkah berikut untuk menampilkan elemen daftar tertaut melingkar ...
Langkah 1 - Periksa apakah daftar itu Kosong ( kepala == NULL )
Langkah 2 - Jika Kosong , maka tampilkan 'Daftar Kosong !!!' dan menghentikan fungsinya.
Langkah 3 - Jika bukan Kosong maka, tentukan 'temp' Node pointer dan inisialisasi dengan kepala .
Langkah 4 - Tetap menampilkan temp → data dengan panah ( ---> ) sampai temp mencapai node terakhir
Langkah 5 - Akhirnya tampilkan temp → data dengan panah yang menunjuk ke head → data .

Doubly Linked List
Pengenalan Double Linked List
Pengertian Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next.

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.

Operasi pada Double Linked List

Double linked list memiliki beberapa operasi dasar pada list, misalkan penyisipan, penghapusan, menampilkan maju, dan menampilkan mundur.
·         Insert First: Penyisipan di awal list, sehingga pointer head juga akan berpindah ke elemen baru.
·         Insert Last: Penyisipan di akhir list, sehingga pointer tail juga akan berpindah ke elemen baru.
·         Insert After / Before: Penyisipan after/before kurang lebih sama satu sama lain.
·         Delete First: Penghapusan di awal list, pointer head akan berpindah ke node selanjutnya,sementara node awal akan di dealokasi.
·         Delete Last: Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya,sementara node akhir akan di dealokasi.
·         Delete Node: Penghapusan node dengan data tertentu.

Kode berikut menunjukkan operasi penyisipan di awal daftar yang tertaut ganda.
//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
      
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
      
   //point first to new first link
   head = link;
}

Kode berikut menunjukkan operasi penghapusan pada awal daftar yang tertaut ganda.
//delete first item
struct node* deleteFirst() {
 
   //save reference to first link
   struct node *tempLink = head;
       
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
       
   head = head->next;
       
   //return the deleted link
   return tempLink;
}

Kode berikut menunjukkan operasi penyisipan pada posisi terakhir dari daftar yang ditautkan ganda.
//insert link at the last location
void insertLast(int key, int data) {
 
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
       
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }
 
   //point last to new last node
   last = link;
}



Circular Doubly Linked

Double Linked List Circular 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.


Referensi:
http://christ-13.blogspot.com/2012/07/single-linked-list-circular-dan-non.html

http://www.btechsmartclass.com/data_structures/circular-linked-list.html
https://rizkidoank.com/2016/10/17/double-linked-list/
https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm
http://setyowahyudr.blogspot.com/2009/06/double-linked-list-circular.html

Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Image
Binary Search Tree  is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree The above properties of Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search a given key.
Read more

Hashing and Hash Tables, Trees & Binary Tree

Hashing Suppose we want to design a system for storing employee records keyed using phone numbers. And we want following queries to be performed efficiently:          Insert a phone number and corresponding information.         Search a phone number and fetch the information.        Delete a phone number and related information. We can think of using the following data structures to maintain information about different phone numbers.        Array of phone numbers and records.        Linked List of phone numbers and records.        Balanced binary search tree with phone numbers as keys.         Direct Access Table. Hashing is an improvement over Direct Access Table. The idea is to use hash function that converts a given phone number or any other key to a smaller number and uses the small number as index in a ...
Read more