MODUL PEMROGRAMAN 2
LINKED LIST
LINKED LIST merupakan operasi yang menggabungkan operasi pada stack dan queue yaitu FIFO dan LIFO.Membuat Program SINGLE LINKED LIST dengan statement untuk fungsi sisip sebelum simpul, sisip setelah simpul dan hapus tengah dengan ketentuan sebagai berikut : Untuk fungsi sisip sebelum simpul, jika data harus disisip di awal list maka akan mengubah posisi head. Demikian juga jika simpul tertentu yang dimaksud tidak ada maka ada pesan simpul baru tidak dapat disisipkan. Selain kondisi tersebut, lakukan sisip di tengah. Untuk fungsi sisip setelah simpul, jika simpul tertentu yang dimaksud tidak ada maka ada pesan simpul baru tidak dapat disisipkan. Selain kondisi tersebut, lakukan sisip di tengah. Untuk fungsi hapus tengah, apabila yang dihapus posisi awal list maka akan mengubah posisi head. Demikian juga jika data yang akan dihapus tidak ada maka ada pesan simpul tidak ada. Selain kondisi tersebut, lakukan hapus simpul tengah.
Double Linked List adalah : Sebuah struktur data yang memiliki 2 pointer penunjuk, sehingga bisa saling terhubung antara elemen satu dengan elemen lainnya. dengan menggunakan struktur data seperti berikut : data pointer penunjuk elemen setelahnya (next) pointer penunjuk elemen sebelumnya (prev) Linked List biasa disebut simpul atau node.
Siti yuliyanti
Page 1
MODUL PEMROGRAMAN 2
dalam program ini diperlukan beberapa library yaitu : #include<stdio.h> #include<stdlib.h>
untuk merepresentasikannya bisa seperti ini typedef struct simpul node; struct simpul { int data; node *prev; node *next; };
lalu membuat variabel global untuk head, tail, dan baru node *head = NULL, *tail = NULL, *baru;
lalu buat fungsi untuk alokasi memori, dan disini diperlukan stdlib.h void allocate_node (int x) { baru = (node *) malloc (sizeof(node)); if(baru==NULL) { printf("Alokasi Gagal\n"); exit(1); } else { baru->data=x; baru->next=NULL; baru->prev=NULL; } }
setelah simpul baru dialokasikan, maka simpul baru bisa dibuat : head = tail = baru;
ada beberapa fungsi yang diperlukan untuk menambahkan (menyisipkan) simpul baru, yaitu : sisip awal sisip akhir sisip sebelum sisip sesudah dan untuk menghapus simpul, diperlukan beberapa fungsi, yaitu : hapus awal hapus akhir Siti yuliyanti
Page 2
MODUL PEMROGRAMAN 2
hapus simpul Untuk menyisipkan fungsi-fungsinya adalah : fungsi buat list void buat_list() { printf("Data Masih Kosong, List akan dibuat dengan data tersebut\n"); system("PAUSE"); head = tail = baru; }
fungsi sisip awal void sisip_awal() { if(head==NULL && tail==NULL) buat_list(); else { baru->next=head; head->prev=baru; head=baru; } }
fungsi sisip akhir void sisip_akhir() { if(head==NULL && tail==NULL) buat_list(); else { baru->prev=tail; tail->next=baru; tail=baru; } }
fungsi sisip sebelum void sisip_sebelum(int s) { node *before=head; int cek=0; if(before->next==NULL) cek=1; else { while(before->next->data!=s)
Siti yuliyanti
Page 3
MODUL PEMROGRAMAN 2
{ before=before->next; if(before->next==NULL) { cek = 1; break; } } } if(cek==0) { baru->prev = before; baru->next = before->next; before->next->prev = baru; before->next = baru; } else gatot(); }
fungsi sisip sesudah void sisip_sesudah(int s) { node *after=tail; int cek=0; if(after->prev == NULL) cek=1; else { while(after->prev->data!=s) { after=after->prev; if(after->prev==NULL) { cek = 1; break; } } } if(cek==0) { baru->next = after; baru->prev = after->next; after->prev->next = baru; after->prev = baru; } else gatot(); }
Lalu untuk menghapus diperlukan beberapa fungsi, yaitu : hapus simpul Siti yuliyanti
Page 4
MODUL PEMROGRAMAN 2
void free_node(node *p) { free(p); p=NULL; printf("DATA TERHAPUS\n"); }
hapus satu void hapus_satu() { node *hapus = head; head = NULL; tail = NULL; free_node(hapus); }
hapus awal void hapus_awal() { node *hapus = head; head->next->prev = NULL; head = head->next; free_node(hapus); }
hapus akhir void hapus_akhir() { node *hapus = tail; tail->prev->next = NULL; tail = tail->prev; free_node(hapus); }
hapus simpul tertentu void hapus_tengah(int s) { node *hapus=head; int cek=0; while(hapus->data!=s) { if(hapus->next==NULL) { cek=1; break; } hapus = hapus->next; } if(cek==0) {
Siti yuliyanti
Page 5
MODUL PEMROGRAMAN 2
hapus->prev->next = hapus->next; hapus->next->prev = hapus->prev; free_node(hapus); } else gadel(); }
untuk menampilkan pesan diperlukan fungsi tambahan : void gatot() { printf("SIMPUL BARU TIDAK DAPAT DISISIPKAN\n"); system("PAUSE"); } void gadel() { printf("TIDAK ADA DATA YANG DIHAPUS\n"); system("PAUSE"); }
Dan juga untuk menampilkan data yang berada pada list bisa di representasikan seperti ini : void tampil() { node *p= head; printf("\nData Simpul ==> "); while(p!=NULL) { printf("%d ", p->data); p=p->next; } printf("\n\n"); }
Dan pada main bisa menggunakan code seperti ini : void main() { head=baru; int pilih, data, s; char lagi='y'; while(lagi=='y') { system("CLS"); awal(); tampil(); printf("Menu Pilihan : \n"); printf("1. Sisip Awal\n"); printf("2. Sisip Akhir\n"); printf("3. Sisip Sebelum Simpul\n"); printf("4. Sisip Sesudah Simpul\n"); printf("5. Hapus Awal\n");
Siti yuliyanti
Page 6
MODUL PEMROGRAMAN 2
printf("6. Hapus Akhir\n"); printf("7. Hapus Tengah\n"); printf("\nPilih No : "); scanf("%d", &pilih); switch(pilih) { case 1 : printf("Masukkan data : "); scanf("%d", &data); allocate_node(data); sisip_awal(); break; case 2 : printf("Masukkan data : "); scanf("%d", &data); allocate_node(data); sisip_akhir(); break; case 3 : printf("Masukkan data : "); scanf("%d", &data); allocate_node(data); if(head==NULL && tail==NULL) buat_list(); else { printf("Dimasukkan sebelum scanf("%d",&s); if(s==head->data) sisip_awal(); else sisip_sebelum(s); } break; case 4 : printf("Masukkan data : "); scanf("%d", &data); allocate_node(data); if(head==NULL && tail==NULL) buat_list(); else { printf("Dimasukkan sesudah scanf("%d",&s); if(s==tail->data) sisip_akhir(); else sisip_sesudah(s); } break; case 5 : if(head == NULL && tail == NULL) gadel(); else if(head == tail) hapus_satu(); else
Siti yuliyanti
: ");
: ");
Page 7
MODUL PEMROGRAMAN 2
hapus_awal(); break; case 6 : if(head == NULL && tail == NULL) gadel(); else if(head == tail) hapus_satu(); else hapus_akhir(); break; case 7 : printf("Data yang dihapus : "); scanf("%d", &data); if(head == NULL && tail == NULL) gadel(); else if(data == head->data && data == tail->data && head == tail) hapus_satu(); else if(data == head->data) hapus_awal(); else if(data == tail->data) hapus_akhir(); else hapus_tengah(data); break; } fflush(stdin); printf("Lagi (y/t) ? "); scanf("%c", &lagi); } }
system(“PAUSE”) digunakan untuk menghentikan program sejenak. system(“CLS”) digunakan untuk menghapus layar. kedua command tersebut membutuhkan <stdlib.h> sama hal nya dengan penggunaan alokasi memori yang menggunakan malloc() , sizeof() , dan free() .
Siti yuliyanti
Page 8
