Kamis, 14 Mei 2009
STRUKTUR DATA
SINGLY LINKED LIST
1. Pengertian
Bekerja dengan data yang besar tidak dapat kita hindari. Dan tidak jarang pula, data besar tersebut memiliki hubungan yang erat. Sebagai contoh, kita akan bekerja dengan file yang menyimpan sangat banyak record, di mana setiap record juga memiliki banyak field. Tugas kita tidak hanya sekadar menampilkan setiap record-nya, melainkan harus pula menambahkan record, menghapus beberapa record sesuai keinginan user, sampai mengurutkan record! Kondisi tersebut mengharuskan kita memiliki satu rantai data yang panjang dan saling berhubungan. Rantai data tersebut harus mampu menampung semua data yang kita miliki. Penggunaan array saja jelas tidak bisa, karena kita bekerja dengan barisan data heterogen. Kita perlu menggunakan union ataupun struct. Namun, kita juga tidak dapat semena-mena menggunakan array of struct dalam jumlah besar. Karena lokasi penampungan memory untuk alokasi konvensional tidak akan mempu mencukupi kebutuhan memory kita. Selain itu, kita mungkin akan melakukan alokasi dan dealokasi beberapa kali di dalam program untuk mengoptimasi penggunaan memory. Solusi yang lebih baik adalah menggunakan linked list, baik singly (single) linked list ataupun doubly (double) linked list. Tetapi pada makalah ini yang dibahas adalah singly (single) linked list.
Nude merupakan komponen-komponen yang membentuk hubungan seperti rantai dengan bantuan pointer. Atau bisa juga dikatakan sebagai beberapa obyek yang saling terhubung dan membentuk linked list. Setiap node terbagi menjadi dua bagian, yaitu bagian data dan bagian penyambung. Bagian data berisi data yang akan disimpan dan diolah. Sedangkan bagian penyambung berisi alamat simpul berikutnya.
Linked adalah koleksi obyek heterogen dengan sifat setiap obyek (kecuali obyek terakhir) mempunyai penerus dan setiap obyek (kecuali obyek pertama) mempunyai pendahulu. Salah satu penggunaan pointer adalah untuk membuat linked list atau senarai berantai. Linked list sendiri dapat diartikan sebagai sekumpulan komponen yang saling berhubungan (berantai) dengan bantuan pointer.
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan singly (single) linked apabila hanya ada satu pointer yang menghubungkan setiap node. Setiap node akan berbentuk struct dan memiliki satu buah field bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan cara first-create-firstaccess ataupun first-create-last-access.
2. Pembahasan
Single linked list atau biasa disebut linked list terdiri dari elemen-elemen individu, dimana masing-masing individu akan saling terhubung. Masing-masing elemen terdiri dari dua bagian, yaitu bagian data atau informasi yang disimpan dan bagian lainnya sebagai penghubung dengan elemen selanjutnya.
Untuk mengakses elemen dalam linked list, dimulai dari instance head dan menggunakan instance nextNode dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai. Dengan single linked list, list dapat dilintasi hanya satu arah dari head ke tail karena masing-masing elemen tidak terdapat link dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses elemen sebelumnya, kita harus mulai dari head.
Asumsikan kita memiliki sejumlah node yang selalu menoleh ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, Anda bisa mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah variabel next. Sampai di sini, kita baru saja mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan mendeklarasikan beberapa variabel pointer bertipe struct tnode. Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list, node aktif dalam linked list, dan node sementara yang kita gunakan dalam pembuatan node di linked list. Berikan nilai awal NULL kepada mereka. Berikan deklarasi seperti berikut ini:
struct tnode *head=NULL, *curr=NULL,
*node=NULL;
Dengan demikian, sampai saat ini, kita telah memiliki tiga node. Satu sebagai kepala (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node sementara (node). Kita telah siap untuk membuat singly linked list. Untuk itu, kita akan memasukkan nilai tertentu sebagai nilai untuk field x dengan cara melakukan perulangan sehingga campur tangan user tidak diperlukan. Seperti yang dikemukakan sebelumnya, kita akan membuat singly linked list dengan cara first-create-first-access. Dengan cara ini, node yang dibuat pertama akan menjadi head. Node-node yang dibuat setelahnya akan menjadi node-node pengikut. Untuk mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-node berikutnya akan berbaris ke arah bagian anak panah yang tajam.
[head]->[node1]->[node2]->[node3]...
[noden]->NULL
Apabila kita perhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Bagaimana dengan node terakhir? Kita berikan nilai NULL. Dengan demikian, setiap node kebagian jatah.
Sebagai contoh perhatikan ilustrasi berikut untuk lebih jelasnya:
Single Linked List merupakan jenis Linked List yang hanya menggunakan satu variabel pointer untuk menyimpan banyak data.
Double Linked List Merupakan linked list yang tiap-tiap nodenya menyimpan node sebelumnya dan node yang selanjutnya, atau biasa disebut dengan linked list berpointer ganda.
Circular Linked adalah linked list yang node awalnya menunjuk ke node akhir dan node akhirnya menunjuk ke node awal. Sehingga membentuk link list tersebut membentuk suatu siklus seperti lingkaran.
Tidak ada komentar:
Posting Komentar