Sirkular list (atau circular linked list) adalah tipe struktur data yang mirip dengan linked list, tetapi dengan perbedaan bahwa elemen terakhir mengarah kembali ke elemen pertama, membentuk sebuah lingkaran. Ini berarti tidak ada elemen yang menunjukkan null, dan traversal dapat dimulai dari mana saja di list dan berakhir di titik yang sama.
Berikut adalah materi tentang sirkular list dalam bahasa pemrograman:
1. Pengertian Sirkular List
-Definisi: Sirkular list adalah tipe linked list di mana elemen terakhir menunjuk kembali ke elemen pertama, membentuk sebuah siklus.
- Jenis: Ada dua jenis sirkular list:
- Sirkular Singly Linked List: Setiap elemen memiliki satu penunjuk yang mengarah ke elemen berikutnya.
- Sirkular Doubly Linked List: Setiap elemen memiliki dua penunjuk, satu ke elemen berikutnya dan satu lagi ke elemen sebelumnya.
2. Struktur Data Sirkular List
Berikut adalah struktur data dasar untuk sirkular singly linked list dan sirkular doubly linked list:
- Circular Singly Linked List Node (C)
struct Node {
int data;
struct Node* next;
};
- Circular Doubly Linked List Node (C)
struct DNode {
int data;
struct DNode* next;
struct DNode* prev;
};
3. Operasi Dasar pada Sirkular List
a. Inisialisasi List
Inisialisasi list dengan menyiapkan pointer head.
-Singly Linked List (C)
struct Node* head = NULL;
- Doubly Linked List (C)
struct DNode* head = NULL;
b. Penambahan Elemen
Penambahan elemen di sirkular list dapat dilakukan di awal, akhir, atau setelah elemen tertentu.
- Tambah di Awal (Singly Linked List in C)
void addToEmpty(struct Node** head, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
*head = newNode;
newNode->next = *head;
}
void addAtBeginning(struct Node** head, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
struct Node* temp = *head;
while(temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
*head = newNode;
}
c. Penghapusan Elemen
Penghapusan elemen dari sirkular list juga dapat dilakukan di awal, akhir, atau elemen tertentu.
- Hapus Elemen (Singly Linked List in C)
void deleteNode(struct Node** head, int key) {
if (*head == NULL) return;
struct Node *temp = *head, *prev;
if (temp->data == key) {
while(temp->next != *head) {
temp = temp->next;
}
temp->next = (*head)->next;
free(*head);
*head = temp->next;
return;
}
while(temp->next != *head && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp->data == key) {
prev->next = temp->next;
free(temp);
}
}
d. Traversal
Traversal pada sirkular list melibatkan mengunjungi setiap elemen mulai dari head hingga kembali ke head.
- Traversal (Singly Linked List in C)
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
4. Kelebihan dan Kekurangan Sirkular List
- Kelebihan:
- Dapat mengakses semua elemen dari titik awal mana pun.
- Berguna dalam aplikasi yang memerlukan traversal berulang, seperti implementasi antrian melingkar.
- Kekurangan:
- Lebih kompleks dibandingkan linked list sederhana.
- Memerlukan penanganan khusus untuk menghindari loop tak terbatas.
5. Aplikasi Sirkular List
- Sistem Operasi: Digunakan dalam penjadwalan proses dengan round-robin scheduling.
- Buffer Melingkar: Digunakan dalam implementasi buffer melingkar (circular buffer).
- Permainan: Digunakan dalam permainan untuk memutar giliran pemain secara berurutan.
Dengan memahami konsep dasar, struktur data, operasi dasar, serta kelebihan dan kekurangan dari sirkular list, Anda dapat mengimplementasikan dan memanfaatkan struktur data ini dalam berbagai aplikasi yang memerlukan traversing elemen secara berulang atau melingkar.
Komentar
Posting Komentar