Linked-list Explained

The drawing of list {1, 2, 3}

Linked-list dan array memiliki kesamaan, menyimpan data collection. Secara terminologi yang membedakan array dan linked-list hanya cara menyimpan “elemen”. Salah satu cara memahami materi ini dengan melihat bagaimana cara array bekerja untuk diterapkan ke linked-list.

1. Introduction to linked list
2. Difference between linked-list and array
3. Linked-list operations
4. Linked-list other implementations

1. Introduction to linked-list

Lanjutan dari penjelasan singkat diatas, yang membedakan kemiripan linked-list dan array adalah bagaimana cara data disimpan, linked-list disimpan di dalam heap, tetapi bagaimana bisa membentuk linear seperti array? mudahnya kita bisa bayangkan node-node yang telah teralokasi pada memori dikaitkan hingga menjadi chain of nodes, saling menunjuk melalui pointer variable. Yang membuat unik dari linked-list, node tersebut harus memiliki informasi node tetanggnya cukup dengan address node lain, langsung mengarah ke blok memorinya.

Sekumpulan node yang diberi informasi penunjuk

Dari visualisasi diatas, kumpulan data yang diberi arti menyerupai array dengan menunjuk satu ke lain, terciptalah linear data structure linked-list.

2. Difference between Linked-list and Array

Karena data structure diciptakan untuk mengatasi limitasi penggunaan, linked-list jika disandingkan dengan array mempunyai keunggulan dan kekurangan.

Advantages

• Easy insert operation, tidak berunut seperti array (non-contiguous memory) hanya data yang diperlukan berada di data structure.
• Dynamic size, kita bebas menambah atau mengurangi data tanpa terbatas static memory allocation (resource efficiency).

Disadvantages

• Bad accessing operation, kompleksitas O(n) harus mengiterasi linked-list hingga mendapat data yang kita mau.
• Extra memory untuk menyimpan informasi node tetangganya.

3. Linked-list operations

1. Push
   Insert operation pada linked-list, memasukan node baru ke untaian pada 3 macam posisi, head (awal untaian), tail (akhir untaian), dan middle (antara head dan tail). Take note ketika linked-listnya kosong dan posisi insertnya pada salah satu ujung untaian.
2. Pop
   Delete operation pada linked-list, menghapus node yang berada untaian di 3 macam posisi, head (awal untaian), tail (akhir untaian), dan middle (antara head dan tail).
3. View
   Access operation pada linked-list, mengiterasi node ke node lain berdasar informasi node sekarang, (Node 1 -> Node n) sampai ujung linked-list.

Berikut adalah code/implementasinya.

Doubly Linked-list

4. Linked-list other implementations

1. Singly Linked-list (each node has one next pointer variable to another node)
2. Doubly Linked-list (each node has previous and next pointer variable to another node)
3. Multiple Linked-list (each node has many pointer variables to another node)
4. Circular Linked-list (daripada assign next pointer ke NULL, point kan ke head atau node lain pada linked-list)

References

Linked List Basics — http://cslibrary.stanford.edu/103/