Daftar Tautan Melingkar: Keuntungan dan Kerugian

Apa itu Daftar Tautan Melingkar?

Linked list melingkar adalah urutan node yang disusun sedemikian rupa sehingga setiap node dapat diakses kembali.tracsetiap “node” adalah elemen yang merujuk pada dirinya sendiri 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 diisi ulang.tracdapat berdiri sendiri. Contoh yang ditunjukkan di atas adalah daftar berantai tunggal melingkar.

Catatan: Daftar berantai melingkar paling sederhana adalah sebuah node tunggal yang penunjuk next-nya trackembali ke bentuk semula, seperti yang ditunjukkan di bawah ini.

Dasar Operations in Circular Linked Lists

Tiga operasi dasar pada linked list 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.
• Penelusuran daftar tertaut melingkar adalah proses menampilkan seluruh isi daftar tertaut dan seterusnya.trackembali ke node sumber.

Bagian selanjutnya menjelaskan cara kerja penyisipan dan dua jenis penyisipan yang mungkin dilakukan dalam linked list melingkar tunggal.

Insersi Operaproduksi

Pertama-tama, Anda membuat satu node yang pointer next-nya menunjuk kembali ke dirinya sendiri, seperti yang ditunjukkan di bawah ini. Tanpa node awal ini, penyisipan pertama akan menjadi node pertama dalam daftar.

Selanjutnya ada dua kemungkinan:

• Penyisipan pada posisi saat ini dari linked list melingkar. Ini sesuai dengan penyisipan di awal atau di akhir linked list tunggal biasa — dalam linked list melingkar, awal dan akhir adalah titik yang sama.
• Penyisipan setelah node yang diindeks. Node harus diidentifikasi dengan nomor indeks yang sesuai dengan nilai elemennya.

Untuk menyisipkan elemen di awal atau akhir linked list melingkar — yaitu, pada posisi di mana node pertama kali ditambahkan — ikuti langkah-langkah di bawah ini:

• 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: Pointer yang menandai awal atau akhir lingkaran dapat ditetapkan ulang ke node mana pun. Penelusuran tetap akan kembali ke node yang sama, seperti yang akan dibahas lebih lanjut dalam artikel ini.

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.

Sebagai contoh, sisipkan “VALUE2” setelah node yang berisi “VALUE0”, dengan asumsi titik awalnya adalah node dengan “VALUE0”.

• Putuskan hubungan antara node pertama dan kedua, lalu tempatkan node dengan “VALUE2” di antaranya.
• Pointer next dari node pertama mengarah ke node baru, dan pointer next dari node baru mengarah ke node yang sebelumnya merupakan node kedua.
• Susunan lainnya tetap tidak berubah. Semua node diatur ulang.tracmampu mengurus diri mereka sendiri.

CATATAN: Karena susunannya bersifat siklik, prosedur untuk memasukkan node sama saja terlepas dari posisi mana yang Anda pilih. Pointer yang menutup siklus berperilaku seperti pointer lainnya dalam daftar.

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

Misalkan sebuah linked list melingkar dengan 3 node. Dua kasus penghapusan tersebut adalah:

• Menghapus elemen saat ini
• Penghapusan setelah suatu elemen.

Penghapusan di awal/akhir:

1. Melintasi node pertama dari node terakhir.
2. Penghapusan dari akhir hanya memerlukan satu langkah penelusuran, dari node terakhir ke node pertama.
3. Hapus tautan antara node terakhir dan node pertama.
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. Telusuri 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, lalu tautkan node sebelumnya secara langsung ke node yang ditunjuk oleh pointer next dari node saat ini (node ​​setelah VALUE1).

Langkah 3) Bebaskan atau batalkan alokasi node saat ini.

Penjelajahan Daftar Tertaut Melingkar

Untuk menelusuri linked list melingkar dari pointer terakhir, pertama-tama periksa apakah pointer terakhir bernilai NULL. Jika tidak NULL, periksa apakah list hanya memiliki satu elemen. Jika tidak, telusuri list dengan pointer sementara hingga Anda mencapai pointer terakhir lagi, seperti yang ditunjukkan pada animasi 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 berantai melingkar menguntungkan untuk operasi akhir daftar karena awal dan akhirnya bertepatan. Algorithms Misalnya, penjadwalan round-robin dapat memproses proses yang diantrekan dengan lancar, tanpa menemui pointer yang mengambang atau NULL.
3. Daftar berantai melingkar tetap mendukung semua operasi reguler dari daftar berantai tunggal. Sebuah daftar berantai melingkar daftar tertaut ganda Bahkan dapat menghilangkan kebutuhan untuk melakukan penelusuran penuh untuk menemukan suatu elemen — dalam kasus terburuk, target berada di seberang penunjuk awal, sehingga paling banyak setengah dari daftar perlu ditelusuri.

Kekurangan Daftar Tertaut Melingkar

Kerugian dalam menggunakan daftar tertaut melingkar adalah sebagai berikut:

1. Daftar melingkar lebih kompleks daripada daftar tertaut tunggal.
2. RevMembalik daftar melingkar lebih kompleks daripada membalik daftar berantai tunggal atau ganda.
3. Jika penghentian loop tidak ditangani dengan hati-hati, kode penelusuran dapat memasuki loop tak terbatas.
4. Lebih sulit untuk menemukan akhir daftar dan menulis kondisi kontrol perulangan yang benar.
5. Penyisipan di awal memerlukan penelusuran seluruh daftar untuk mencapai node terakhir (dari perspektif implementasi).

Daftar Tertaut Tunggal sebagai Daftar Tertaut Melingkar

Anda disarankan untuk membaca dan mengimplementasikan kode C di bawah ini. Kode tersebut mengilustrasikan aritmatika pointer yang terkait dengan linked list tunggal 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 mendefinisikan struktur dari setiap node yang merujuk pada dirinya sendiri. Bagian ini berisi sebuah nilai dan sebuah pointer dengan tipe yang sama seperti struktur tersebut.
3. Setiap instance struktur terhubung ke objek struktur lain 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 addToEmpty, alokasikan node kosong menggunakan fungsi malloc().
2. Tempatkan data yang masuk ke dalam node sementara.
3. Tetapkan node sementara ke posisi terakhir dan atur penunjuk berikutnya ke dirinya sendiri sehingga node tunggal tersebut menunjuk kembali ke dirinya sendiri.
4. Kembalikan pointer terakhir ke fungsi main() / konteks 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 daftar kosong, serahkan ke addToEmpty() dan kembalikan kendali.
2. Buat node sementara untuk ditempatkan setelah node saat ini.
3. Hubungkan titik-titik penunjuk seperti yang ditunjukkan pada diagram di atas.
4. Mengembalikan pointer terakhir yang sesuai dengan pola yang digunakan 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 daftar kosong, abaikan kata kunci pencarian, tambahkan item saat ini sebagai satu-satunya node dalam daftar, dan kembalikan kendali.
2. Dalam setiap iterasi loop do-while, pointer sebelumnya menyimpan hasil terakhir yang dilalui.
3. Barulah kemudian langkah penelusuran selanjutnya terjadi.
4. Perulangan do-while berakhir ketika data target ditemukan atau ketika variabel temp mencapai pointer terakhir lagi. Blok kode berikut menentukan apa yang harus dilakukan dengan item yang ditemukan.

...
    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 ditelusuri tetapi item tidak ditemukan, tampilkan pesan "Elemen tidak ditemukan" dan kembalikan kendali ke pemanggil.
2. Jika node target ditemukan, alokasikan node baru untuk nilai yang akan disisipkan.
3. Link Hubungkan node sebelumnya ke node baru, dan hubungkan pointer next dari node baru ke temp (variabel traversal).
4. Ini menempatkan elemen baru tepat setelah node target dalam daftar tertaut melingkar. Kontrol kemudian kembali ke pemanggil.

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 node terakhir (saat ini), pertama-tama periksa apakah daftar tersebut kosong. Jika kosong, tidak ada elemen yang dapat dihapus.
2. Variabel sementara memajukan satu tautan ke depan.
3. Hubungkan penunjuk terakhir ke node setelah node pertama.
4. Bebaskan pointer sementara untuk membatalkan alokasi node yang tidak terhubung.

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, pertama-tama periksa apakah daftar tersebut kosong. Jika kosong, tidak ada elemen yang dapat dihapus.
2. Dua pointer ditugaskan posisi tertentu untuk menemukan elemen yang akan dihapus.
3. Penunjuk-penunjuk tersebut digerakkan satu demi satu (jejak sebelumnya suhu).
4. Penelusuran berlanjut hingga elemen target ditemukan atau penunjuk berikutnya mencapai simpul terakhir lagi.

    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 seluruh linked list ditelusuri tanpa menemukan target, pesan “Elemen tidak ditemukan” akan ditampilkan.
2. Jika tidak, elemen tersebut akan dilepas tautannya dan dibebaskan pada langkah 3 dan 4.
3. Pointer sebelumnya terhubung ke node yang ditunjuk oleh pointer berikutnya dari temp (node ​​setelah node yang dihapus).
4. Pointer sementara kemudian 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. Penelusuran intip tidak mungkin dilakukan jika tidak ada node — pengguna harus terlebih dahulu mengalokasikan atau memasukkan node.
2. Jika hanya ada satu node, tidak diperlukan penelusuran — isi node dicetak langsung dan loop while tidak dieksekusi.
3. Jika terdapat lebih dari satu node, sementara akan mencetak setiap item hingga elemen terakhir.
4. Saat elemen terakhir tercapai, perulangan berakhir dan fungsi mengembalikan kendali ke main().

Penerapan Daftar Tautan Melingkar

• Menerapkan penjadwalan round-robin dalam proses sistem dan penjadwalan melingkar dalam grafik berkecepatan tinggi.
• Penjadwalan token-ring dalam jaringan komputer.
• Digunakan pada unit tampilan seperti papan toko digital yang membutuhkan penelusuran data secara terus menerus.

Pertanyaan Umum Demo Slot