Linked List

PENGERTIAN LINKED LIST

• Linked list adalah sebuah struktur data linear yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan).

• Perbedaan linked list dan array adalah pada lokasi penempatan elemen, dimana pada linked list elemen tidak ditempatkan di lokasi memori yang berdekatan dan elemen-elemen tersebut dihubungkan dengan pointer.
• Terdapat beberapa macam linked list:

1. Circular Single Linked List
2. Doubly Linked List
3. Circular Doubly Linked List

1. Circular Single Linked List

• Circular Single Linked List adalah Single Linked List yang pointer nextnya kembali menunjuk pada head linked list tersebut, sehingga terbentuk sebuah siklus berulang.
• Tidak ada storing nilai NULL pada linked list.

2. Doubly Linked List

• Doubly Linked List adalah sebuah tipe linked list yang kompleks dimana node mengandung pointer yang menunjuk ke node sebelumnya serta node berikutnya dalam sebuah urutan.

• Terdapat beberapa fungsi yang dapat dijalankan pada Double Linked List:
• Insert

• Insert dapat dilakukan dalam beberapa situasi berikut:

1. Add a node at the front

Node baru selalu ditambahkan sebelum head dari Linked List yang diberikan.

2. Add a node after a given node

Pointer ditandai ke node sebagai prev_node dan node yang baru ditambahkan setelah given node.

3. Add a node at the end

Node baru selalu ditambahkan setelah last node dari given linked list.

• Delete

• Tahapan dari delete linked list antara lain:
1. Find previous node of the node to be deleted
2. Change the next of previous node
3. Free memory for the node to be deleted
• Delete Linked List dapat dilakukan di beberapa situasi:
1. If the node to be deleted is the only node
2. If the node to be deleted is head
3. If the node to be deleted is tail
4. If the node to be deleted is not in head or tail

3. Circular Doubly Linked List

• Sama seperti circular single linked list, tetapi seluruh node (masing-masing nya) memiliki 2 (two) pointers.