Struktur Data

Linked List

Linked List adalah bagian dari Struktur Data. Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimoan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node.

Pada linked list, terdapat istilah push, dan pop dimana push berarti insert data baru pada linked list tersebut, dimana kita bisa push dari depan(dimana data yang kita masukkan berada di paling depan linked list kita dan data yang kita masukkan tersebut menjadi head), belakang (dimana data yang kita masukkan akan berada di paling belakang linked list kita dan data yang kita masukkan tersebut menjadi tail) atau dari tengah( data yang kita masukkan bukan berada di head maupun tail, melainkan berada di tengah-tengah linked list). Sedangkan pop berarti mendelete data, data dari depan, tengah dan juga belakang. Pada linked list, head berarti yang paling depan pada linked list tersebut, sedangkan tail berarti data yang terakhir.

Pada linked list digunakan fungsi malloc, untuk memesan sebuah alamat memory. Pada saat penggunaan malloc itu sendiri, mungkin beberapa bertanya-tanya mengapa digunakan sizeof, tidak langsung saja misal int, langsung saja 4, tidak usah pake sizeof(int), jawabannya adalah agar dinamis, karena kita tidak pernah tau program kita akan dicompile di compiler apa, bisa saja 16 ataupun 32 bit, yang mengakibatkan jumlah byte nya berbeda-beda.

Didalam suatu linked list, dikenal 2 istilah yaitu head dan tail. Head adalah elemen yang berada pada posisi pertama dalam suatu linked list, sedangkan Tail adalah element yang berada pada posisis terakhir dalam suatu linked list.

Terdapat beberapa macam linked list, yaitu =

1.    Single Linked List

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

Pada single linked list, hanya terdapat satu panah(kita bisa akses dari head ke tail, tapi tidak bisa dari tail ke head). Untuk melakukan insert maka yang pertama kali harus kita lakukan adalah memesan tempat terlebih dahulu.Pada C, bisa menggunakan fungsi malloc yang diinclude dari library #include <stdlib.h>.

Selain menggunakan panah seperti potongan program diatas, bisa juga menggunakan .(dot) , contoh :

node->value=x; dapat menjadi *node->value=x;

Untuk mendelete/pop, hal pertama kali yang harus kita selamatkan adalah menyelamatkan head dan juga tail nya, selain itu juga pertama kali kita harus mencari apa yang ingin kita hapus, menghapus data tersebut dan juga menghubungkan data-data yang masih ada.

Pembuatan Single Linked List dapat menggunakan 2 metode:

–         LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

              Diibaratkan seperti ururtan dan juga memiliki konsep FIFO(first in first out), Elemen-elemen pada queue ditambahkan di belakang, dan di delete dari depan, sehingga ketika kita menggunakan linked list, saat memasukkan kita bisa menggunakan pushtail() dan dan untuk menghapus pophead() , dan juga bisa digunakan single linked list maupun double linked list.

–         FIFO (First In First Out), aplikasinya : Queue (Antrean)

              Diibaratkan seperti tumpukan, mis. tumpukan piring. Stack ini memiliki konsep LIFO(Last In First Out)/FILO(First In Last Out), Stack ini dapat dibuat dengan array maupun linked list. sehingga ketika kita ingin membuat stack dengan linked list(baik single maupun double), untuk memasukkan pushhead dan menghapus pophead atau untuk memasukkan dengan pushtail dan menghapus dengan poptail.

2.    Double Linked List

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

Perbedaan antara Single linked list dengan Double linked list adalah struktur tambahan dalam Double linked list bernama pointer prev yang digunakan untuk menunjuk elemen sebelumnya.

3.    Circular Linked List

Pada circular linked list, data/node pertama(head) akan terhubung dengan node/data terakhir(tail), sehingga akan membentuk pola seperti lingkaran. Pada circular linked list ini, maka tidak terdapat pointer yang menunjuk ke NULL, karena tail->next=head dan juga head->prev=tail(pada double linked list) atau hanya ada tail->next=head pada single linked list.

·      Circular Single Linked List

Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

·      Circular Double Linked List

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

4.    Multiple Linked List

Pada multiple linked list terdapat lebih dari 2 link. Salah satu terdapat pointer yang menunjuk kepada data selanjutnya lalu mungkin ada yang menunjuk kepada data sebelumnya, atupun juga menunjuk sebuah node tertentu.