LINKED LIST

Linked List

Dalam ilmu komputer, linked list adalah kumpulan elemen data linear, yang urutannya tidak mengikuti urutan penempatan fisiknya dalam memori. Melainkan, setiap elemen menunjuk ke yang berikutnya.

Kelemahan dari linked list adalah waktu akses yang linear dan sulit untuk disalurkan. Array memiliki lokalitas cache yang lebih baik dibandingkan dengan linked list.

Circular Singly Linked List

Circular singly linked list adalah jenis struktur data yang terdiri dari node yang dibuat menggunakan struktur referensial sendiri. Masing-masing node berisi ua bagian, yaitu data dan referensi ke list node berikutnya. Hanya referensi ke list node pertama yang diperlukan untuk mengakses seluruh linked list.

Circular Doubly Linked List

Circular doubly linked list adalah jenis struktur data yang lebih kompleks di mana sebuah node berisi pointer ke node sebelumnya serta node berikutnya. Circular doubly linked list tidak mengandung NULL di node manapun. Node terakhir dari list berisi address dari node pertama dari list. Node pertama dari daftar juga berisi address dari node terakhir di pointer sebelumnya.

Contoh penerapan Circular doubly linked list dalam C+/C:

// Structure of the node 
struct node
{
    int data;
    struct node *next; // Pointer to next node
    struct node *prev; // Pointer to previous node
};

 

Kelebihan dan kekurangan dari circular doubly linked list:

Kelebihan:

• List dapat dilalui dari kedua arah dari kepala ke ekor atau dari ekor ke kepala.
• Melompat dari kepala ke ekor atau dari ekor ke kepala dilakukan dalam waktu konstanO(1).
• Circular Doubly Linked Lists digunakan untuk implementasi struktur data tingkat lanjut.

Kekurangan;

• Dibutuhkan sedikit memori ekstra di setiap node untuk mengakomodasi pointer sebelumnya.
• Banyak petunjuk yang terlibat saat mengimplementasikan atau melakukan operasi dalam list. Jadi, pointer harus ditangani dengan hati-hati jika tidak data dari list dapat hilang.

Pengaplikasian;

• Mengatur playlist lagu.
• Mengatur keranjang belanja website shopping

Doubly Linked List

Doubly linked list adalah struktur linked data yang terdiri dari satu set sequentially linked records yang disebut node. Setiap node berisi dua bidang, yang disebut link, yang merupakan referensi ke node sebelumnya dan berikutnya di urutan node. Node awal dan akhir, link sebelumnya dan berikutnya, masing-masing, menunjuk ke semacam terminator, biasanya node sentinel atau nol, untuk memfasilitasi traversal daftar.

Contoh pengaplikasian node DLL dalam C+:

/* Node of a doubly linked list */struct Node {
    int data;
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

Kelebihan dan kekurangan DLL dibandingkan singly linked list:

Keuntungan lebih dari singly linked list

• DLL dapat dilintasi baik maju maupun mundur.
• Operasi hapus di DLL lebih efisien jika penunjuk ke simpul yang akan dihapus diberikan.
• Kita dapat dengan cepat menyisipkan simpul baru sebelum simpul yang diberikan.
• Dalam daftar tertaut tunggal, untuk menghapus sebuah simpul, diperlukan pointer ke simpul sebelumnya. Untuk mendapatkan simpul sebelumnya, terkadang daftar ini dilintasi. Dalam DLL, kita bisa mendapatkan simpul sebelumnya menggunakan pointer sebelumnya.

Kerugian dari daftar yang singly linked list

• Setiap node DLL Membutuhkan ruang ekstra untuk pointer sebelumnya.
• Dimungkinkan untuk mengimplementasikan DLL dengan pointer tunggal.
• Semua operasi memerlukan pointer ekstra sebelum dipertahankan. Misalnya, dalam penyisipan, kita perlu memodifikasi pointer sebelumnya bersama dengan pointer berikutnya. Misalnya dalam fungsi berikut untuk penyisipan di posisi yang berbeda, kita perlu 1 atau 2 langkah tambahan untuk mengatur pointer sebelumnya.

Credits to Wikipedia, https://www.java2novice.com/, https://www.geeksforgeeks.org/, https://www.javatpoint.com/, and HackerRank on Youtube