Circular Linked List: Keuntungan dengan Contoh Program C.

Daftar Isi:

Anonim

Apa itu Daftar Tertaut Melingkar?

Daftar tertaut melingkar adalah urutan node yang diatur sedemikian rupa sehingga setiap node dapat ditelusuri kembali ke node itu sendiri. Di sini "node" adalah elemen referensi sendiri dengan pointer ke satu atau dua node di sekitar iI'simediate.

Di bawah ini adalah gambaran daftar tertaut melingkar dengan 3 node.

Di sini, Anda dapat melihat bahwa setiap node dapat dilacak kembali ke dirinya sendiri. Contoh yang ditunjukkan di atas adalah daftar tertaut tunggal melingkar.

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

Dalam tutorial daftar tautan melingkar ini, Anda akan mempelajari:

  • Apa itu Daftar Tertaut Melingkar?
  • Operasi Dasar
  • Operasi Penyisipan
  • Operasi Penghapusan
  • Traversal dari Daftar Tertaut Melingkar
  • Keuntungan dari Circular Linked List
  • Daftar tertaut tunggal sebagai Daftar Tertaut Melingkar
  • Penerapan Daftar Tertaut Melingkar

Operasi Dasar

Operasi dasar pada daftar tertaut melingkar adalah:

  1. Insersi
  2. Penghapusan dan
  3. Traversal
  • Penyisipan adalah proses menempatkan node pada posisi tertentu dalam daftar tertaut melingkar.
  • Penghapusan adalah proses menghapus node yang ada dari daftar tertaut. Node dapat diidentifikasi dengan kemunculan nilainya atau dengan posisinya.
  • Traversal dari daftar tertaut melingkar adalah proses menampilkan seluruh konten daftar tertaut dan menelusuri kembali ke node sumber.

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

Operasi Penyisipan

Awalnya, Anda perlu membuat satu node yang mengarah ke node itu sendiri seperti yang ditunjukkan pada gambar ini. Tanpa node ini, penyisipan membuat node pertama.

Selanjutnya, ada dua kemungkinan:

  • Penyisipan pada posisi saat ini dari daftar tertaut melingkar. Ini sesuai dengan penyisipan di awal akhir dari daftar tertaut tunggal reguler. 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 dari daftar tertaut melingkar, yaitu pada posisi di mana node pertama kali ditambahkan,

  • Anda harus memutuskan tautan mandiri yang ada ke simpul yang ada
  • Penunjuk node baru berikutnya akan terhubung ke node yang sudah ada.
  • Penunjuk node terakhir selanjutnya akan mengarah ke node yang disisipkan.

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

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

(Node yang ada)

LANGKAH 1) Putuskan tautan yang ada

LANGKAH 2) Buat tautan maju (dari node baru ke node yang sudah ada)

LANGKAH 3) Buat link loop ke node pertama

Selanjutnya, Anda akan mencoba penyisipan setelah node.

Misalnya, mari kita masukkan "VALUE2" setelah node dengan "VALUE0". Mari kita asumsikan bahwa titik awal adalah node dengan "VALUE0".

  • Anda harus memutuskan garis antara node pertama dan kedua dan menempatkan node dengan "VALUE2" di antaranya.
  • Pointer berikutnya dari node pertama harus terhubung ke node ini, dan pointer berikutnya dari node ini harus terhubung ke node kedua sebelumnya.
  • Sisa pengaturan tetap tidak berubah. Semua node dapat dilacak kembali ke dirinya sendiri.

CATATAN: Karena ada pengaturan siklik, memasukkan node melibatkan prosedur yang sama untuk setiap node. Penunjuk yang menyelesaikan siklus menyelesaikan siklus seperti node lainnya.

Ini ditunjukkan di bawah ini:

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

LANGKAH 1) Hapus tautan dalam antara node yang terhubung

LANGKAH 2) Hubungkan node sisi kiri ke node baru

LANGKAH 3) Hubungkan node baru ke node sebelah kanan.

Operasi Penghapusan

Mari kita asumsikan daftar tertaut melingkar 3-node. Kasus untuk penghapusan diberikan di bawah ini:

  • Menghapus elemen saat ini
  • Penghapusan setelah elemen.

Penghapusan di awal / akhir:

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

(Setup yang sudah ada)

LANGKAH 1 ) Hapus tautan melingkar

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

LANGKAH 3) Bebaskan / hapus alokasi node pertama

Penghapusan setelah node:

  1. Lintasi sampai node berikutnya adalah node yang akan dihapus.
  2. Lintasi ke node berikutnya, letakkan pointer di node sebelumnya.
  3. Hubungkan simpul sebelumnya ke simpul setelah simpul sekarang, menggunakan penunjuk berikutnya.
  4. Bebaskan node saat ini (delink).

LANGKAH 1) Katakanlah kita perlu menghapus node dengan "VALUE1."

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

LANGKAH 3) Bebaskan atau hapus alokasi node saat ini.

Traversal dari Daftar Tertaut Melingkar

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

Keuntungan dari Circular Linked List

Beberapa keuntungan dari daftar tertaut melingkar adalah:

  1. Tidak ada persyaratan untuk penetapan NULL dalam kode. Daftar melingkar tidak pernah menunjuk ke pointer NULL kecuali dialokasikan sepenuhnya.
  2. Daftar terkait melingkar menguntungkan untuk operasi akhir karena awal dan akhir bertepatan. Algoritme seperti penjadwalan Round Robin dapat dengan rapi menghilangkan proses yang antri dalam mode melingkar tanpa menemui petunjuk yang menjuntai atau referensial NULL.
  3. Daftar tertaut melingkar juga menjalankan semua fungsi reguler dari daftar tertaut tunggal. Faktanya, daftar melingkar tertaut ganda yang dibahas di bawah ini bahkan dapat menghilangkan kebutuhan traversal panjang-penuh untuk menemukan sebuah elemen. Elemen itu paling banyak hanya akan berlawanan dengan awal, menyelesaikan hanya setengah dari daftar tertaut.

Daftar Tertaut Tunggal sebagai Daftar Tertaut Melingkar

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

#include#includestruct 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 perlu disertakan.
  2. Bagian selanjutnya menjelaskan struktur setiap node referensial sendiri. Ini berisi nilai dan penunjuk dengan tipe yang sama seperti struktur.
  3. Setiap struktur berulang kali menautkan ke objek struktur dengan tipe yang sama.
  4. Ada prototipe fungsi yang berbeda untuk:
    1. Menambahkan elemen ke daftar tertaut yang kosong
    2. Memasukkan pada posisi menunjuk saat ini dari daftar tertaut melingkar.
    3. Memasukkan setelah nilai indeks tertentu dalam daftar tertaut.
    4. Menghapus / Menghapus setelah nilai diindeks tertentu dalam daftar tertaut.
    5. Menghapus pada posisi menunjuk saat ini dari daftar terkait melingkar
  5. Fungsi terakhir mencetak setiap elemen melalui traversal melingkar di setiap status 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 data 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 penunjuk seperti yang ditunjukkan.
  4. Kembalikan penunjuk 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 kontrol kembali
  2. Untuk setiap iterasi dalam do-while loop, pastikan bahwa ada pointer sebelumnya yang menyimpan hasil traverse terakhir.
  3. Hanya dengan demikian traversal berikutnya dapat terjadi.
  4. Jika data ditemukan, atau temp mencapai kembali ke penunjuk terakhir, do-while berhenti. Bagian selanjutnya dari kode 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 kontrol ke pemanggil.
  2. Jika sudah ada node yang ditemukan, dan / atau node tersebut belum menjadi node terakhir, maka buat node baru.
  3. Tautkan node sebelumnya dengan node baru. Tautkan node saat ini dengan temp (variabel traversal).
  4. 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 bisa 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 ditautkan.
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 dihapus.
  2. Pointer diberikan 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 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 melintasi seluruh daftar tertaut, pesan kesalahan ditampilkan mengatakan item tidak ditemukan.
  2. Jika tidak, elemen akan dihapus tautannya dan dibebaskan pada langkah 3 dan 4.
  3. Pointer sebelumnya terhubung ke alamat yang ditunjuk sebagai "selanjutnya" oleh elemen yang akan dihapus (temp).
  4. Oleh karena itu, penunjuk suhu dibatalkan alokasinya 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. Peek atau traversal tidak mungkin dilakukan jika tidak ada yang dibutuhkan. Pengguna perlu mengalokasikan atau memasukkan node.
  2. Jika hanya ada satu node, tidak perlu melintasi, konten node dapat dicetak, dan loop sementara 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 Tertaut Melingkar

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