DATA STRUCTURE

LINKED LIST

linked list adalah salah satu bentuk struktur data yang berisi kumpulan data/elemen (node) yang saling terhubung atau sambung menyambung 

(tidak boleh putus) dan sangat dinamis dimana elemennya dapat ditambahkan atau dihapus dimana saja. linked list saling terhubung dengan bantuan pointer. Sebuah linked list dikatakan losing apabila isi pointer head adalah NULL.

linked list berbeda dengan array. Perbedaannya adalah array merupakan kumpulan linear elemen data dan menyimpan nilainya di lokasi memori berturut-turut juga data diakses secara acak. Sedangkan linked list merupakan kumpulan node node, tidal menyimpan node dilokasi memori secara berturut-turut dan haya data divises secara berurutan.

• SINGLE LINKED LIST

Single linked list merupakan rangkaian yang tanya memiliki satu arah sebagai penghubungnya. Single linked list diawali dengan sebuah head yang menyimpan alamat awal dan diakhiri dengan node yang mengarah ke NULL.  

Berikut beberapa operasi yang biasa ada di dalam sebuah single linked list :

• PUSH / INSERT

Pop atau Insert merupakan operasi menambahkan data. Dalam linked list anda bisa menambahkan data di depan atau di tengah ataupun di belakang. Untuk insertDepan artinya data yang baru ditambahkan akan berada di depan data lainnya yang berarti juga headnya ialah data yang baru ditambahkan, sebelum headnya  dipindahkan ke data yang baru tersebut hubungkan terlebih dahulu data yang mau ditambahkan dengan data yang sudah ada setelah itu baru headnya dipindahkan ke data paling depan.

Untuk insertMid (insert tengah) artinya data akan ditambahkan akan berada diantara dua data yang sudah ada, caranya adalah dengan menghubungkan dulu data sebelum(1) dengan data yang baru setelah itu hubungkan data yang baru dengan data sesudahnya(2). Sedangkan insertLast artinya data yang baru ditambahkan akan berada di belakang data lainnya, pertama hubungkan data terakhir dengan data yang baru setelah itu hubungkan data yang baru dengan NULL. Karena dalam linked list data terakhir selalu terhubung dengan NULL. 

• POP / DELETE

Pop atau delete merupakan operasi menghapus data. Dalam linked list data bisa di hapus dari depen, tengah ataupun belakang. Untuk menghapus data yang berada di depan (head) kita free(head) detelah itu headnya di pindahkan ke data yang paling awal. untuk menghapus data yang ada di tengah kita harus menghubungkan dulu data sebelum data yang ingin di hapus dengan data setelah data yang ingin di hapus setelah itu kita free data yang ingin di hapus. sedangkan untuk menghapus data terakhir hubungkan dulu data sebelum data yang akan dihapus dengan NULL setelah itu free data yang ingin dihapus.

Misalnya, sudah ada data 10(head) ➞ 20 ➞ 30 ➞ 40 ➞ NULL 

data yang ingin ditambahkan adalah 78. maka :

insertDepan hasilnya :   78 ➞ 10(head) ➞ 20 ➞ 30 ➞ 40 ➞ NULL

                                       78(head) ➞ 10 ➞ 20 ➞ 30 ➞ 40 -➞ NULL

indrtMid hasilnya :    10(head) ➞ 20 ➞ 30 ➞ 78  40 ➞ NULL

                                   10(head) ➞ 20 ➞ 30 ➞ 78 ➞ 40 ➞ NULL

insertLast hasilnya :    10(head) ➞ 20 ➞ 30 ➞ 40 ➞ 78 NULL

                                    10(head) ➞ 20 ➞ 30 ➞ 40 ➞ 78 ➞ NULL

data yang ingin dihapus adalah 10.

delFront hasilnya :    (head) ➞ 20 ➞ 30 ➞ 40 ➞ NULL

                                  20 (head) ➞ 30 ➞ 40 ➞ NULL

data yang ingin dihapus adalah 30.

delMid hasilnya :     10(head) ➞ 20  30 ➞ 40 ➞ NULL

                                                        └──┘

                                                 (hubungkan 20 dengan 40)

                                 

data yang ingin dihapus adalah 40.

delLast hasilnya :     10(head) ➞ 20 ➞ 30  40 ➞NULL

                                                                  └──┘

                                                        (hubungkan 30 dengan NULL)

                                 10(head) ➞ 20 ➞ 30 ➞ NULL 

• DOUBLE LINKED LIST

Double linked list mirip dengan single linked list, bedanya double linked list memiliki 2 pointer petunjuk arah, yakni kearah node sebelumnya (previos/prev) dan kearah setelahnya (next). 

Jika pada single linked list hanya head maka pada double linked list ada head dan tail, head untuk menyimpan alamat node awal  dan tail untuk menyimpan alamat node terakhir. pada double linked list, head dan tail selalu terhubung dengan NULL (seperti gambar diatas).

Berikut beberapa operasi yang biasa ada di dalam sebuah double linked list : 

• PUSH / INSERT

Sama seperti di single linked list, kita bisa insert dari depan, tengah ataupun belakang. Perhatikan contoh.

Misalnya,  sudah ada data  NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL 

data yang ingin ditambahkan adalah 78. maka :

                    (hubungkan (next) 78 dengan 10)

                                        ┌┐ 

insertDepan :     NULL  78 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL 

                                        └┘

                    (hubungkan (prev) 10 dengan 78)

                           NULL  78(head) ⇄ 10 ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL

                           NULL ← 78(head) ⇄ 10 ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL

                (hubungkan (next) 20 dengan 78)     (hubungkan (prev) 30 dengan 78)

                                                               ┌┐┌┐

insertMid :     NULL ← 10(head) ⇄ 20    78  30 ⇄ 40(tail) ➞ NULL 

                                                               └┘└┘

                (hubungkan (prev) 78 dengan 20)     (hubungkan (next) 78 dengan 30)

                       NULL ← 10(head) ⇄ 20 ⇄ 78 ⇄ 30 ⇄ 40(tail) ➞ NULL 

                                                                   (hubungkan (next) 40 dengan 78)

                                                                                    ┌──┐ 

insertLast :      NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) 78 NULL

                                                                                    └──┘

                                                                   (hubungkan (prev) 78 dengan 40)

                        NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ⇄ 78 NULL

                       

                        NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 78 (tail) NULL

    

                        NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 78 (tail) ➞ NULL

• POP / DELETE

Sama seperti di single linked list, kita bisa delete dari depan, tengah ataupun belakang. Perhatikan contoh.

Misalnya,  sudah ada data  NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL 

data yang ingin dihapus adalah 10

delFront :     NULL  (head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL 

                     NULL  20(head) ⇄ 30 ⇄ 40(tail) ➞ NULL 

                     NULL ← 20(head) ⇄ 30 ⇄ 40(tail) ➞ NULL 

data yang ingin dihapus adalah 30

                                              (hubungkan (next) 20 dengan 40)

                                                          ┌────┐

delMid :      NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL

                                                          └────┘

                                              (hubungkan (prev) 40 dengan 20)

                    NULL ← 10(head) ⇄ 20 ⇄  40(tail) ➞ NULL

data yang ingin dihapus adalah 40

                                                          (hubungkan (next) 30 dengan NULL)

                                                                     ┌──────┐       

delLast :      NULL ← 10(head) ⇄ 20 ⇄ 30 ⇄ 40(tail) ➞ NULL

                    NULL ← 10(head) ⇄ 20 ⇄ 30 ➞ NULL

  

                    NULL ← 10(head) ⇄ 20 ⇄ 30(tail) ➞ NULL

Referensi :

https://medium.com/codelabs-unikom/struktur-data-single-linked-list-93bbd56b6ed1

https://socs.binus.ac.id/2017/03/15/single-linked-list/

https://socs.binus.ac.id/2017/03/15/doubly-linked-list/

http://brawlyvonfabre.blogspot.com/p/single-linked-list.html