Skip to main content

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/

Comments

Post a Comment

Popular posts from this blog

Review

Single Linked List  merupakan suatu sistem penyimpanan dimana memori yang digunakan untuk penyimpanan digunakan secara dinamis (memori yang digunakan sesuai dengan ukuran dari data yang ditampung) Struktur Single Linked List (node) :  - Data yang ditmapung, dapat berupa : char,int, bool dan sebagainya - Pointer next   yang merefernce ke alamat node setelahnya Pendeklarasian: struct Mahasiswa{ char nama[20]; char nim[20]; struct Mahasiswa * next; }; Dalam  Single 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 Double Linked List  merupakana salah satu perkembangan dari single linked list yaitu penyimpanan data secara dinamis (menggunakan memori secukupnya) Struktur Double Linked List :  - Data yang ditampung, dapat berupa int , char , bool dan sebaginaya - Point
Post a Comment
Read more

Heap dan Trie

HEAP heap merupakan algoritma yang konsepnya hampir sama dengan Tree yaitu memilki satu buah root yang akan becabang menampung node node lain yang memliki datanya masing - masing. Heap memilki dua struktur, yaitu :  - Max Heap  merupakan heap yang rootnya mempunyai value terbesar dan menampung node node yang memilki nilai value yang lebih kecil. - Min Heap merupakan heap yang rootnya mempunyai value terkecil dan menampung node node yang lebih besar dari value si root. Pengimplementasian heap digunakan pada Heap Sort (Heapify) :  - Descending membentuk max heap dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terbesar di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted - Ascending membentuk  min heap  dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terkecil di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted Tries merupakan
Post a Comment
Read more

Hash Map dan BST

Hash Map adalah suatu array yang mempunyai sekumpulan data yang ditampung sesuai dengan index arraynya, karena menggunakan index sebagai acuan / patokan sehingga pencarian data menjadi lebih cepat Collision Karena hashmap hanya tergantung pada index sehingga dalam pemasukan data dapat mengalami istilah "collision" sehingga ada beberapa cara agar collision dapat dicegah yaitu :  1. Chaining : Jika data memilki hasil hashing yang sama maka index hashing tersebut akan dibuat menjadi sebuah linked list sehingga collision tidak dapat terjadi 2. Linear probling  adalah salah satu cara ketika memasukkan data ke hash mapnya tidak terjadi collision. Linear probling akan terjadi ketika pemasukkan data ke index tersebut tetapi index tersebut telah terisi dan akan terus mencari index yang kosong baru mengisi data tersebut Binary Search Tree adalah cara menampung data yang memanfaatkan konsep akar dan menggunakan suatu node sebagai patokan atau a
Post a Comment
Read more