we are move to our new home
http://babibu.eamca.com
feel free to explore

Tuesday, April 20, 2010

Linked List


Linked list adalah kumpulan item yang disebut nodes, terdiri dari information field dan next address field. Information field berisi satu elemen dari list, sedangkan next address field berisi alamat dari node berikutnya. Field ini menggabungkan node-node dan disebut pointer.
Linked list diakses melalui pointer yang menunjuk ke node pertama dalam sebuah list. Node selanjutnya diakses melalui pointer yang terdapat di next address node sebelumnya. Next address di node terakhir berisi null yang menandakan akhir dari list.
Linked list dapat diimplementasikan dalam bahasa C dengan menggunakan beberapa fungsi, yaitu :
Fungsi getnode, untuk menyisipkan node dalam linked list
int getnode(void)
{
int p;
if(avail == -1){
printf(“overflow\n”);
exit(1);
}
p=avail;
avail=node[avail].next;
return(p);
}

Fungsi freenode, untuk menghapus node dalam linked list
void freenode(int p)
{
node[p].next = avail;
avail = p;
return;
}

Fungsi insafter, untuk menyisipkan node
void insafter(int p, int x)
{
int q;
if(p == -1){
printf(“void insertion\n”);
return;
}
q = getnode();
node[q].info = x;
node[q].next = node[p].next;
node[p].next = q;
return;
}


Fungsi delafter, untuk menghapus node di sembarang posisi
void delafter(int p, int *px)
{
int q;
if((p==-1)||(node[p].next==-1){
printf(“void deletion\n”);
return;
}
q = node[p].next;
*px = node[q].info;
node[p].next = node[q].next;
freenode(q);
return;
}

Linked list berbeda dengan array. Alokasi memori array bersifat statis, sedangkan alokasi memori linked list bersifat dinamis.
Terdapat juga perbedaan dalam pengaksesan. Untuk mengakses data ke-n dalam linked list dilakukan penyusuran data secara satu persatu, sedangkan dalam array, programmer dapat langsung mengakses data ke-n.




Dari perbedaan-perbedaan tersebut, maka diketahui bahwa keuntungan linked list adalah alokasi memorinya bersifat dinamis sehingga programmer tidak perlu mendefinisikan besar linked list. Sedangkan dalam array, kita perlu mendefinisikan besar array dahulu, karena memori array bersifat statis.

Linked list memiliki empat macam bentuk. Pertama, single linked list, yaitu list yang setiap node-nya memiliki field nilai dan field next yang berupa pointer ke node selanjutnya. Kedua, double linked list, yang selain field nilai dan field next, terdapat field prev yang berupa pointer ke node selanjutnya. Ketiga, circular linked list, dimana field next dari node terakhir menunjuk ke node pertama. Dan yang keempat , circular double linked list, adalah gabungan double linked list dan circular linked list.

Salah satu problem yang dapat diselesaikan dengan linked list Josephus Problem. Josephus problem dapat digambarkan dengan kumpulan prajurit yang sedang dikepung musuh. Hanya ada satu kuda untuk satu prajurit agar dapat lolos dan mencari bantuan. Untuk menentukan siapa yang lolos, mereka membentuk lingkaran. Mereka memasukkan salah satu nama dan angka n dalam sebuah topi.

Dimulai dari prajurit yang namanya diambil tadi, mereka berhitung searah jarum jam sampai angka n. Prajurit yang mendapat angka n keluar dari lingkaran, dan perhitungan dimulai lagi dari prajurit selanjutnya. Perhitungan ini tidak menghitung prajurit yang telah keluar lingkaran. Proses ini berlanjut sehingga setiap mencapai angka n, seorang prajurit keluar. Prajurit yang terakhir dapat mengambil kuda dan lolos mencari bantuan.

Dalam program, inputnya berupa angka n dan daftar nama prajurit urut searah jarum jam. Prajurit pertama menjadi awal perhitungan. Outputnya berupa daftar prajurit sesuai urutan keluarnya dan nama prajurit terakhir.

0 comments:

Post a Comment