Double Linked List

Doubly Linked List

Double linked list (DLL) adalah pengembangan dari Single Linked List (SLL) dimana terdapat tambahan fitur baru yaitu tambahan pointer baru yang disebut sebagai prev. 

Pada awalnya, Single Linked List (SLL) hanya mempunyai satu pointer penunjuk yaitu "next" dimana digunakan untuk menunjuk node berikutnya , sedangkan dengan menggunkan DLL, kita mereserve satu memori baru untuk membuat pointer yang menunjuk pada node sebelumnya yang sering dinamakan "prev".

Gambar menunjukkan DLL yang mereserve memori untuk tiga data yaitu, pointer untuk prev , pointer untuk next dan valuenya.

Dengan adanya bantuan "prev" dapat lebih memudahkan dalam memasukkan data secara terurut maupun dalam mencari node karena dapat dicompare dengan node sebelumnya maupun sesudahnya.

Pendeklarasian:

struct Mahasiswa{

char nama[20];

char nim[20];

struct Mahasiswa * next;

struct Mahasiswa * prev;

};

Dalam Doubly Linked list dapat dilakukan juga :

Insert, Delete maupun Update

Ada beberapa cara dalam menginsert node baru :
- Insert di awal (head)

- Insert di akhir (tail)

- Insert di next dari node yang ditunjuk

- Insert di prev dari node yang ditunjuk

Salah satu kelemahan dari DLL : 

- Memori yang digunkan lebih boros daripada SLL karena DLL mereserve memori untuk tiga hal yaitu pointer untuk prev dan next dan datanya, sedangkan (12 bytes = pointer "prev" + int + pointer "next") di SLL hanya membutuhkan dua memori yaitu pointer next dan datanya (8 bytes = int + pointer "next")

Note : 

- pointer "next" = 4 bytes, pointer "prev" = 4 bytes dan int = 4 bytes

- DLL : Double Linked List

- SLL : Single Linked List

Circular Single Linked List

Perbedaan antara ciruclar single linked list dan single linked list biasa terdapat di bagian tail.

Di bagian tail dari circular single linked list pointer "next" nya tidak akan menunjuk ke null melainkan akan menunjuk ke awal node (head) sehingga tidak terdapat node yang isinya null

Keuntungan : 

- Setiap node dapat dijadikan sebagai titik mulai (acuan)

- Pengimplementasian dalam queue lebih berguna karena pada saat kita melakukan "next" terus akan mendapatkan nilai sebelum dari node yang dijadikan acuan 

Circular Double Linked List

Perbedaan hampir sama seperti Circular Single Linked List dimana tidak akan ada nilai null di linked list tersebut. 

Di Circular Double Linked List, head akan memilki "prev"yang akan menunjuk pada tail dan tail akan memilki "next" yang akan menunjuk ke head 

Keuntungan :
- Linked list menjadi reversible
- Untuk pindah dari head ke tail maupun tail ke head lebih cepat dengan konstan waktu O(1)

Kekurangan :
- Membutuhkan memori lebih banyak dalam melakukan "prev"
- Banyak pointer yang dikaitkan sehingga dalam penggunaan pointer harus lebih teliti dan hati - hati

Contoh pengimplementasian :
- Menghandle pembuatan playlist lagu
- Menghandle shopping cart di online shop

Reference: 

Doubly Linked List
https://www.youtube.com/watch?v=JdQeNxWCguQ
https://www.geeksforgeeks.org/doubly-linked-list/

Circular Doubly Linked List dan Linked List
https://www.tutorialspoint.com/data_structures_algorithms/circular_linked_list_algorithm.htm
https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/