LINKED LIST

LINKED LIST
Linked list atau biasa disebut senarai berantai adalah suatu kumpulan data yang saling terhubung antar 1 data dengan data berikutnya. Suatu element (disebut dengan node) dalam linked list selalu mempunyai hubungan dengan data berikutnya. Agar lebih jelas perhatikan contoh di bawah ini : 4Awal5915AkhirNULL
Gambar 1. Contoh linked list
Dalam gambar1 di atas, terlihat bahwa ada 4 buah data. Setiap data mempunyai anggota yang menunjuk ke data berikutnya, kecuali elemen terakhir yang berisi NULL. NULL berarti bahwa elemen tersebut tidak menunjuk ke posisi apapun. Selain itu elemen pertama ditunjuk oleh variable Awal dan elemen terakhir ditunjuk oleh variable Akhir.
Setiap elemen dari linked list mempunyai 2 bagian yaitu bagian data (info) yang bernilai dengan angka, dan sebagian lagi adalah penunjuk ke data berikutnya (pointer).
Linked list merupakan suatu penyimpanan data yang dinamis.
Adapun proses-proses yang biasa terjadi dalam linked list adalah :
1. Pendeklarasian struktur dan variable linked list
Dari gambar 1 dapat dilihat bahwa setiap elemen linked list mempunyai 2 bagian yaitu bagian data (info) dan bagian yang menunjuk ke data berikutnya (suksesor).
Contoh struktur untuk linked list di atas adalah :
1 : typedef struct tdata *pdata;
2 : typedef struct tdata
3 : {
4 : int info;
5 : pdata next;
6 : };
7 :
8 : pdata awal,akhir;
Keterangan :
􀂃 Perintah typedef struct tdata *pdata; berarti buat suatu type baru dengan nama pdata yang merupakan sebuah pointer ke struktur yang bernama
Halaman - 1
Linked List
tdata. Untuk saat ini struktur data tdata belum dibuat. Ini diperbolehkan dalam bahasa C.
􀂃 Perintah baris ke-2 sampai dengan baris ke-6 adalah pendeklarasian struktur tdata yang mempunyai field bernama info yang bertipe int, dan variable next yang bertipe pdata (pointer ke tdata).
􀂃 Perintah pada baris ke-7 adalah contoh pendeklarasian variable yang menggunakan tipe pdata. Perintah di atas berarti pembuatan variable awal dan akhir yang bertipe pdata.
Setelah perintah tersebut, kondisi di memori adalah : AwalAkhir
variable awal dan akhir menunjuk ke NULL, artinya tidak menunjuk ke data apapun.
2. Membuat elemen linked list
Membuat suatu elemen linked list berarti memesan tempat di memori untuk menyimpan sebuah list. Dalam bahasa C pemesanan alokasi memori adalah dengan menggunakan perintah/fungsi malloc.
Contoh pembuatan 1 buah list adalah :
pdata baru;
baru=(pdata)malloc(sizeof(tdata));
baru->info=databaru;
baru->next=NULL;
Halaman - 2
Linked List
3. Menghapus elemen list
Menghapus elemen list berarti menghilangkan atau menghancurkan alokasi memori sebuah list yang telah ada di memori. Proses ini dilakukan agar data yang tidak diperlukan benar-benar terhapus di memori sehingga penggunaan memori dapat optimal karena data-data yang tidak diperlukan dihilangkan. Dalam bahasa C, penghapusan list adalah dengan menggunakan perintah free.
Contoh implementasi dalam bahasa C adalah :
free(baru);
4. Penambahan elemen di posisi awal
Penambahan elemen di posisi awal adalah menambahkan data baru pada posisi awal, sehingga data baru tersebut akan menjadi awal. Ada 2 kondisi yang harus diperhatikan ketika kita melakukan proses penambahan elemen baru di awal yaitu kondisi linked list sedang kosong dan kondisi linked list sudah mempunyai elemen.
􀂃 Penambahan di awal ketika linked list masih kosong AwalAkhir15Baru harus menjadi AwalAkhir15Baru
Itu berarti ketika linked list masih kosong, maka variable awal dan akhir akan diisi dengan variable baru.
􀂃 Penambahan di awal ketika linked list sudah mempunyai elemen 5915AwalAkhir3Baru
harus menjadi
Halaman - 3
Linked List
5915AwalAkhir3Baru
dan kemudian 5915AwalAkhir3Baru
Dengan ilustrasi di atas, maka proses penambahannya adalah dengan mengisikan field next milik elemen baru dengan posisi awal linked list, kemudian posisi awal berubah ke posisi baru.
Implementasi dari langkah-langkah di atas dalam bahasa C adalah :
void tambah_awal(pdata *awal, pdata *akhir, int databaru)
{
pdata baru;
baru=(pdata)malloc(sizeof(tdata));
if (baru!=NULL)// if malloc sukses (memori tersedia)
{
baru->info=databaru;
baru->next=NULL;
if(*awal==NULL) // if linked list is empty
{
*awal=baru;
*akhir=baru;
}
else// if linked list tidak kosong
{
baru->next=*awal;
*awal=baru;
}
}
else
printf("Memori Penuh. Tidak Bisa Tambah Elemen.\n");
}
Contoh cara pemanggilannya adalah :
tambah_awal(&awal,&akhir,1);
tambah_awal(&awal,&akhir,7);
int data;
printf(“Data : “);scanf(“%d”,&data);
tambah_awal(&awal,&akhir,data);
tambah_awal(&awal,&akhir,3);
Halaman - 4
Linked List
5. Penambahan elemen di posisi terakhir
Penambahan di posisi akhir adalah proses penambahan data baru dimana data baru disimpan di posisi terakhir. Setelah proses penambahan selesai, maka variable akhir akan menunjuk ke data baru tersebut. Ada 2 kondisi yang harus diperiksa yaitu kondisi penambahan akhir pada linked list yang masih kosong dan kondisi penambahan akhir pada linked list yang sudah mempunyai elemen.
􀂃 Penambahan akhir ketika linked list masih kosong AwalAkhir20Baru harus menjadi AwalAkhir20Baru
Dari ilustrasi di atas, maka variable awal dan akhir akan diisi dengan alamat baru.
􀂃 Penambahan akhir ketika linked list sudah mempunyai elemen. 5915AwalAkhir20Baru
Setelah elemen baru dibuat, maka sambungkan field next milik elemen terakhir linked list ke data baru. 5915AwalAkhir20Baru
Kemudian variable/pointer akhir dipindahkan ke data baru. 5915Awal20BaruAkhir
Halaman - 5
Linked List
Dari langkah-langkah di atas, maka dapat diimplementasikan ke dalam bahasa C sebagai berikut :
void tambah_akhir(pdata *awal, pdata *akhir, int databaru)
{
pdata baru;
baru=(pdata)malloc(sizeof(tdata));
if (baru!=NULL)
{
baru->info=databaru;
baru->next=NULL;
if(*awal==NULL) // if linked list is empty
{
*awal=baru;
*akhir=baru;
}
else // if linked list is not empty
{
(*akhir)->next=baru;
*akhir=baru;
}
}
else
printf("Memori Penuh. Tidak Bisa Tambah Elemen.\n");
}
Contoh cara pemanggilan fungsi tersebut adalah :
tambah_akhir(&awal,&akhir,1);
tambah_akhir(&awal,&akhir,7);
int data;
printf(“Data : “);scanf(“%d”,&data);
tambah_akhir(&awal,&akhir,data);
tambah_akhir(&awal,&akhir,3);