Linked List

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

SINGLE LINKED LIST I.

Tujuan 1. Memahami pengertian linked list, gunanya dan dapat mengimplementasikan dalam pemrograman 2. Dapat mengidentifikasi permasalahan-permasalahan pemrograman yang harus diselesaikan dengan menggunakan linked list, sekaligus menyelesaikannya

II.

Dasar Teori

Pengolahan data yang kita lakukan menggunakan komputer seringkali mirip dengan ilustrasi di atas, yang antara lain berupa penyimpanan data dan pengolahan lain dari sekelompok data yang telah terorganisir dalam sebuah urutan tertentu. Salah satu cara untuk menyimpan sekumpulan data yang kita miliki adalah menggunakan array. Telah kita bicarakan dalam bagian sebelumnya, keuntungan dan kerugian pemakaian array untuk menyimpan sekelompok data yang banyaknya selalu berubah dan tidak diketahui dengan pasti kapan penambahan atau penghapusan akan berakhir. Single Linked List Single linked list atau biasa disebut linked list terdiri dari elemenelemen individu, dimana masing-masing dihubungkan dengan pointer tunggal. Masing-masing elemen terdiri dari dua bagian, yaitu bagian data/informasi yang disimpan dan bagian pointer yang disebut dengan pointer next. Dengan menggunakan struktur two-member seperti ini, linked list dibentuk dengan cara mengarahkan pointer next dari suatu elemen ke elemen yang mengikutinya seperti gambar 2.2. Pointer next pada elemen terakhir merupakan NULL, yang menunjukkan akhir dari suatu list. Elemen pada awal suatu list disebut head, dan elemen terakhir dari suatu list disebut tail. Untuk mengakses elemen dalam linked list, dimulai dari head dan menggunakan pointer next dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai. Dengan 1

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

single linked list, list dapat dilintasi hanya satu arah dari head ke tail karena masing-masing elemen tidak terdapat link dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses elemen sebelumnya, kita harus mulai dari head. Secara konseptual, linked list merupakan deretan elemen yang berdampingan. Akan tetapi, karena elemen-elemen tersebut dialokasikan secara dinamis (menggunakan malloc), sangat penting untuk diingat bahwa kenyataannya, linked list akan terpencar-pencar lokasinya di memori seperti Gambar 2.3. Pointer dari elemen ke elemen (pointer next) berarti sebagai penjamin bahwa semua elemen dapat diakses. Representasi Simpul (Node) Struktur node pada linked list merupakan suatu simpul(node) yang berisi pointer ke suatu data yang merupakan data dirinya sendiri. Model struktur dari linked list tersebut dalam C adalah sebagai berikut: typedef struct data_int Node; struct data_int { int data; Node *next; }; Dalam hal ini, tipe Node berisi : ‰

Informasi berupa data, serta

‰ Pointer bernama next yang menunjuk ke obyek bertipe Node dilanjutkan dengan deklarasi global dari pointer ke struktur (pointer to struct) di atas sebagai berikut: Node *head = NULL; Node *p; Dengan adanya pendeklarasian head sebagai sebuah variabel bertipe pointer yang menunjuk ke obyek bertipe Node) melalui pernyataan: Node *head = NULL; maka head akan berisi NULL (artinya linked list belum memiliki simpul) Catatan : NULL adalah konstanta yang didefinisikan pada file stdio.h Selain itu juga dideklarasikan variabel p sebagai sebuah pointer to Node juga (tanpa inisialisasi) yang akan digunakan sebagai pointer yang menunjuk kepada simpul yang akan dibuat. Pembentukan simpul pertama dilakukan melaui serangkaian pernyataan berikut : 2

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

1) p = (Node *) malloc(sizeof(Node)); 2) p->data = 11511; 3) p->next = NULL; 4) head = p; Delete Dalam single LINKED LIST -

Fungsi delete pada linked list meliputi : delete simpul pertama (head) dari linked list delete setelah simpul tertentu delete simpul terakhir

Penghapusan Simpul Pertama: Algoritma: • cari node yang akan di hapus dengan node hapus • sambung linked list dengan mengarahkan head->next=hapus>next,sehingga linked list tidak putus • hapus data denga free(hapus) dan set hapus=NULL. Penghapusan Setelah Simpul Tertentu Untuk melakukan delete setelah node tertentu dari linked list diperlukan dua buah pointer bantuan berupa pointer after sebagai penanda node yang akan dihapus setelahnya dan pointer hapus untuk menandai simpul yang akan dihapus. Alogoritma: • cari node yang akan dihapu dengan node hapus • cek data terakhie dengan mengeset while(hapus->next!=NULL),jika hapus next->=NULL maka delete awal, jika tidak maka terus cek hingga ketemu hapus->next=NULL. • set prev=hapus,agar saat looping prev menyimpan alamat hapus yang sebelumnya. • sambung Linked List dengan prev->next=NULL,lalu hapus dengan free(hapus),hapus=NULL. Penghapusan Simpul Terakhir Untuk melakukan delete node terakhir dari linked list diperlukan dua buah pointer bantuan berupa pointer prevhapus sebagai penanda node yang 3

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

akan dihapus setelahnya dan pointer hapus untuk menandai simpul yang akan dihapus. Algoritma: • cari node yang akan dihapus dengan variable x • cek dimana tempat data x,jika di awal maka delete awal,jika akhir maka delete akhir. • jika x ketemu di tengah,tandai dengan pointer hapus dan arahkan pointer prev->next=hapus->next agar linked list tidak terputus. • lalu hapus dengan free(hapus) dan mengeset hapus=NULL. III.

Percobaan

Linked List DELETE AWAL #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int data; node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_awal(); void tampil(); main() { char jawab; sisip_akhir(); printf("ingin menghapus data pertama?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') 4

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

{ delete_awal(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("masukkan Data:"); scanf("%d",&p->data); fflush(stdin); p->next=NULL; return 1; } } void sisip_akhir() { node *tail; char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; 5

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

tail->next=p; tail=tail->next; } printf("ingin memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_awal() { node *hapus; hapus=head; head=hapus->next; free(hapus); hapus=NULL; } void tampil() { node *hasil; hasil=head; printf("data\n"); while(hasil!=NULL) { printf("%d\n",hasil->data); hasil=hasil->next; } }

6

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

DELETE AWAL STRUCT #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { char nama[10]; int no; int nilai; node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_awal(); void tampil(); main() { char jawab; sisip_akhir(); printf("ingin menghapus data pertama?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') { delete_awal(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("no = "); scanf("%d",&p->no); 7

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

fflush(stdin); printf("nama mahasiswa ="); gets(p->nama); fflush(stdin); printf("nilai ="); scanf("%d",&p->nilai); p->next=NULL; return 1; } } void sisip_akhir() { node *tail; char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; tail->next=p; tail=tail->next; } printf("ingin memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_awal() 8

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

{ node *hapus; hapus=head; head=hapus->next; free(hapus); hapus=NULL; } void tampil() { node *hasil; printf("NO\tNAMA\tNILAI\n"); hasil=head; while(hasil!=NULL) { printf("%d\t%s\t%d\n",hasil->no,hasil->nama,hasil->nilai); hasil=hasil->next; } }

Analisa Delete Awal Fungsi delete diawal menggunakan pointer bantuan *hapus , kemudian pointer hapus bagian next di assignment ke head agar hapus->next selalu menjadi pointer penunjuk data yang pertama hingga tidak ada lagi data yang di inputkan . Kemudian data yang ditunjuk oleh pointer hapus akan di hapus . 9

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

DELETE AKHIR #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int data; node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_akhir(); void tampil(); main() { char jawab; sisip_akhir(); printf("ingin menghapus data terakhir?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') { delete_akhir(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("masukkan Data:"); scanf("%d",&p->data); fflush(stdin); p->next=NULL; 10

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

return 1; } } void sisip_akhir() { node *tail; char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; tail->next=p; tail=tail->next; } printf("ingin memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_akhir() { node *prev; node *hapus; hapus=head; while(hapus->next!=NULL) { 11

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

prev=hapus; hapus=hapus->next; } prev->next=NULL; free(hapus); hapus=NULL; } void tampil() { node *hasil; hasil=head; printf("data\n"); while(hasil!=NULL) { printf("%d\n",hasil->data); hasil=hasil->next; } }

DELETE AKHIR STRUCT #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { char nama[10]; int no; int nilai; 12

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_akhir(); void tampil(); main() { char jawab; sisip_akhir(); printf("ingin menghapus data terakhir?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') { delete_akhir(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("no = "); scanf("%d",&p->no); fflush(stdin); printf("nama mahasiswa ="); gets(p->nama); fflush(stdin); printf("nilai ="); scanf("%d",&p->nilai); p->next=NULL; return 1; } } void sisip_akhir() { node *tail; 13

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; tail->next=p; tail=tail->next; } printf("ingin memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_akhir() { node *prev; node *hapus; hapus=head; while(hapus->next!=NULL) { prev=hapus; hapus=hapus->next; } prev->next=NULL; free(hapus); hapus=NULL; 14

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

} void tampil() { node *hasil; printf("NO\tNAMA\tNILAI\n"); hasil=head; while(hasil!=NULL) { printf("%d\t%s\t%d\n",hasil->no,hasil->nama,hasil->nilai); hasil=hasil->next; } }

Analisa Delete Di akhir Fungsi delete diakhir menggunakan 2 pointer bantuan yaitu *hapus dan *prev , pertama pointer hapus di assignment ke head agar pointer hapus memeriksa / mencari data yang akan dihapus dari awal hingga data NULL . update posisi hapus hingga menunjuk posisi terakhir . Kemudian arahkan pointer prev pada data sebelum data yang ditunjuk pleh ponter hapus / data terakhir (prev=hapus), pointer prev ( menunjuk data sebelumnya agar data terakhir bagian nextnya dapat di-NULLkan ) kemudian NULLkan next nya ( jadi data terakhir ).Hapus bagian pointer hapus . 15

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

DELETE SETELAH NODE TERTENTU #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int data; node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_after(); void tampil(); main() { char jawab; sisip_akhir(); printf("apakah ingin menghapus diinputkan?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') { delete_after(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("masukkan Data:"); scanf("%d",&p->data); fflush(stdin);

data

awal

yang

telah

16

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

p->next=NULL; return 1; } } void sisip_akhir() { node *tail; char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; tail->next=p; tail=tail->next; } printf("mau memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_after() { int x; node *cari; node *hapus; cari=head; 17

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("setelah data ke berapa data yang ingin di hapus?"); scanf("%d",&x); while(cari->data!=x) { if(cari->next==NULL) printf("data no.%d tidak ada dalam linked list\n",x); else { cari=cari->next; } } hapus=cari->next; cari->next=hapus->next; free(hapus); hapus=NULL; } void tampil() { node *hasil; hasil=head; printf("data\n"); while(hasil!=NULL) { printf("%d\n",hasil->data); hapus=hapus->next; } }

DELETE SETELAH NODE TERTENTU STRUCT 18

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

#include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { char nama[10]; int data; int nilai; node *next; }; node *head; node *p; int allocate_node(); void sisip_akhir(); void delete_after(); void tampil(); main() { char jawab; sisip_akhir(); printf("apakah ingin menghapus diinputkan?(y/t)\njawab:"); scanf("%s",&jawab); if(jawab='y') { delete_after(); tampil(); } else tampil(); } int allocate_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) return 0; else { printf("no = "); scanf("%d",&p->data); fflush(stdin); printf("nama mahasiswa ="); gets(p->nama); fflush(stdin);

data

awal

yang

telah

19

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("nilai ="); scanf("%d",&p->nilai); p->next=NULL; return 1; } } void sisip_akhir() { node *tail; char jawab; tail=head; do { allocate_node(); if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) tail=tail->next; tail->next=p; tail=tail->next; } printf("mau memasukkan data lagi?(y/t)\njawab:"); scanf("%s",&jawab); fflush(stdin); } while(jawab!='t'); } void delete_after() { int x; node *cari; node *hapus; 20

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

cari=head; printf("setelah data ke berapa data yang ingin di hapus?"); scanf("%d",&x); while(cari->data!=x) { if(cari->next==NULL) printf("data no.%d tidak ada dalam linked list\n",x); else { cari=cari->next; } } hapus=cari->next; cari->next=hapus->next; free(hapus); hapus=NULL; } void tampil() { node *hasil; printf("NO\tNAMA\tNILAI\n"); hasil=head; while(hasil!=NULL) { printf("%d\t%s\t%d\n",hasil->data,hasil->nama,hasil->nilai); hasil=hasil->next; } }

21

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

Analisis Delete setelah node tertentu Fungsi delete diakhir menggunakan 2 pointer bantuan yaitu *hapus dan *cari untuk mencari dan menandai data yang bernilai sama dengan inputan . lalu set agar hapus=cari->next; cari->next=hapus->next; free(hapus); hapus=NULL; untuk menghapus data yang telah ditemukan menggunakan pointer bantuan cari . 4.MENU INSERT dan DELETE #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int data; node *next; }; node *head; node *p; int allocate_node(); 22

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

void menu(); void sisip(); void sisip_awal(); void sisip_akhir(); void sisip_after(); void sisip_before(); void del(); void del_awal(); void del_akhir(); void del_after(); void tampil(); main() { do { menu(); } while(1); } void menu() { int pil; printf("MENU UTAMA\n"); printf("1.Insert\n2.Delete\n3.Tampil\n4.Keluar\n"); printf("pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1:allocate_node(); sisip(); break; case 2: del(); break; case 3:tampil(); break; case 4:exit(0); break; } printf("\n"); } 23

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

void sisip() { int pil; printf("MENU INSERT\n"); printf("1.Insert Awal\n2.Insert Akhir\n3.Insert After\n4.Insert Before\n"); printf("pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1: sisip_awal(); break; case 2: sisip_akhir(); break; case 3: sisip_after(); break; case 4: sisip_before(); break; } } int allocate_node() { int nilai; printf("masukkan nilai data:"); scanf("%d",&nilai); p=(node *)malloc(sizeof(node)); if(p==NULL) { printf("pemesanan alokasi memori GAGAL\n"); return 0; } else { p->data=nilai; p->next=NULL; return 1; } } void sisip_awal() { 24

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

if(head==NULL) head=p; else { p->next=head; head=p; } } void sisip_akhir() { node *tail; tail=head; if(allocate_node==0) exit(0); if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) { tail=tail->next; } tail->next=p; tail=tail->next; } } void tampil() { node *baca; baca=head; while(baca!=NULL) { 25

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("%d\n",baca->data); baca=baca->next; } } void sisip_before() { node *bef; node *pbef; int x; if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } fflush(stdin); printf("nilai tersebut akan disisipkan sebelum data?"); scanf("%d",&x); bef=head; if(head->data==x) { p->next=head; head=p; } else { do { pbef=bef; if(bef->next==NULL) { printf("data %d tidak ada dalam linked list\n",x); exit(0); } else { bef=bef->next; } } while(bef->data!=x); p->next=bef; 26

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

pbef->next=p; } } void sisip_after() { int x; node *after;

if(allocate_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } after=head; printf("\n"); printf("data akan disisipkan setelah data?"); scanf("%d",&x); while(after->data!=x) { if(after->next==NULL) printf("data tidak ada dalam linked list\n"); else after=after->next; } p->next=after->next; after->next=p; } void del() { int pil; printf("MENU INSERT\n"); printf("1.Delete Awal\n2.Delete Before\n"); printf("masukkan pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1:

Akhir\n3.Delete

After\n4.Delete

27

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

del_awal(); break; case 2: del_akhir(); break; case 3: del_after(); break; } } void del_awal() { node *hapus; hapus=head; head=hapus->next; free(hapus); hapus=NULL; } void del_akhir() { node *prev; node *hapus; hapus=head; while(hapus->next!=NULL) { prev=hapus; hapus=hapus->next; } prev->next=NULL; free(hapus); hapus=NULL; } void del_after() { int x; node *prev; node *hapus; prev=head; printf("setelah data ke berapa data yang ingin di hapus?"); 28

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

scanf("%d",&x); while(prev->data!=x) { if(prev->next==NULL) printf("data no.%d tidak ada dalam linked list\n",x); else { prev=prev->next; } } hapus=prev->next; prev->next=NULL; free(hapus); hapus=NULL; } Analisis : Fungsi main() hanya berisikan fungsi menu() .Program akan selesai jika memilih menu keluar yang berisi perintah exit(0). Sehingga program ini dapat menginput,hapus,dan tampilkan data linked list sesuai keinginan user nya. Sampai program selesai dengan memilih menu keluar . 5.MENU STRUCT #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int no; char nama[20]; float nilai; node *next; }; node *head; node *p; int allocated_node(); void menu(); void sisip(); void sisip_awal(); void sisip_akhir(); void sisip_after(); 29

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

void sisip_before(); void del(); void del_awal(); void del_akhir(); void del_after(); void tampil(); void main() { do { menu(); } while(1); } void menu() { int pil; printf("MENU UTAMA\n"); printf("1.Insert\n2.Delete\n3.Tampil\n4.Keluar\n"); printf("masukkan pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1:allocated_node(); sisip(); break; case 2: del(); break; case 3:tampil(); break; case 4:exit(0); break; } printf("\n"); } void sisip() { int pil; printf("\n"); 30

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("MENU INSERT\n"); printf("1.Insert Awal\n2.Insert Akhir\n3.Insert After\n4.Insert Before\n"); printf("masukkan pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1: sisip_awal(); break; case 2: sisip_akhir(); break; case 3: sisip_after(); break; case 4: sisip_before(); break; } printf("\n"); } int allocated_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) { printf("pemesanan alokasi memori GAGAL\n"); return 0; } else { printf("Masukkan NO.MHS:"); scanf("%d",&p->no); fflush(stdin); printf("Masukkan Nama MHS:"); gets(p->nama); fflush(stdin); printf("Masukkan Nilai MHS:"); scanf("%g",&p->nilai); fflush(stdin); p->next=NULL; return 1; printf("\n"); } 31

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

} void sisip_awal() { if(allocated_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } if(head==NULL) head=p; else { p->next=head; head=p; } fflush(stdin); ; } void sisip_akhir() { node *tail; tail=head; if(allocated_node==0) exit(0); if(head==NULL) { head=p; tail=p; } else { while(tail->next!=NULL) { tail=tail->next; } 32

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

tail->next=p; tail=tail->next; } } void tampil() { node *baca; baca=head; printf("NO\tNAMA\tNILAI\n"); printf("===========================\n"); while(baca!=NULL) { printf("%d\t%s\t%g\n\n",baca->no,baca->nama,baca->nilai); baca=baca->next; } } void sisip_before() { node *bef; node *pbef; int x; printf("\n"); if(allocated_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } fflush(stdin); printf("data tersebut akan disisipkan sebelum MHS.no?"); scanf("%d",&x); bef=head; if(head->no==x) { p->next=head; head=p; } else { 33

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

do { pbef=bef; if(bef->next==NULL) { printf("data %d tidak ada dalam linked list\n",x); exit(0); } else { bef=bef->next; } } while(bef->no!=x); p->next=bef; pbef->next=p; } } void sisip_after() { int x; node *after;

if(allocated_node==0) { printf("pemesanan memori GAGAL\n"); exit(0); } after=head; printf("\n"); printf("data akan disisipkan setelah MHS.no?"); scanf("%d",&x); while(after->no!=x) { if(after->next==NULL) printf("data tidak ada dalam linked list\n"); else after=after->next; 34

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

} p->next=after->next; after->next=p; } void del() { int pil; printf("\n"); printf("MENU INSERT\n"); printf("1.Delete Awal\n2.Delete Akhir\n3.Delete After\n"); printf("masukkan pilihan anda:"); scanf("%d",&pil); switch(pil) { case 1: del_awal(); break; case 2: del_akhir(); break; case 3: del_after(); break; } } void del_awal() { node *hapus; hapus=head; head=hapus->next; free(hapus); hapus=NULL; } void del_akhir() { node *prev; node *hapus; hapus=head; 35

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

while(hapus->next!=NULL) { prev=hapus; hapus=hapus->next; } prev->next=NULL; free(hapus); hapus=NULL; } void del_after() { int x; node *prev; node *hapus; prev=head; printf("setelah MHS.no ke berapa yang ingin di hapus?"); scanf("%d",&x); while(prev->no!=x) { if(prev->next==NULL) printf("MHS no.%d tidak ada dalam linked list\n",x); else { prev=prev->next; } } hapus=prev->next; prev->next=NULL; free(hapus); hapus=NULL; } Analisis : Fungsi main() hanya berisikan fungsi menu() .Program akan selesai jika memilih menu keluar yang berisi perintah exit(0). Sehingga program ini dapat menginput,hapus,dan tampilkan data linked list sesuai keinginan user nya. Sampai program selesai dengan memilih menu keluar . 36

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

6.SORTING DATA #include<stdio.h> #include<stdlib.h> typedef struct simpul node; struct simpul { int data; node *next; }; int allocated_node(); void menu(); void sisip(); void del(); void cari(); void tampil(); node *head=NULL; node *p; void main() { do { menu(); } while(1); } int allocated_node() { p=(node *)malloc(sizeof(node)); if(p==NULL) { printf("Pemesanan Memori GAGAL\n"); return 0; } else { printf("Masukkan Data:"); scanf("%d",&p->data); p->next=NULL; return 1; } } void menu() { int pil; 37

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("MENU\n"); printf("1.Insert\n2.Delete\n3.Tampil\n4.Cari Data\n5.Keluar\n"); printf("Masukkan Pilihan Anda:"); scanf("%d",&pil); switch(pil) { case 1:allocated_node(); sisip(); break; case 2:del(); break; case 3:tampil(); break; case 4:cari(); break; case 5:exit(0); default:printf("Pilihan Anda Salah\n"); break; } } void sisip() { node *bantu; node *prev; bantu=head; if(allocated_node==0) exit(0); if(head==NULL) { head=p; } else { while(bantu!=NULL) { if(p->datadata) { p->next=head; head=p; break; } else if(p->data>=bantu->data) { 38

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

if(bantu->next!=NULL) { prev=bantu; bantu=bantu->next; } else { bantu->next=p; break; } } else { p->next=bantu; prev->next=p; break; } } } } void del() { int x; int ketemu=1; node *hapus; node *prev; hapus=head; printf("Masukkan Data yang akan di Delete:"); scanf("%d",&x); if(hapus==NULL) { printf("Linked List kosong\n"); } else { while(hapus->data!=x) { if(hapus->next!=NULL) { prev=hapus; hapus=hapus->next; } else { ketemu=0; 39

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

printf("Data Tidak Ada Dalam Linked List\n"); } } if(ketemu!=0) { if(hapus==head) { head=hapus->next; free(hapus); hapus=NULL; } else { prev->next=hapus->next; free(hapus); hapus=NULL; } } } } void tampil() { node *baca=head; while(baca!=NULL) { printf("%d\n",baca->data); baca=baca->next; } } void cari() { int x; int ketemu=1,jumlah=0; node *bantu; bantu=head; printf("Masukkan Data Yang ingin dihitung:"); scanf("%d",&x); while(bantu!=NULL) { while(bantu->data!=x) { if(bantu->next!=NULL) { 40

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

bantu=bantu->next; } else { ketemu=0; break; } } if(ketemu!=0) { jumlah++; } bantu=bantu->next; } if(jumlah>0) printf("Data %d ditemukan sebanyak %d kali\n",x,jumlah); else printf("Datanya Gag ketemu Mas..\n"); }

41

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

FLOWCHART MENU SORTING • FLOWCHART MENU INSERT TERSUSUN

42

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

•

FLOWCHART DELETE

43

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

•

FLOWCHART CARI DATA

44

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

Analisis Linked list memudahkan dalam pemasukan atau penghapusan data baik terurut ataupun tidak, karena dengan linked list kemungkinan data terjaga sangat baik. Dan dari hasil percobaan yang dilakukan, ternyata program sorting baik itu data atau struct memakai program yang relative lebih simple dan lebih mudah. Ini berarti semakin menghemat penggunaan memori yang terpakai.

45

POLITEKNIK ELEKTRONIKA NEGERI SURABAYA INSTITUT TEKNOLOGI SEPULUH NOPEMBER

KESIMPULAN : 1. Single linked list atau biasa disebut linked list terdiri dari elemenelemen individu, dimana masing-masing dihubungkan dengan pointer tunggal. 2. Linked List Insert: a. Siapkan node yang akan disimpan, tempatkan pada variabel penampung dan cek lokasi, b. Cari posisi insert, c. Sambungkan. 3. Linked List Delete: a. Cari posisi node yang akan didelete, b. Sambungkan node agar linked list tidak terputus, c. Bebaskan lokasi dan NULL-kan pointer. 4. Insert terdiri dari insert awal, insert akhir, insert sebelum node tertentu dan insert sesudah node tertentu. 5. Delete terdiri dari delete awal, delete akhir dan delete sesudah node tertentu.

46