Intro to Linked List : Why do I need it?

Linked list atau daftar berantai merupakan sebuah struktur data yang terdiri dari urutan rekaman data yang pada tiap rekaman terdapat alamat rekaman selanjutnya (http://en.wikipedia.org/wiki/Linked_list). Untuk lebih mudah memahami definisi dari linked list, bayangkanlah linked list tersebut seperti sebuah “Kereta Api”. Sebuah kereta terdiri dari sekumpulan gerbong dimana tiap gerbong terdapat penyambung dengan gerbong yang lain. Pada linked list, “gerbong-gerbong” tersebut merupakan rekaman data sementara “penyambung” tiap gerbong tersebut merupakan alamat pada linked list. Jika di ilustrasikan, maka linked list akan tampak sebagai berikut!

Bukankah sangat mirip dengan sebuah kereta api? Selalu ingatlah perbandingan ini, sebab akan lebih mudah memahami algoritma linked list dengan mengibaratkan pada sebuah kereta api dibanding memahami sintax linked list pada sebuah bahasa pemrograman.

“Alamat” pada linked list dikenal dengan pointer pada bahasa pemrograman. Sehingga untuk membangun sebuah linked list diperlukan abstrack data type (ADT) (bagi yang belum mengerti abstract data type, silahkan baca postingan sebelumnya tentang ADT) terhadap objek yang akan dibuatkan datanya dan pointer yang berfungsi mengatur alamat-alamat pada data-data yang ada (postingan ini tidak akan membahas tentang pointer. Tapi, bagi yang ingin belajar mengenai pointer, silahkan download materinya disini). Sounds hard? To tel you the truth, it is hard. Especialy when it comes to tree. However, easy or hard is a matter of perspective. You’ll never know about it till you’ve tried. Okay, moving on.

Pertanyaan yang paling penting yang akan dibahas pada postingan ini ialah, mengapa perlu dibutuhkan cara merepresentasikan data yang rumit seperti ini? Bukankah sudah ada cara merepresentasikan data yang lebih baik yaitu dengan array? Ada beberapa masalah yang dihadapi jika menggunakan array sebagai cara merepresentasikan data.

1. Pada saat mendefinisikan sebuah array, jumlah maksimal dari data yang akan disimpan harus sudah didefinisikan. Namun, seorang programmer tidak dapat mengetahui dengan pasti berapa jumlah data yang akan masuk saat membuat program dan pengubahan terhadap jumlah maksimal tersebut membutuhkan pikiran dan tenaga yang lebih yang hanya dapat dilakukan oleh programmer expert.
2. Untuk menghindari masalah pertama, maka cara paling aman ialah dengan mendefinisikan jumlah maksimal sebesar-besarnya. Namun, dengan demikian akan ada dua kemungkinan masalah yang muncul. Pertama, jika data yang di inputkan jauh lebih sedikit dari data maksimal, maka akan ada pemborosan memory. Kedua, jika ternyata jumlah maksimal tersebut tetap tidak mencukupi, maka program yang dibuat tidak akan berjalan dengan baik.

Maka untuk menghindari masalah-masalah diatas, linked list muncul sebagai solusi. Bagaimana linked list dapat mengatasi masalah diatas? Bayangkan lagi sebuah kereta api! Apakah si pembuat kereta api perlu menentukan dengan pasti berapa jumlah gerbong kereta api? Tentu saja tidak. Si pembuat kereta api cukup membuat beberapa gerbong  saja dan jika ternyata tidak mencukupi, maka cukup menambahkan satu penyambung diakhir gerbong dan mengaitkannya pada gerbong yang baru atau ternyata gerbongnya berlebihan, tinggal dilepaskan penyambung pada gerbong terakhir sehingga jumlah gerbongnya berkurang. Itulah konsep yang ditawarkan linked list. Sehingga data dapat diinputkan sebanyak mungkin tanpa harus terjadi pemborosan memory ataupun kurangnya tempat penyimpanan data.

Selain dua masalah diatas, ada beberapa masalah lain yang juga merupakan kekurangan dari representasi data dengan array yaitu penyisipan, penghapusan, dan pengurutan.

1. Penyisipan (insert) : Pada sebuah array, jika satu data disisipkan diakhir maka tidak akan ada masalah. Hanya tinggal menambahkan saja. Tapi jika data diinputkan di awal atau ditengah maka data-data sebelumnya harus digeser satu persatu. Bayangkan jika sebuah sistem memiliki sepuluh juta data dan tiap data mengandung 7 informasi dan akan disisipkan satu data diawal array. Maka tujuh puluh juta informasi tersebut harus digeser. Hal ini tentu akan memakan waktu yang sangat lama meskipun dengan memory yang besar. Pada sebuah linked list penyisipan data diawal, ditengah, atau diakhir tidak akan bermasalah karena tidak membutuhkan pergeseran data. Yang akan berubah hanya alamat yang ditunjuk pada data tersebut. Bayangkan lagi sebuah kereta api! Misalnya kita memiliki dua puluh gerbong dengan Gerbong A sebagai gerbong pertama dan akan disisipkan Gerbong X diawal kereta api. Maka yang perlu dilakukan ialah mengubah sambungan lokomotif ke gerbong X dan menyambung gerbong X dengan gerbong A tanpa harus mengganggu gerbong yang lainnya.
2. Penghapusan (delete) : Penghapusan tidak begitu jauh beda dengan penyisipan. Pada representasi data dengan array penghapusan data pada bagian awal array akan menyebabkan pergeseran data-data dibelakangnya. Semakin banyak data dibelakangnya semakin lama waktu yang diperlukan untuk dapat melakukan pergeseran tersebut. Bagaimana dengan linked list? Sekali lagi, yang perlu diubah hanya alamat dari linked list tersebut. Dengan tidak bosan-bosannya penulis katakan, “bayangkan sebuah kereta api!”. Bagaimana cara membuang gerbong pertama pada sebuah kereta api? Tinggal mengubah sambungan lokomotif ke gerbong kedua sehingga gerbong pertama akan terbuang. Simpelkn? (implementasi pada bahasa pemrograman akan mengerikan dan tidak sesimpel ini. Hehehe..^_^. Just kidding)
3. Pengurutan (sorting) : Pada bagian pengurutan inilah masalah yang benar-benar harus dihadapi oleh representasi data dengan array. Apa masalahnya? Perhatikan algoritma berikut!

Algoritma MAXSORT merupakan algoritma pengurutan data pada array. Pada algoritma ini, jika terdapat n data maka akan terjadi minimal 0 kali pertukaran data (jika ternyata pada penginputan data telah terurut, tentu saja kasus seperti ini di dunia nyata hanya memiliki kemungkinan dibawah 5%, malah dibawah 1%) dan maksimal n kali pertukaran data (kasus terburuk pada pengurutan MAXSORT dengan kemungkinannya sangat tinggi). Sekarang bayangkan data yang dimiliki oleh Facebook! Tentu saja ratusan giga, bahkan mungkin pada satu server akan terdapat lebih dari satu tera data. Lalu lakukan pengurutan data dengan algoritma diatas! Apa yang terjadi? Untuk meload sebuah halaman facebook akan dibutuhkan waktu yang sangat lama bahkan dengan kecepatan internet yang tinggi, apalagi kalau mengingat betapa menyedihkannya kecepatan internet di Indonesia jika dibandingkan dengan USA atau Inggris.

Pada linked list, pengurutan data tidak diikuti dengan pertukaran fisik data dan sekali lagi, yang berubah hanyalah urutan alamat dari data-data tersebut. Sehingga pengurutan data menjadi lebih cepat. Kelima masalah diatas yang membuat perlunya menggunakan linked list sebagai representasi data ketimbang menggunakan array.

Catatan :

*) Implementasi linked list pada bahasa pemrograman belum disertakan pada postingan ini karena memerlukan pembahasan tersendiri.

*) Implementasi linked list pada bahasa pemrograman akan diposting pada postingan selanjutnya.^_^.