Linked List

Linked list adalah sebuah struktur data yang terdiri atas urutan data-data yang di tiap datanya memiliki referensi untuk data berikutnya atau sebelumnya dalam suatu urutan data.

Ilustrasi Linked List

Linked list pada umumnya digunakan untuk menampung data-data, sehingga memiliki fungsi yang mirip dengan Array. Namun, antara kedua hal tersebut terdapat hal-hal yang menjadi pembeda, yaitu :

• Pada array, ukuran array sudah ditentukan saat dideklarasikan sehingga menggunakan memori yang tetap dan tidak bisa berubah ukurannya. Sedangkan pada linked list, memori yang digunakan tergantung jumlah data yang dimasukkan. Memori akan terpakai atau tersedia hanya saat penambahan atau pengurangan data. Sehingga linked list lebih dinamis.
• Pada array, data disimpan di lokasi memori yang berurutan satu dengan yang lain. Sedangkan pada linked list lokasi penyimpanan data tidak secara berurutan.
• Pada array, bisa dilakukan pengaksesan data secara acak karena kita dapat mengakses secara langsung dengan memasukkan index yang diinginkan. Sedangkan pada linked list tidak dapat dilakukan pengaksesan data secara acak karena mengikuti urutan sequence (looping).

Linked list biasanya digunakan untuk memecahkan masalah secara real-time karena cirinya yang mengalokasikan memori seiring program berjalan, hal ini penting agar program yang dijalankan tidak mengalami kendala performa akibat memori penuh yang disebabkan data tidak terpakai. Linked list menggunakan tipe data pointer untuk referensi antar datanya. Posisi dalam suatu linked list ditandai dengan adanya posisi head yang merujuk pada posisi data paling awal dan tail yang merujuk pada posisi data paling akhir.

Linked list terdiri atas 2 metode, yaitu Insert/Push yang merupakan penambahan rekor data/node dan Delete/Pop yang merupakan penghapusan rekor data/node dalam suatu linked list.

Ada 2 jenis linked list yaitu :

Single Linked List

Single Linked List adalah jenis linked list yang memiliki hubungan satu arah sebagai referensi antar datanya. Hubungan antar data direpresentasikan dengan adanya pointer next yang menunjuk data di posisi berikutnya.

Diagram Single Linked List

Pada Single Linked List proses Insert data harus memperhatikan dimana data akan dimasukkan. Pada umumnya dilakukan Insert Head (data dimasukkan di posisi paling awal) dan Insert Tail (data dimasukkan di posisi paling akhir). Hal yang harus diperhatikan adalah untuk tidak lupa memindahkan posisi head dan tail ke posisi yang sesuai, jika Insert head maka posisi head digeser ke ujung kiri dan jika Insert tail maka posisi tail digeser ke kanan. Setiap kali ada penambahan data jangan lupa lakukan tail->next = NULL agar tidak terjadi error looping selamanya.

Untuk metode Delete, hal yang harus diperhatikan adalah tentukan node mana yang ingin dihapus. 

Posisi yang diperhatikan adalah : jika node adalah node satu satunya, node adalah head, node adalah tail, dan node diantara head dan tail.

Untuk menghapus node dapat menggunakan fungsi free(node) yang akan menghapus node sehingga memori yang terpakai akan menjadi tersedia kembali, hal ini memungkinkan program berjalan tanpa adanya memori tidak terpakai (redundant). 

Jangan lupa saat dilakukan penghapusan node pastikan node node yang tersisa terhubung satu dengan yang lain atau hubungannya tidak terputus.

Circular Single Linked List adalah single linked list yang dimana node terakhirnya menunjuk ke node paling awal (head) sehingga tidak ada node yang merujuk ke NULL, seolah-olah looping.

Circular Single Linked List

Double Linked List

Double Linked List pada dasarnya sama dengan single linked list, hal yang membedakannya adalah adanya hubungan dua arah antar datanya yaitu next dan prev. Next merujuk pada data sesudah dan prev merujuk pada data sebelumnya.

Double Linked List

Pada Double Linked List, metode Insert dan Delete hampir sama dengan metode Insert dan Delete pada Single Linked List. Pembedanya adalah perhatikan bahwa ada hubungan ke node sebelumnya yaitu prev.

Circular Double Linked List adalah double linked list yang membentuk suatu sirkuit (tertutup) sehingga tidak ada data yang menuju NULL baik untuk prev maupun nextnya. Karena ada dua arah hubungan, maka ada dua sirkuit yang terbentuk. Pertama adalah next dari data terakhir yang menuju ke data pertama (head) dan yang kedua adalah prev dari data pertama yang menuju ke data terakhir (tail).

Circular Double Linked List

Materi Tambahan

Linked List banyak digunakan dalam berbagai jenis program-program komersial maupun non-komersial. Hal ini bertujuan agar performa program dapat dijalankan dengan baik. Tidak hanya itu, penggunaan Linked List juga sangat digunakan dalam industri Video Games.

Dalam pembuatan game Linked List digunakan untuk merepresentasikan sesuatu yang disebut Game Objects. Hal ini mengatur tentang objek objek yang terdapat di sebuah game, seperti player, enemies, rintangan, power up, dan lain lain.

Penggunaan Linked List dalam video game lebih ditujukan untuk kepentingan render suatu objek. Sebagai contoh, apabila suatu objek akan di spawn maka akan dilakukan metode insert node, sedangkan jika objek tersebut memenuhi suatu kondisi tertentu yang mengharuskan objek tersebut menghilang maka dapa dilakukan metode delete agar tidak berinteraksi lagi dengan objek lain di game tersebut.

Akan tetapi tidak semua hal dalam suatu game menggunakan linked list, untuk beberapa hal sebaiknya tidak menggunakan linked list melainkan array. Hal tersebut mencakup terrain, pohon, tanaman, 2D tiles dan lain lain dalam sebuah game tampak atas (top down games).

Untuk mengetahui lebih lanjut saya lampirkan referensi saya dibawah ini
https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/using-linked-lists-to-represent-game-objects-r2041/