Linked list
Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.
Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.
-------- -------- --------
Mesin Data Data
-------- -------- --------
(kepala) ---> Pointer ---> Pointer --
-------- -------- --------
Programmer membaca data menyerupai kondektur yang ingin memeriksa karcis penumpang. Programmer menyusuri linked list melalui kepalanya, dan kemudian berlanjut ke gerbong (data) berikutnya, dan seterusnya sampai gerbong terakhir (biasanya ditandai dengan pointer menunjukkan alamat kosong (NULL)). Penyusuran data dilakukan secara satu persatu sehingga penyusuran data bekerja dengan keefektifan On. Dibandingkan array, ini merupakan kelemahan terbesar linked list. Pada array, apabilan programmer ingin mengakses data ke-n (index n), maka programmer dapat langsung mengaksesnya. Sedangkan dengan linked list programmer harus menyusuri data sebanyak n terlebih dahulu.
Apabila kita menggunakan java, konsep linked list ini sudah terlingkupi dalam Java Collection Framework (JCF). Dengan Java, kita tidak perlu lagi membuat LinkedList. Kita tinggal menggunakan class yang sudah disediakan dalam JCF.
Berikut ini saya akan menjelaskan operasi-operasi yang ada pada Linked List yaitu sebagai berikut :
1.Insert
Insert digunakan untuk menambahkan sebuah simpul baru ke dalam suatu linked list.
2.IsEmpty
IsEmpty digunakan untuk mengetahui apakah linked list kosong atau tidak.
3.Fine First
Fine First digunakan untuk mencari elemen pertama dari linked lis
4.Fine Next
Fine Next digunakan untuk mencari elemen sesudah elemen yang ditunjuk oleh now.
5.Retrieve
Retrieve digunakan untuk mengambil elemen yang ditunjuk oleh now. Kemudian elemen tersebut akan dikembalikan oleh fungsi.
6.Update
Update digunkan untuk mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
7.Delete Now
Delete Now digunakan untuk menghapus elemen yang ditunjuk oleh now.
8.Delete Head
Delete Head digunakan untuk menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
9.Clear
Clear digunakan untuk menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
Jenis-Jenis Linked List
• Singly linked list
• Double linked list
• Circular Linked List
Dalam pembuatan single linked list dapat menggunakan dua metode:
a. LIFO (Last In First Out) aplikasinya : Stack (Tumpukan)
Adalah suatu metoda pembuatan linked list dimana data yang masuk paling akhir adalah data yang keluar paling awal.
b. FIFO (First In First Out) aplikasinya : Queue (Antrian)
Adala suatu metoda pembuatan linked list dimana data yang masuk paling awal adalah data yang keluar paling awal juga.
Program Linked List dengan pointer
#include
#include
using std::cout;
//fungsi pendeklarasian nilai dengan variabel typeinfo bertipe integer
typedef int typeinfo;//menjadikan typeinfo bernilai integer
typedef struct typenode *typeptr;//membuat fungsi struct typenode dengan fungsi typeptr
typedef struct typenode {typeinfo info; //membuat fungsi struct typenode dengan fungsi typeinfo nama info
typeptr next;};//membuat fungsi struct typenode dengan fungsi typeinfo nama typeptr
typeptr awal,akhir;//typeptr dengan variabel awal dan akhir
void buatlistbaru();//pendeklarasian fungsi
void sisipdepan (typeinfo IB);//pendeklarasian fungsi dengan nilai IB
void sisipbelakang (typeinfo IB);//pendeklarasian fungsi dengan nilai IB
void sisiptengah (typeinfo IB);//pendeklarasian fungsi dengan nilai IB
void hapuslist(typeinfo IB);//pendeklarasian fungsi dengan nilai IB
void cetaklist ();//pendeklarasian fungsi
int main()//main program / program utama
{
//fungsi program
buatlistbaru();//sintaks menjalankan program
sisipdepan(10);//sintaks menjalankan program
sisipbelakang(25);//sintaks menjalankan program
sisipbelakang(100);//sintaks menjalankan program
sisiptengah(50);//sintaks menjalankan program
cetaklist ();//sintaks menjalankan program
hapuslist (50);//sintaks menjalankan program
cetaklist ();//sintaks menjalankan program
return 0;
}
//tujuan dari program di bawah ialah untuk menetukan letak awal dan akhir dari list//
void buatlistbaru()//perintah memanggil fungsi
{ typeptr list;//pendeklarasian variabel "list" dengan tipe pointer
list = (typenode *) malloc(sizeof(typenode));//pointer "list" menunjuk ke suatu pointer kosong
list=NULL;//nilai dari pointer "list" adalah NULL/kosong
awal=list;//pointer "awal" menunjuk ke yang ditunjuk pointer "list"
akhir=list;//pointer "akhir" menunjuk ke yang ditunjuk pointer "list"
}
//tujuan dari program di bawah ialah menyisipkan suatu node yang nantinya akan diletakkan di bagian depan list//
void sisipdepan(typeinfo IB)//perintah memanggil fungsi dan pemberian nilai IB
{ typeptr NB;//perintah pendekarasian variabel "NB" dengan tipe data pointer
NB=(typenode *) malloc(sizeof(typenode));//pointer "NB" menunjuk ke suatu pointer kosong
NB->info=IB;//info dari pointer NB sama dengan IB
if (awal == NULL)//jika info awal sama dengan NULL, maka jalankan program dibawah
{ awal = NB;//pointer "awal" menunjuk ke yang ditunjuk pointer "NB"
akhir =NB; }//pointer "akhir" menunjuk yang ditunjuk ke pointer "NB"
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{ NB->next=awal;}//alamat pointer "NB" menunjuk ke pointer "awal"
awal=NB;//pointer "awal" menunjuk ke yang ditunjuk pointer "list"
}
//tujuan dari program di bawah ialah menyisipkan suatu node yang nantinya akan diletakkan di bagian belakang list//
void sisipbelakang(typeinfo IB)//perintah memanggil fungsi dan pemberian nilai IB
{ typeptr NB;//perintah pendekarasian variabel NB dengan tipe data pointer
NB=(typenode *) malloc(sizeof(typenode));//pointer "NB" menunjuk ke suatu pointer kosong
NB->info=IB;//info dari pointer NB sama dengan IB
if (awal == NULL)//jika info awal sama dengan NULL, maka jalankan program dibawah
{ awal = NB;//pointer "awal" menunjuk ke yang ditunjuk pointer "NB"
akhir =NB; }//pointer "akhir" menunjuk ke yang ditunjuk pointer "NB"
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{ akhir->next=NB;}//alamat pointer "akhir" menunjuk ke pointer "NB"
akhir=NB;//pointer "akhir" menunjuk ke pointer "list"
akhir->next=NULL;//alamat pointer "akhir" kosong/NULL
}
//tujuan dari program di bawah ialah menyisipkan suatu node yang nantinya akan diletakkan di bagian belakang list//
void sisiptengah(typeinfo IB)//perintah memanggil fungsi dan pemberian nilai IB
{ typeptr NB, bantu;//perintah pendekarasian variabel NB dan bantu dengan tipe data pointer
NB=(typenode *) malloc(sizeof(typenode));//pointer "NB" menunjuk ke suatu pointer kosong
NB->info=IB;//info dari pointer NB sama dengan IB
NB->next=NULL;//alamat pointer "NB" kosong/NULL
if (awal == NULL)//jika info awal sama dengan NULL, maka jalankan program dibawah
{ awal = NB;//pointer "awal" menunjuk ke yang ditunjuk pointer "NB"
akhir =NB; }//pointer "akhir" menunjuk ke yang ditunjuk pointer "NB"
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{ bantu=awal;//pointer "bantu" sama dengan "awal"
while ((IB > bantu->next->info) && (bantu->next!=NULL))//jika "IB" lebih besar daripada info dari bantu next, maka jalankan program dibawah
bantu=bantu->next;}//memindah alamat yang ditunjuk pointer "bantu" ke node selajutnya
NB->next=bantu->next;//memindah alamat yang dituju NB ke alamat yang dituju bantu
bantu->next=NB;//memindah alamat bantu ke "NB"
}
//tujuan dari program di bawah ialah menghapus suatu node list//
void hapuslist(typeinfo IH)//perintah memanggil fungsi dan pemberian nilai IB
{ typeptr hapus, bantu;//perintah pendekarasian variabel hapus dan bantu dengan tipe data pointer
if(awal==NULL)//jika info awal sama dengan NULL, maka jalankan program dibawah
cout << "List masih kosong";//output
else if (awal->info==IH)//jika prosedur pembanding tidak sesuai, cek jika info awal sama dengan IH, maka mengerjakan perintah di bawah
{ hapus=awal;//memindah pointer hapus menunjuk ke pointer awal
awal=hapus->next;//memindah pointer awal ke alamat yang ditunjuk hapus next
free(hapus); }//node yangt ditunjuk oleh pointer "hapus" akan dihapus
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{ bantu=awal;//memindah pointer hapus menunjuk ke pointer awal
while ((bantu->next->info!=IH) && (bantu->next=NULL))//jika info dari alamat yang dituju bantu adalah IH dan alamat yang dituju bantu adalah NULL, maka mengerjakan perintah di bawah
{bantu=bantu->next;}//memindah alamat yang ditunjuk pointer "bantu" ke alamat yang dituju pointer"bantu"
hapus=bantu->next;//memindah pointer hapus ke "alamat" yang dituju "bantu"
if (hapus==NULL)//jika hapus sama dengan NULL, maka jalankan program di bawah
{ cout<< "List tidak ditemukan \n"; }//output
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{if (hapus==akhir)//jika pointer "hapus" sama dengan pointer "akhir", maka jalankan program di bawah
{akhir=bantu;//memidah alamat yang dituju pointer "akhir" ke pointer "bantu"
akhir->next=NULL; }//alamat pointer "NB" kosong/NULL
else//jika prosedur pembanding tidak sesuai, maka mengerjakan perintah di bawah
{bantu->next=hapus->next;}//memindah alamat yang dituju pointer "bantu" ke alamat yang ditujun pointer "hapus"
free(hapus);}//node yangt ditunjuk oleh pointer "hapus" akan dihapus
}
}
//tujuan dari program di bawah ialah mencetak list//
void sisiptengah(typeinfo IB)
void cetaklist()//perintah memanggil fungsi
{ typeptr bantu;//perintah pendekarasian variabel "NB" dengan tipe data pointer
bantu=awal;//pointer bantu menunjuk ke yang ditunjuk pointer "awal"
while (bantu!=NULL)//jika nilai "bantu" tidak sama dengan NULL
{
cout << " " << bantu->info;//output sekaligus mencetak info dari bantu
cout << " " ;//output
bantu=bantu->next;//memindah alamat yang ditunjuk pointer "bantu" ke alamat yang dituju pointer"bantu"
}
}
