LINKED LIST
Linked list adalah sebuah data structure, suatu cara untuk mengalokasikan data. Pada array, kita menyimpan atau mereservasi beberapa memori yang saling bersebelahan untuk digunakan sebagai penyimpanan data. Namun, array memiliki kelemahan yang cukup mengganggu pada beberapa kasus. Contohnya, ketika kita membuat array yang akan menampung data berupa angka tapi kita tidak tahu seberapa banyak data yang akan disimpan. Biasanya, hal ini kita selesaikan dengan membuat ukuran array yang sangat besar. Namun, pada kenyataannya tidak semua kasus ketika kita menyimpan jumlah data sebesar ukuran array yang kita deklarasikan. Hal inilah yang membuat linked list sangat berguna. Tidak seperti array, linked list tidak harus megalokasikan data pada memori yang bersebelahan namun, dihubungkan oleh sebuah pointer dan dijadikan seperti list. Linked list biasa, juga sering disebut single linked list atau singly linked list. Pada linked list, elemen pertama atau node(sebutan yang diberikan oleh para programmer) pertama biasanya disebut sebagai head dan node terakhir disebut tail. Tiap elemen dihubungkan dengan pointer yang biasa dinamakan next. Semua node, dari head hingga tail dihubungkan dengan pointer next yang menunjuk alamat node berikut setelah node tersebut dan pointer yang menunjuk node setelah tail menunjuk ke NULL atau bisa dibilang tidak menunjuk ke apa-apa. Kelemahan dari single linked list ini adalah kita tidak bisa langsung membuka data yang kita inginkan karena informasi yang kita pegang hanyalah alamat dari head dan alamat node yang ditunjuk oleh node sebelumnya. Kelemahan single linked list lainnya adalah informasi alamat node yang kita tahu hanyalah alamat node yang sedang kita lihat dan alamat node berikutnya yang ditunjukkan pointer pada node saat ini. Contohnya, jika kita memiliki linked list: head->nodeA->nodeB->tail->NULL dan posisi kita sekarang ada pada nodeB, maka kita hanya bisa mengakses nodeB hingga tail.
1. Circular Single Linked List
Circular single linked list memiliki cara kerja yang sama persis seperti single linked list namun kita bisa lebih bebas dalam mengakses data. Jika pada single linked list akhir dari list tersebut dimana node terakhir atau tail memiliki pointer yang menunjuk ke NULL, maka pada circular single linked list pointer pada tail bukan menunjuk NULL, akan tetapi menunjuk alamat head. Pada circular single linked list juga, posisi dari head dan tail lebih fleksibel karena list tersebut terus terhubung dan tidak berujung sehingga patokan tersebut tidak diperlukan.
2. Doubly Linked List
Doubly linked list adalah linked list yang memungkinkan kita mengakses data pada node sebelumnya. Pada single linked list kita tidak bisa mengakses data pada node sebelumnya dan pada circular single linked list kita bisa mengakses data pada node sebelumnya hanya jika kita melakukan looping sehingga dibutuhkan waktu yang lebih lama untuk mengakses data pada node sebelum node yang sedang kita lihat. Bagaimana caranya sehingga doubly linked list ini bisa mengakses data sebelumnya? caranya adalah dengan menambahkan satu lagi pointer yang disebut prev(previous).
Jika pointer next menunjuk alamat node berikutnya, maka prev menunjuk node sebelumnya. pointer prev pada node pertama atau head menunjuk pada NULL.
3. Circular Doubly Linked List
Circular doubly linked list adalah doubly linked list yang pointer prev pada head menunjuk alamat tail dan pointer next pada tail menunjuk alamat head sehingga linked list tersebut saling terhubung.
Untuk source code dan penjelasan lebih lanjut ketiga linked list diatas bisa dilihat pada youtube:
a. Circular Doubly Linked List: https://youtu.be/zmoLA97B85Y
b. Circular Single Linked List: https://youtu.be/BFYLS0uPnJk
c. Doubly Linked List: https://youtu.be/elZQCUWSpbM
d. Linked List: https://youtu.be/Rs1KPyb9fHY
