Daftar Tautan Melingkar: Keuntungan dan Kerugian

Apa itu Daftar Tautan Melingkar?

Daftar tertaut melingkar adalah urutan node yang disusun sedemikian rupa sehingga setiap node dapat ditelusuri kembali ke dirinya sendiri. Di sini "node" adalah elemen referensi mandiri dengan penunjuk ke satu atau dua node di sekitarnya.

Di bawah ini adalah gambaran linked list melingkar dengan 3 node.

Di sini, Anda dapat melihat bahwa setiap node dapat ditelusuri ke dirinya sendiri. Contoh yang ditunjukkan di atas adalah daftar tertaut tunggal berbentuk lingkaran.

Catatan: Daftar tertaut melingkar yang paling sederhana, adalah sebuah simpul yang hanya menelusuri dirinya sendiri seperti yang ditunjukkan

Dasar Operations dalam daftar Circular Linked

Operasi dasar pada daftar tertaut melingkar adalah:

1. Insersi
2. Penghapusan dan
3. Lintasan

• Penyisipan adalah proses menempatkan sebuah node pada posisi tertentu dalam daftar tertaut melingkar.
• Penghapusan adalah proses menghapus node yang ada dari daftar tertaut. Node dapat diidentifikasi berdasarkan kemunculan nilainya atau posisinya.
• Penjelajahan daftar tertaut melingkar adalah proses menampilkan seluruh konten daftar tertaut dan menelusuri kembali ke node sumber.

Di bagian selanjutnya, Anda akan memahami penyisipan sebuah node, dan jenis penyisipan yang mungkin dilakukan dalam Daftar Tertaut Tunggal Melingkar.

Insersi Operaproduksi

Awalnya, Anda perlu membuat satu node yang menunjuk ke dirinya sendiri seperti yang ditunjukkan pada gambar ini. Tanpa node ini, penyisipan akan membuat node pertama.

Selanjutnya ada dua kemungkinan:

• Penyisipan pada posisi saat ini dari daftar tertaut melingkar. Hal ini sesuai dengan penyisipan di awal akhir daftar tertaut tunggal biasa. Dalam daftar tertaut melingkar, awal dan akhir adalah sama.
• Penyisipan setelah node yang diindeks. Node harus diidentifikasi dengan nomor indeks yang sesuai dengan nilai elemennya.

Untuk menyisipkan di awal/akhir daftar tertaut melingkar, yaitu pada posisi di mana node pertama kali ditambahkan,

• Anda harus memutus tautan mandiri yang ada ke node yang ada
• Penunjuk berikutnya dari node baru akan tertaut ke node yang sudah ada.
• Pointer berikutnya dari node terakhir akan menunjuk ke node yang disisipkan.

CATATAN: Penunjuk yang merupakan token master atau awal/akhir lingkaran dapat diubah. Itu masih akan kembali ke node yang sama pada traversal, yang dibahas sebelumnya.

Langkah-langkah pada (a) i-iii ditunjukkan di bawah ini:

(Node yang ada)

LANGKAH 1) Putuskan tautan yang ada

LANGKAH 2) Membuat forward link (dari node baru ke node yang sudah ada)

LANGKAH 3) Buat tautan loop ke node pertama

Selanjutnya, Anda akan mencoba menyisipkan setelah sebuah node.

Misalnya, mari kita masukkan “VALUE2” setelah node dengan “VALUE0”. Mari kita asumsikan bahwa titik awalnya adalah node dengan “VALUE0”.

• Anda harus memutus garis antara node pertama dan kedua dan menempatkan node dengan “VALUE2” di antaranya.
• Penunjuk berikutnya dari simpul pertama harus tertaut ke simpul ini, dan penunjuk berikutnya dari simpul ini harus tertaut ke simpul kedua sebelumnya.
• Pengaturan lainnya tetap tidak berubah. Semua node dapat ditelusuri ke dirinya sendiri.

CATATAN: Karena ada pengaturan siklik, memasukkan sebuah node melibatkan prosedur yang sama untuk node mana pun. Pointer yang menyelesaikan sebuah siklus menyelesaikan siklus sama seperti node lainnya.

Ini ditunjukkan di bawah ini:

(Katakanlah hanya ada dua node. Ini adalah kasus yang sepele)

LANGKAH 1) Hapus tautan dalam antara node yang terhubung

LANGKAH 2) Hubungkan node sebelah kiri ke node baru

LANGKAH 3) Hubungkan simpul baru ke simpul sebelah kanan.

penghapusan Operaproduksi

Mari kita asumsikan daftar tertaut melingkar dengan 3 simpul. Kasus penghapusan diberikan di bawah ini:

• Menghapus elemen saat ini
• Penghapusan setelah suatu elemen.

Penghapusan di awal/akhir:

1. Melintasi node pertama dari node terakhir.
2. Untuk menghapus dari akhir, hanya boleh ada satu langkah traversal, dari node terakhir ke node pertama.
3. Hapus tautan antara node terakhir dan node berikutnya.
4. Tautkan node terakhir ke elemen berikutnya dari node pertama.
5. Bebaskan node pertama.

(Pengaturan yang ada)

LANGKAH 1) Hapus tautan melingkar

LANGKAH 2) Hapus tautan antara simpul pertama dan berikutnya, hubungkan simpul terakhir ke simpul setelah simpul pertama

LANGKAH 3) Bebaskan / batalkan alokasi node pertama

Penghapusan setelah sebuah node:

1. Lintasi hingga node berikutnya adalah node yang akan dihapus.
2. Melintasi ke node berikutnya, menempatkan pointer pada node sebelumnya.
3. Hubungkan node sebelumnya ke node setelah node sekarang, menggunakan pointer berikutnya.
4. Bebaskan node saat ini (yang dihapus tautannya).

LANGKAH 1) Katakanlah kita perlu menghapus sebuah node dengan “VALUE1.”

LANGKAH 2) Hapus tautan antara node sebelumnya dan node saat ini. Tautkan simpul sebelumnya dengan simpul berikutnya yang ditunjuk oleh simpul saat ini (dengan VALUE1).

LANGKAH 3) Bebaskan atau batalkan alokasi node saat ini.

Penjelajahan Daftar Tertaut Melingkar

Untuk melintasi daftar tertaut melingkar, mulai dari penunjuk terakhir, periksa apakah penunjuk terakhir itu sendiri NULL. Jika kondisi ini salah, periksa apakah hanya ada satu elemen. Jika tidak, lintasi menggunakan penunjuk sementara hingga penunjuk terakhir tercapai lagi, atau sebanyak yang diperlukan, seperti yang ditunjukkan dalam GIF di bawah ini.

Keuntungan dari Daftar Tertaut Melingkar

Beberapa keuntungan dari daftar tertaut melingkar adalah:

1. Tidak ada persyaratan untuk penugasan NULL dalam kode. Daftar melingkar tidak pernah menunjuk ke pointer NULL kecuali sepenuhnya dibatalkan alokasinya.
2. Daftar tertaut melingkar menguntungkan untuk operasi akhir karena awal dan akhir bertepatan. Algorithms seperti penjadwalan Round Robin dapat dengan rapi menghilangkan proses-proses yang diantri secara melingkar tanpa menemui petunjuk referensial yang menggantung atau NULL.
3. Daftar tertaut melingkar juga menjalankan semua fungsi reguler dari daftar tertaut tunggal. Faktanya, melingkar daftar tertaut ganda dibahas di bawah ini bahkan dapat menghilangkan kebutuhan traversal penuh untuk menemukan lokasi suatu elemen. Elemen itu paling banyak hanya berlawanan dengan awal, menyelesaikan hanya setengah dari daftar tertaut.

Kekurangan Daftar Tertaut Melingkar

Kerugian dalam menggunakan daftar tertaut melingkar adalah sebagai berikut:

1. Daftar melingkar lebih rumit dibandingkan dengan daftar tertaut tunggal.
2. RevBentuk daftar melingkar lebih kompleks dibandingkan dengan daftar tunggal atau ganda.
3. Jika tidak ditangani dengan hati-hati, kode tersebut mungkin akan berputar tanpa batas.
4. Lebih sulit untuk menemukan akhir daftar dan kontrol loop.
5. Memasukkan di Mulai, kita harus menelusuri daftar lengkap untuk menemukan node terakhir. (Perspektif Implementasi)

Daftar Tertaut Tunggal sebagai Daftar Tertaut Melingkar

Anda dianjurkan untuk mencoba membaca dan menerapkan kode di bawah ini. Ini menyajikan aritmatika penunjuk yang terkait dengan daftar tertaut melingkar.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Penjelasan kode:

1. Dua baris kode pertama adalah file header yang disertakan.
2. Bagian selanjutnya menjelaskan struktur setiap node referensi mandiri. Ini berisi nilai dan pointer dengan tipe yang sama dengan struktur.
3. Setiap struktur berulang kali terhubung ke objek struktur dengan tipe yang sama.
4. Ada prototipe fungsi yang berbeda untuk:
   1. Menambahkan elemen ke daftar tertaut yang kosong
   2. Memasukkan di saat ini menunjuk posisi daftar tertaut melingkar.
   3. Memasukkan setelah tertentu diindeks nilai dalam daftar tertaut.
   4. Menghapus/Menghapus setelah tertentu diindeks nilai dalam daftar tertaut.
   5. Menghapus pada posisi yang saat ini menunjuk pada daftar tertaut melingkar
5. Fungsi terakhir mencetak setiap elemen melalui traversal melingkar di status mana pun dari daftar tertaut.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
    
struct node *insertCurrent(struct node *last, int data)

Penjelasan kode:

1. Untuk kode addEmpty, alokasikan node kosong menggunakan fungsi malloc.
2. Untuk node ini, tempatkan datanya ke variabel temp.
3. Tetapkan dan tautkan satu-satunya variabel ke variabel temp
4. Kembalikan elemen terakhir ke konteks main()/aplikasi.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Penjelasan kode

1. Jika tidak ada elemen untuk disisipkan, maka Anda harus memastikan untuk menambahkan ke daftar kosong dan mengembalikan kontrol.
2. Buat elemen sementara untuk ditempatkan setelah elemen saat ini.
3. Tautkan petunjuk seperti yang ditunjukkan.
4. Kembalikan pointer terakhir seperti pada fungsi sebelumnya.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );


    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Penjelasan kode:

1. Jika tidak ada elemen dalam daftar, abaikan datanya, tambahkan item saat ini sebagai item terakhir dalam daftar dan kembalikan kontrol
2. Untuk setiap iterasi dalam perulangan do- while pastikan ada penunjuk sebelumnya yang menyimpan hasil yang terakhir dilintasi.
3. Hanya dengan demikian traversal berikutnya dapat terjadi.
4. Jika data ditemukan, atau suhu mencapai kembali ke penunjuk terakhir, do-sementara dihentikan. Bagian kode selanjutnya memutuskan apa yang harus dilakukan dengan item tersebut.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Penjelasan kode:

1. Jika seluruh daftar telah dilalui, namun item tidak ditemukan, tampilkan pesan “item tidak ditemukan” dan kemudian kembalikan kendali ke pemanggil.
2. Jika ada node yang ditemukan, dan/atau node tersebut belum menjadi node terakhir, maka buatlah node baru.
3. Link node sebelumnya dengan node baru. Tautkan node saat ini dengan temp (variabel traversal).
4. Hal ini memastikan bahwa elemen ditempatkan setelah node tertentu dalam daftar tertaut melingkar. Kembali ke penelepon.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Penjelasan kode

1. Untuk menghapus hanya node terakhir (saat ini), periksa apakah daftar ini kosong. Jika ya, maka tidak ada elemen yang dapat dihilangkan.
2. Variabel temp hanya melintasi satu tautan ke depan.
3. Tautkan penunjuk terakhir ke penunjuk setelah penunjuk pertama.
4. Bebaskan penunjuk suhu. Ini membatalkan alokasi penunjuk terakhir yang tidak tertaut.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Penjelasan kode

1. Seperti fungsi penghapusan sebelumnya, periksa apakah tidak ada elemen. Jika ini benar, maka tidak ada elemen yang dapat dihilangkan.
2. pointer ditugaskan posisi tertentu untuk menemukan elemen yang akan dihapus.
3. Petunjuknya maju, satu di belakang yang lain. (sebelumnya di belakang suhu)
4. Proses berlanjut hingga elemen ditemukan, atau elemen berikutnya menelusuri kembali ke penunjuk terakhir.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;	

Penjelasan program

1. Jika elemen ditemukan setelah menelusuri seluruh daftar tertaut, pesan kesalahan ditampilkan yang menyatakan bahwa item tidak ditemukan.
2. Jika tidak, elemen akan dilepaskan dan dilepaskan pada langkah 3 dan 4.
3. Pointer sebelumnya ditautkan ke alamat yang ditunjuk sebagai “berikutnya” oleh elemen yang akan dihapus (temp).
4. Oleh karena itu, penunjuk suhu tidak dialokasikan dan dibebaskan.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;    
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Penjelasan kode

1. Pengintipan atau traversal tidak dimungkinkan jika tidak diperlukan. Pengguna perlu mengalokasikan atau memasukkan sebuah node.
2. Jika hanya ada satu node, tidak perlu melakukan traverse, konten node dapat dicetak, dan perulangan while tidak dijalankan.
3. Jika ada lebih dari satu node, maka temp akan mencetak semua item hingga elemen terakhir.
4. Saat elemen terakhir tercapai, loop berakhir, dan fungsi mengembalikan panggilan ke fungsi utama.

Penerapan Daftar Tautan Melingkar

• Menerapkan penjadwalan round-robin dalam proses sistem dan penjadwalan melingkar dalam grafik berkecepatan tinggi.
• Penjadwalan token ring di jaringan komputer.
• Ini digunakan dalam unit tampilan seperti papan toko yang memerlukan traversal data secara terus menerus.