Circular Single Linked List, Double Linked List, Circular Double Linked List

Circular Single Linked List
Circular single linked list adalah single linked list yang node terakhirnya bukan menunjuk ke NULL, melainkan menunjuk kearah node pertama. Cara membuatnya adalah sama dengan single linked list biasa tetapi setiap menambahkan node baru, pointer selanjutnya dari node tersebut mengarah ke node pertama.

Contoh penggunaan circular single linked list adalah untuk algoritma first in first out atau algoritma round-robin. Circular single linked list juga bisa dipakai untuk mengakses data yang membutuhkan mengakses node awal lagi setelah mencapai node terakhir. Contoh lainnya adalah game monopoli dimana bentuk permainannya hanya bisa pergi ke kota selanjutnya dan ketika mencapai kota terakhir maka akan mengulang lagi dari kota pertama. Circular single linked list akan dapat mempermudah proses tersebut.


Doubly Linked List
Doubly linked list adalah tipe linked list dimana setiap node mempunyai dua pointer, ke arah node selanjutnya dan ke arah node sebelumnya. Dengan begitu saat melakukan traversal di suatu linked list, bisa kembali ke node sebelumnya dibanding dengan single linked list yang hanya bisa sekali jalan. Cara membuat doubly linked list adalah dengan menambahkan satu pointer lagi pada struct node nya. Pointer ini harus menunjuk ke arah node sebelumnya. Kecuali untuk node pertama, maka pointer ke arah sebelumnya diisi dengan NULL dan untuk node terakhir, pointer ke arah selanjutnya diisi dengan NULL.

Contoh penggunaan dari doubly linked list adalah sistem undo dan redo. Dimana kita harus mengakses data yang sekarang dan bisa kembali ke sebelum dan sesudahnya dengan cepat. Jika sistem undo dan redo dilakukan dengan single linked list, maka dia harus mengulang lagi dari node pertama untuk kembali ke node sebelumnya.


Circular Doubly Linked List
Circular double linked list adalah gabungan antara doubly linked list dan circular linked list. Bentuknya adalah seperti doubly linked list biasa, tetapi hanya berbeda pada node awal dan akhirnya saja. Untuk node awal, pointer yang menunjuk node sebelumnya diisi dengan address dari node akhir bukan NULL seperti pada doubly linked list biasa. Pada node akhir pointer yang menunjuk node selanjutnya diisi dengan address dari node pertama yang seharusnya diisi dengan NULL juga pada doubly linked list. Dengan begitu seseorang bisa melakukan traversal ke depan dan kebelakang.

Contoh penggunan doubly linked list adalah seperti playback musik dimana kita bisa melakukan mengulang dari awal, memutar kedepan, dan memutar kebelakang. Dengan menggunakan doubly linked list, proses tersebut bisa dilakukan dengan mudah. Karena data tersebut memiliki insformasi ke dua arah dan mempunyai informasi untuk kembali ke awal setelah mencapai akhir. Data tersebut juga bisa diputar terbalik karena node awal memiliki informasi untuk ke node terakhir tanpa perlu adanya pointer tambahan.