PERTEMUAN KE 11 Linked List Apa Itu Linked List? Linked list tidak lain adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis
sehingga
isi
dari
daftar
dapat
dimanipulasi.
Untuk
memahami linked list, terlebih dahulu anda harus tahu konsep pointer dan pengalokasian memori. Coba anda bayangkan apabila anda mendeklarasikan array dari record(array of record) sebanyak 10 elemen. Setiap kali program dijalankan, maka akan memesan memory sebesar 10x ukuran record. Itu merupakan suatu pemborosan walaupun kita hanya menggunakan 5 elemen record. Maka dari itu, biasanya para programer lebih memilih menggunakan linked list dalam pemrograman. Linked list dibedakan atas 2 jenis yaitu singly linked list dan doubly linked list. 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. 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. a. Nodes Self-referential objects (object yang mereferensikan dirinya sendiri) yang disebut nodes, yang dihubungkan dengan links, membentuk kata “linked” list. b. Linked List ( LL ) Adalah koleksi data item yang tersusun dalam sebuah barisan secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.
c. Single Linked List Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan. Ilustrasi single LL:
Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LL. Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja. d. Double Linked List Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut. Ilustrasi double LL:
e. Circular Linked List Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih kosong, ilustrasi Circular LL :
Berikut ini Contoh Progam Linked List single dengan Pointer C/C++ (STRUKTUR DATA) : #include
#include #include<stdlib.h> /* untuk beberapa fungsi umum (konversi dll) dan untuk operasi matematika.*/ #include<malloc.h> /*mengatur alokasi memory*/ #define Nil NULL #define info(P) P->info #define next(P) P->next #define First(L) (L) typedef int S152; typedef struct U152 *address;
typedef struct U152 { void SisipSenarai(list *L, list t, list p) { if(p==NULL) { t->next = *L; *L = t; }else { t->next = p->next; p->next = t; } }void CetakSenarai(list L) { list N152; for(N152=L; N152!=Nil; N152=N152->next) { cout<<" "<"; }cout<<" NULL"<<endl; } int main() { list G152; list E152; int I152,W152,nilai; CiptaSenarai(&G152);
cout<<"*Daryono- 123*\n"; cout<<"================================= \n"; cout<<"Masukkan Banyak Data = "; cin>>W152; for(I152=1; I152<=W152; I152++) { cout<<"Masukkan Data Senarai ke-"<>nilai; E152 = NodBaru(nilai); SisipSenarai(&G152, E152, NULL); }CetakSenarai(G152); getch(); return 0; }
Output Progam Linked List dengan Pointer C/C++
Contoh Linked List Double: #include #include #include <stdio.h> #include int pil; void pilih(); void buat_baru(); void tambah_belakang(); void tambah_depan(); void hapus_belakang(); void hapus_depan(); void tampil();
struct simpul { char nim[8], nama [20]; int umur; struct simpul *kiri, *kanan; } mhs, *baru, *awal=NULL, *akhir=NULL,*hapus,*bantu;
int main() { do { clrscr(); cout<<"MENU DOUBLE LINKEDLIST"<<endl; cout<<"1. Tambah Depan"<<endl; cout<<"2. Tambah Belakang"<<endl;
cout<<"3. Hapus Depan"<<endl; cout<<"4. Hapus Belakang"<<endl; cout<<"5. Tampilkan"<<endl; cout<<"6. Selesai"<<endl; cout<<"Pilihan Anda : "; cin>>pil; pilih(); } while(pil!=6); return 0; }
void pilih() { if(pil==1) tambah_depan(); else if(pil==2) tambah_belakang(); else if(pil==3) hapus_depan(); else if(pil==4) hapus_belakang(); else if(pil==5) tampil(); else cout<<"selesai"; }
void buat_baru() { baru=(simpul*)malloc(sizeof(struct simpul));
cout<<"input nim : ";cin>>baru->nim; cout<<"input nama : ";cin>>baru->nama; cout<<"input umur : ";cin>>baru->umur; baru->kiri=NULL; baru->kanan=NULL; }
void tambah_belakang() { buat_baru(); if(awal==NULL) { awal=baru; akhir=baru; } else { akhir->kanan=baru; baru->kiri=akhir; akhir=baru; } cout<<endl<<endl; tampil(); }
void tambah_depan() { buat_baru(); if(awal==NULL) {
awal=baru; akhir=baru; } else { baru->kanan=awal; awal->kiri=baru; awal=baru; } cout<<endl<<endl; tampil(); }
void hapus_depan() { if (awal==NULL) cout<<"Kosong"; else if (awal->kanan==NULL) { hapus=awal; awal=NULL; akhir=NULL; free(hapus); } else { hapus=awal; awal=hapus->kanan; awal->kiri=NULL; free(hapus);
} cout<<endl<<endl; tampil(); }
void hapus_belakang() { if (awal==NULL) cout<<"Kosong"; else if (awal->kanan==NULL) { hapus=awal; awal=NULL; akhir=NULL; free(hapus); } else { hapus=akhir; akhir=hapus->kiri; akhir->kanan=NULL; free(hapus); } cout<<endl<<endl; tampil(); }
void tampil() { if (awal==NULL)
cout<<"Kosong"; else { bantu=awal; while(bantu!=NULL) { cout<<"nim : "<nim; cout<<" nama : "<nama; cout<<" umur : "<umur<<endl; bantu=bantu->kanan; } } getch(); }
Tugas Buatkan Contoh Aplikasi Linked List Circular :
