LINKED LIST
Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence (urutan). Dalam membuat Linked list kita harus mengalokasikan memori dengan menggunakan fungsi malloc pada header file stdlib.h.
Ada beberapa macam Linked List, yaitu :
- Single (Singly) Linked List.
- Double (Doubly) Linked List.
- Circular Single (Singly) Linked List.
- Circular Double (Doubly) Linked List.
1. Single Linked List
- Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai Single Linked List.
- Di dalam Single Linked List, ada 1 pointer yang menjadi gambaran besar, yakni pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri.
- Single Linked List dikatakan kosong apabila isi pointer head adalah NULL.
- Push
Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert melalui depan (pushDepan) ataupun belakang (pushBelakang). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya, dan sebaliknya pushBelakang berarti data yang paling baru akan berada di belakang data lainnya.
Representasinya adalah sebagai berikut:
pushDepan: 1, 2, 3, 4 maka hasilnya adalah: 4 ->3 ->2 -> 1 -> NULL
pushBelakang: 1, 2, 3, 4 maka hasilnya adalah: 1 ->2 ->3 ->4 -> NULL
2. Pop
Pop merupakan operasi delete yang digunakan untuk menghapus suatu data dalam Single Linked List. Dalam penerapan code Single Linked List, umumnya hanya digunakan pointer head sebagai pointer yang menunjuk pada linked list. Namun dalam pembahasan blog ini akan digunakan 1 pointer tambahan, yakni TAIL untuk menunjuk data terakhir di dalam linked list dalam mempermudah proses pembahasan.
Langkah pertama dalam membuat Single Linked List yaitu membuat atau mendeklarasikan Struct seperti gambar dibawah ini.
Langkah pertama dalam membuat Single Linked List yaitu membuat atau mendeklarasikan Struct seperti gambar dibawah ini.
Berikut ini adalah contoh potongan source code pushDepan dalam Single Linked List.
Berikut ini adalah contoh potongan source code pushBelakang dalam Single Linked List.
Berikut ini adalah contoh potongan source code Pop dalam Single Linked List.
Untuk melihat data dalam Single Linked List yang telah dibuat, biasanya membuat sebuah operasi untuk menampilkan data seperti pada potongan source code berikut.
2. Double Linked List
Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next yang menunjuk ke node sebelum dan node sesudahnya.
Keuntungan menggunakan Double Linked List yaitu:
- Double Linked List dapat melintasi dari depan ke belakang atau sebaliknya.
- Dalam Double Linked List, operasi untuk menghapus data lebih efisien jika diberikan pointer pada node yang ingin dihapus.
- Insert node yang baru dapat lebih cepat sebelum node diberikan. Pada Double Linked List, kita dapat mencari node yang sebelumnya menggunakan pointer prev.
Kekurangan menggunakan Double Linked List yaitu:
- Setiap node pada Double Linked List membutuhkan tempat yang lebih banyak untuk pointer yang sebelumnya.
- Semua operasi pada Double Linked List membutuhkan pointer yang ekstra. Contohnya pada operasi insert, kita harus mercancang prev pointer bersamaan dengan next pointer
Sama seperti pada Single Linked list, Double Linked List juga terdapat operasi Push, dan Pop. Langkah pertama dalam membuat Double Linked List yaitu membuat atau mendeklarasikan Struct seperti gambar dibawah ini. Struct pada Double Linked list mirip dengan struct yang telah kita buat pada Single Linked List, hanya saja, pada Double Linked list ditambahkan dengan pointer prev.
Berikut ini adalah contoh potongan source code untuk melakukan operasi Push depan pada Double Linked List.
Berikut ini adalah contoh potongan source code untuk melakukan operasi push belakang pada Double Linked List.
Berikut ini adalah contoh potongan source code untuk melakukan operasi pop.
Dalam Double Linked List, untuk menampilkan data yang telah dibuat dapat dibedakan menjadi 2 bagian yaitu menampilkan data dari depan atau menampilkan data dari belakang.
Berikut adalah potongan source code untuk menampilkan data dari depan.
Sedangkan berikut ini adalah potongan source code untuk menampilkan data dari belakang.
3. Circular Single Linked List
- Pada Circular Single Linked List, node terakhir mengandung sebuah pointer yang menunjuk ke node pertama (node terakhir yaitu tail menunjuk ke head sehingga terhubung).
- Pada Circular Single Lingked List, tidak terdapat NULL pada datanya.
Circular Double Linked List mirip dengan Circular Single Linked list, hanya saja total pointernya pada setiap node sebanyak 2 pointer. pointer prev pada head menunjuk kepada node yang terakhir (tail) sedangkan pointer pada node terakhir yaitu tail menunjuk kepada head.
Tidak ada komentar:
Posting Komentar