LINKED LIST - DATA STRUCTURES

LINKED LIST

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ciri utama linked list adalah dia mempunyai minimal dua elemen utama. Elemen itu adalah data don pointer untuk menunjukkan ke list berikutnya.

Ada beberapa macam Linked List, yaitu :

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

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Single linked list terdapat beberapa metode yang dapat dilakukan, yaitu:

1. Creation
2. Insert : Depan, Belakang, Posisi.
3. Delete : Depan, Belakang, Posisi.
4. Transversal
5. Sorting
6. Searching
7. Termination

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Ada 2 cara menghapus simpul double linked list :

1. Menghapus node di awal tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus. Kemudian head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru. Setelah itu barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Jika head masih NULL maka berarti data masih kosong.
2. Menghapus node di belakang tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus. Kemudian head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru. Setelah itu barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Jika head masih NULL maka berarti data masih kosong.

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

• Circular single linked list

Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

• Circular double linked list

Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.