LINKED LIST
Linked list adalah struktur data linier dimana elemen tidak di simpan di lokasi memori yang berdekatan. Elemen-elemen yang ada di Linked List di tautkan menggunakan pointer seperti yang di tunjukkan pada gambar berikut :
sederhananya, Liked list terdiri dari node dimana setiap node berisi sebuah bidang data dan sebuah referensi/tautan ke node selanjutnya yang ada pada daftar.
Sekarang kita akan membahas 3 topik yang terkait dengan Linked List, yaitu :
- Circular single linked list
- Doubly linked list
- Circular doubly linked list
1. Circular Single Linked List
Circular single linked list adalah suatu linked list yang tidak memiliki nilai NULL untuk medan sambungnya. Ringkasnya, node yang ada pada akhir circular single linked list akan berisi pointer yang akan menunjuk kepada node yang ada di awal/node pertama. Circular single linked list juga hanya memiliki pointer. Seperti ilustrasi yang dapat kita lihat di bawah ini :
pada gambar di atas, node paling akhir dari linked list tersebut memiliki pointer yang menunjuk dari dirinya sendiri (node terakhir) ke node awal/node pertama kembali.
2. Doubly Linked List
Doubly linked list adalah salah satu jenis linked list yang memiliki pointer 2 arah. Doubly linked list memiliki struktur data yang saling terkait. Linked list ini memiliki 2 link, satu berisikan referensi ke data selanjutnya dan yang datu lagi berisikan referensi ke data sebelumnya. Dengan kata lain, pada jenis linked list ini, memiliki 2 pointer penunjuk, 1 pointer menunjuk ke arah node sebelumnya dan yang satu lagi ke arah node setelahnya. Seperti yang bisa kita lihat pada gambar di bawah ini :
Dari gambar di atas, kita dapat melihat bahwa pada doubly linked list terdapat nilai NULL yang berada pada data terakhir/pada tail yang berguna sebagai pertanda data terakhir yang ada di linked tersebut. Doubly linked list berbeda dengan circular single linked list yang tidak memiliki nilai NULL di dalamnya.
contoh codingan linked list dapat dilihat di bawah :
struct Node {
int data;
struct Node* next; // Pointer to next node in Doubly Linked List
struct Node* prev; // Pointer to previous node in Doubly Linked List
};
Insertion
Dengan menggunakan Doubly Linked List, kita dapat menambahkan node dengan 4 cara :
- Pada bagian depan Doubly Linked List
- Setelah node yang di berikan
- Pada akhir Doubly Linked List
- Sebelum node di berikan
Contoh coding insertion pada bagian depan Doubly Linked List :
void push(struct Node* head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
Delete
Ada 4 kondisi yang harus kita perhatikan saat deleting node, yaitu :
- Node yang akan di delete adalah node satu-satunya di linked list
- Node yang akan di delete adalah awalan/head
- Node yang akan di delete adalah akhiran/tail
- Node yang akan di delete bukan head/tail
kita harus memperhatikan kondisi mana yang diinginkan saat kita ingin melakukan deleting pada Doubly Linked List.
Contoh :
(gambar linked list sebelum dilakukan tahap deleting)
(gambar linked list setelah dilakukan tahap deleting)
Dari kedua gambar di atas, kita dapat melihat bahwa yang ingin dihapus adalah node yang berada tidak di head ataupun tail linked list, melainkan node yang berada setelah awalan linked list.
3. Circular Doubly Linked List
Umumnya, Circular Doubly Linked List itu sama dengan Circular Single Linked List, bedanya terletak pada total pointer pada setiap node yang ada di Circular Doubly Linked List berjumlah 2 pointer.
Hal ini dapat kita lihat pada gambar di bawah :
Dari gambar di atas, kita dapat melihat perbedaan antara Circular Doubly Linked List dengan Circular Single Linked List.
Demikian rangkuman singkat tentang materi Linked List. Apabila ada kesalahan atapun kekurangan mohon dimaafkan dan beritahu saya di kolom komentar. Terima kasih. Sampai jumpa di materi selanjutnya....
Referensi :
thanks gan sudah share
BalasHapuslampu service hp