Struktur Data - Daftar Tertaut Melingkar

Circular Linked List adalah variasi dari Linked list dimana elemen pertama mengarah ke elemen terakhir dan elemen terakhir mengarah ke elemen pertama. Daftar Tertaut Tunggal dan Daftar Tertaut Ganda dapat dibuat menjadi daftar tertaut melingkar.

Daftar Tertaut Tunggal sebagai Edaran

Dalam daftar tertaut tunggal, penunjuk berikutnya dari simpul terakhir menunjuk ke simpul pertama.

Daftar Tertaut Ganda sebagai Edaran

Dalam daftar tertaut ganda, penunjuk berikutnya dari simpul terakhir menunjuk ke simpul pertama dan penunjuk sebelumnya dari simpul pertama menunjuk ke simpul terakhir yang membuat lingkaran di kedua arah.

Sesuai ilustrasi di atas, berikut adalah poin-poin penting yang harus diperhatikan.

  • Tautan terakhir menunjuk ke tautan pertama dari daftar dalam kedua kasus daftar tertaut tunggal maupun ganda.

  • Tautan pertama sebelumnya menunjuk ke yang terakhir dari daftar jika ada daftar tertaut ganda.

Operasi Dasar

Berikut adalah operasi penting yang didukung oleh daftar melingkar.

  • insert - Menyisipkan elemen di awal daftar.

  • delete - Menghapus elemen dari awal daftar.

  • display - Menampilkan daftar.

Operasi Penyisipan

Kode berikut menunjukkan operasi penyisipan dalam daftar tertaut melingkar berdasarkan daftar tertaut tunggal.

Contoh

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

Operasi Penghapusan

Kode berikut menunjukkan operasi penghapusan dalam daftar tertaut melingkar berdasarkan daftar tertaut tunggal.

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

Operasi Daftar Tampilan

Kode berikut menunjukkan operasi daftar tampilan dalam daftar tertaut melingkar.

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

Untuk mengetahui implementasinya dalam bahasa pemograman C, silahkan klik disini .