Laporan MODUL 2 Farhan [PDF]

Citation preview

LAPORAN PRAKTIKUM STRUKTUR DATA MODUL 2 SINGLE LINKED LIST Dosen Pengampu Achmad Arif Alfin, S.Si., M.M.T



Oleh : Nama Mahasiswa



: Muhammad Farhan Musthafa



NPM – Kelas



: 20562020021 – A1



Tanggal Pratikum



: 19 Maret 2021



Tanggal Pengumpulan



: 26 Maret 2021



PROGRAM STUDI TEKNIK KOMPUTER FAKULTAS TEKNIK UNIVERSITAS ISLAM KADIRI – KEDIRI 2021



BAB I PENDAHULUAN 1.1. Latar Belakang Pada modul 1 (satu) sebelumnya membahas materi tipe struktur data Array yang digunakan untuk menyimpan data dalam indeks yang terurut. Terdapat kelemahan jika kita menggunakan tipe struktur data Array sebagai media penyimpanan, dimana panjang dari data harus telah ditentukan terlebih dahulu dan semisal kita akan menambah data lagi pasti tidak akan bisa. Untuk mengatasi kelemahan dari tipe struktur data Array, ada cara lain yang dapat digunakan yaitu menggunakan linked list. Linked list merupakan salah satu tipe struktur data yang dapat kita pilih untuk menyimpan data dengan jumlah nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Bentuk dari linked list ini paling sederhana, dimana sekumpulan nodes yang terhubung menjadi satu yang membentuk untaian. Masing masing node menyimpan data dan “alamat” yang akan menghubungkan node tersebut dengan node sesudahnya (next node). Linked List dibagi menjadi Single Linked List, Double Linked List, Circular Linked List, dll. Representasi dari sebuah linked list, dapat dilihat pada gambar 1 berikut ini :



Gambar 1.1. Linked List



1.2. Tujuan Pratikum Setelah mengikuti praktikum ini, Mahasiswa diharapkan mampu untuk: 1. Mendefinisikan konsep single linked list dan kegunaannya. 2. Mengidentifikasi studi kasus yang harus diselesaikan menggunakan single linked list. 3. Mengimplementasikan tipe struktur data single linked list ke dalam aplikasi java dan netbeans.



20



BAB II DASAR TEORI 2.1. Pengertian Single linked list Pada modul 2 ini, akan dijelaskan materi tentang single linked list. Pengertian dari single linked list adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer (lihat gambar 1.1). Di dalam sebuah single linked list, terdapat 1 pointer yang menjadi gambaran besar, yaitu pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri. Operasi yang dapat dilakukan pada linked list adalah menambahkan node (insert) dan menghapus node (delete). Push (single) merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert di depan (pushDepan) ataupun insert di belakang (pushBelakang). Operasi pushDepan berarti data yang paling baru akan dimasukkan dan akan ditempatkan berada di depan data lainnya, sedangkan pushBelakang berarti data yang paling baru akan berada di belakang data lainnya dan dihubungkan dengan next.



21



2.2. Langkah-langkah dalam pengerjaan single linked list 1.



Class Node.



Langkah pertama dalam membuat program linked list adalah mendefinisikan apa itu node. Dalam pemrograman Java NetBean, sebaiknya pendefinisian node ini dibuat dalam sebuah class. Berikut source code class node pada Java NetBean :



class Nodes { int value; Nodes next; Nodes() { } Nodes(int value) { this(value, null); } Nodes(int value, Nodes next) { this.value = value; this.next = next; } }



2.



Inisialisasi.



22



Proses inisialisasi ini digunakan untuk mendeklarasikan sekaligus memberikan nilai awal pada pointer head dan tail. Berikut source code inisialisasi pada Java NetBean: public class Node { private Nodes head; private int size; public Node(){ head = new Nodes(0); size = 0; } public Node(Nodes head, int size) { this.head = head; this.size = size; } public void insertHead(int x) { insertN(x, 0); } public void insertTail(int data) { insertN(data,size); }



3. isEmpty. Proses isEmpty ini digunakan untuk mengetahui linked list dalam keadaan kosong (null). Berikut source code isEmpty pada Java NetBean : Boolean isEmpty() { Return size == 0; }



4.



Size.



23



Proses size ini digunakan untuk mengetahui banyak node pada linked list. Size akan bertambah 1 setiap ada node baru yang ditambahkan pada linked list dan size akan berkurang 1 setiap ada penghapusan node. int size() { return size; }



2.3. CONTOH KASUS 1.



Bagaimana cara insert data, sehingga diperoleh hasil data “ 6 → 9 → 11 “ public static void main(String args[]) { SingleLinkList myList SingleLinkList(); Assert myList.isEmpty() myList.insertHead(6); myList.insertHead(9); myList.insertHead(11); System.out.println(myList); } }



=



new



2. Dari data nomer 1, bagaimana cara insert data x=3 dengan menggunakan pushDepan, sehingga diperoleh hasil “ 3 → 6 → 9 → 11 “



Public void insertN(int data, int position) { checkBounds(position, 0, size); Nodes p = head; for (int i = 0; i < position; ++i) { p = p.next; } Nodes nodes = new Nodes(data); nodes.next = p.next; p.next = nodes; size++; }



Hasil Running dari contoh kasus insert nomor 1 dan 2 adalah sebagai berikut



24



Gambar 2.1. Hasil Running operasi insert



Pop merupakan kebalikan dari push, yaitu operasi delete, dimana di dalam linked list mempunyai 2 kemungkinan delete, yaitu melalui depan (popDepan) ataupun belakang (popBelakang). popDepan berarti data yang akan dihapus adalah data paling depan, sedangkan popBelakang berarti data yang akan dihapus adalah datang paling akhir. CONTOH KASUS ; 1.



Dari data : “ 3 → 6 → 9 → 11 “, bagaimana cara hapus data x=3 dengan menggunakan popDepan, sehingga diperoleh hasil “ 6 → 9 → 11 “



public void deleteN(int position) { checkBounds(position, 0, size - 1); Nodes p = head; for (int i = 0; i < position; ++i) { p = p.next; } Nodes destroy = p.next; p.next = p.next.next; destroy = null; size--; }



Hasil Running dari contoh kasus delete nomer 1 adalah sebagai berikut :



25



Gambar 2.2. Hasil Running Operasi Delete



BAB III 26



LATIHAN PRAKTIKUM



BAB IV



27



TUGAS PRAKTIKUM 1.



Misalkan anda memiliki angka acak 6, 90, 3, 33, 11. Bagaimana cara melakukan insert pada single linked list sehingga diperoleh hasil “ 33 → 6 → 90 → 3 → 11“ ? Sertakan code dan analisanya.



A. Source Code



Gambar



Gambar 4.2. Tampilan Source Code



28



Gambar 4.3. Tampilan Source Code



Gambar 4.4. Tampilan Source Code



29



B. Analisa Pertama membuat public class node untuk mendifinisikan nilai awal ,lalu membuat class Node ,setelah itu kita melakukan insertHead dengan jumlah nilainya C.Output



Gambar 4.5. Tampilan Output



30



2. Berdasarkan jawaban nomor 1, bagaimana source code menghapus node head sehingga diperoleh rangkaian linked list seperti ini “ 6 → 90 → 3 → 11 “ ? A. Source Code Gambar 4.6.



Tampilan Source Code



B. Analisa Dengan menambahkan Source Code myList.deleteHead (); maka tampilan angka depan akan terhapus C. Output



Gambar 4.7. Tampilan Output



31



3. Berdasarkan jawaban nomor 2, bagaimana source untuk menghapus node tail sehingga diperoleh hasil seperti berikut ““ 6 → 90 → 3” ? A. Source Code



Gambar 4.8. Tampilan Source Code



B. Analisa Untuk menghapus angka terakhir atau nodeTail kita masukkan Source Code myList.deleteTail();



C. Output



Gambar 4.9. Tampilan Output



32



4. Berdasarkan jawaban nomor 3, bagaimana source untuk menambahkan data 72 pada node di depan node tail sehingga diperoleh hasil seperti berikut “6 → 90 → 72 → 3” ?



A. Source Code



Gambar 4.10. Tampilan Source Code



B. Analisa Untuk menambahkan data didepan nodeTail Source Code yang digunakan ialah insertN(int data,position) sehingga Source Code yang kita masukkan untuk membuat angka 72 di depan nodeTail ialah myList.insertN(72,2); C. Output



Gambar 4.11. Tampilan Output



33



5. Berdasarkan jawaban nomor 4, bagaimana source untuk menghapus data 90 pada node setelah node head sehingga diperoleh hasil seperti berikut “6 → 72 → 3” ? A. Source Code



Gambar



B. Analisa Untuk menghapus data 90 pada node setelah node head kita menggunakan Source Code deleteN(position); sehingga Sorce Code yang perlu kita isi yaitu myList. deleteN(1); Angka 1 diperoleh dari tata letak angka 90 yang berada setelah angka 6 yang memiliki position 0 C. Output



34



Gambar 4.13. Tampilan Output



BAB V KESIMPULAN A. Analisa Praktikum Dalam pembuatan program linked list langkah yang harus kita lakukan adalah mendefinisikan node dengan membuat class Node lalu melakukan proses inisialisasi untuk mendeklarasikan sekaligus memberikan nilai awal pada pointer head dan tail menggunakan Source Code Public class node ,setelah itu kita tinggal membuat program” yang ingin kita gunakan seperi pertama memasukkan insert data dengan insertHead, menghapus data dengan deleteHead, menghapus data bagian belakang/terakhir dengan deleteTail menambahkan data didepan /dibelakang



data



dengan



insertN(int



data,position),menghapus



data



setelah/sesudah data dengan deleteN(position).



B. Kesimpulan Single linked list adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer (lihat gambar 1.1). Di dalam sebuah single linked list, terdapat 1 pointer yang menjadi gambaran besar, yaitu pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri. Operasi yang dapat dilakukan pada linked list adalah menambahkan node (insert) dan menghapus node (delete).



35



DAFTAR PUSTAKA MODUL 2 SINGLE LINKED LIST (Senarai Berantai)



36



LAMPIRAN A. Tugas Pendahuluan 1. Jelaskan pengertian dari linked list! Jelaskan juga bagaimana cara menambahkan dan menghapus node pada linked list? 2. Apa perbedaan antara linked list dan array? 3. Apa keuntungan dan kerugian implementasi linked list dibandingkan dengan array? 4. Apa yang dimaksud dengan FIFO dan LIFO? 5. Jelaskan perbedaan antara single dan doubly linked list! Jelaskan keuntungan dan kerugian masing-masing! 6. Apa itu ordered linked list! Jawaban 1. Linked List adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan ke elemen lain melalui pointer. Pointer juga merupakan alamat dari sebuah elemen. Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya. Penghapusan node dilakukan dengan memutus rantai node kemudian menghapus node. Jika node berada di tengah rangkaian, rangkaian yang terputus perlu disambung kembali. Untuk memudahkan penghapusan simpul dibutuhkan dua cursor sebagai simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai acuan awal simpul dalam rangkaian. 2. Perbedaan utama antara daftar Array dan Linked berkaitan dengan struktur mereka. Array adalah struktur data berbasis indeks di mana setiap elemen terkait dengan indeks. Di sisi lain, daftar Linked bergantung pada referensi di mana setiap node terdiri dari data dan referensi ke elemen sebelumnya dan selanjutnya. Perbedaan signifikan lainnya antara array dan daftar tertaut adalah bahwa Array memiliki ukuran tetap dan harus dinyatakan sebelumnya, tetapi Daftar Tertaut tidak terbatas pada ukuran dan memperluas dan kontrak selama eksekusi. 3. Keuntungannya adalah jenis data yang berbeda dapat di-link dan operasi remove atau insert hanya dilakukan dengan mengubah pointer nya saja. Kerugiannya adalah diperlukan ruang tambahan untuk tempat field pointer dan diperlukan waktu yang lebih banyak untuk mencari node dalam linked list.



37



4. FIFO (first in first out) memiliki pengertian Masuk Pertama, Keluar Pertama, yang abstak dalam cara mengatur dan manipulasi data yang relatif terhadap waktu dan prioritas. LIFO (Last In First Out) memiliki pengertian terakhir masuk, pertama keluar. Dalam ilmu komputer dan teori queueing ini merujuk kepada cara item disimpan dalam beberapa jenis struktur data yang diproses. 5. Single Linked List, suatu yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke null. Doubly Linked List, suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menujuk ke null. Keuntungan Single Linked List adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu. Kerugiannya adalah pemakaian memory lebih besar. Keuntungan Doubly Linked List adalah Dapat melakukan reverse traversal. Kerugiannya adalah diperlukan ruang tambahan untuk tempat field pointer. 6. Ordered linked list adalah Daftar tertaut yang itemnya disimpan dalam urutan tertentu.



38



B. Jawaban “Source Code” Pratikum 1. Soal Pratikum nomor 1



39



public class Node { private Nodes head; private int size; public Node(){ head = new Nodes(0); size = 0; } public Node(Nodes head, int size) { this.head = head; this.size = size; } public void insertHead(int x) { insertN(x, 0); } public void insertTail(int data) { insertN(data,size); } private void insertN(int data, int position) { checkBounds(position, 0, size); Nodes p = head; for (int i = 0; i < position; ++i) { p = p.next; } Nodes nodes = new Nodes(data); nodes.next = p.next; p.next = nodes; size++; }



40



private void checkBounds(int position, int low, int



high) { if (position > high || position < low) {



throw new IndexOutOfBoundsException(position + ""); } } class Nodes { int value; Nodes next; Nodes() { } Nodes(int value) { this(value, null); } Nodes(int value, Nodes next) { this.value = value; this.next = next; } } public boolean isEmpty() { return size == 0;



//Checks if the list is empty



(true if its empty) } public int size() { return size; }



41



public static void main(String args[]) { SingleLinkList myList = new SingleLinkList(); assert myList.isEmpty(); // input data dari depan myList.insertHead(11); myList.insertHead(3); myList.insertHead(90); myList.insertHead(6); myList.insertHead(33); System.out.println(myList); } }



42



2. Soal Pratikum nomor 2 public static void main(String args[]) { SingleLinkList myList = new SingleLinkList(); assert myList.isEmpty(); // input data dari depan myList.insertHead(11); myList.insertHead(3); myList.insertHead(90); myList.insertHead(6); myList.insertHead(33); System.out.println(myList); myList.deleteHead(); System.out.println(myList); } }



43



3. Soal Pratikum nomor 3 public static void main(String args[]) { SingleLinkList myList = new SingleLinkList(); assert myList.isEmpty(); // input data dari depan myList.insertHead(11); myList.insertHead(3); myList.insertHead(90); myList.insertHead(6); myList.insertHead(33); System.out.println(myList); myList.deleteHead(); System.out.println(myList); myList.deleteTail(); System.out.println(myList); } }



44



4. Soal Pratikum nomor 4 public static void main(String args[]) { SingleLinkList myList = new SingleLinkList(); assert myList.isEmpty(); // input data dari depan myList.insertHead(11); myList.insertHead(3); myList.insertHead(90); myList.insertHead(6); myList.insertHead(33); System.out.println(myList); myList.deleteHead(); System.out.println(myList); myList.deleteTail(); System.out.println(myList); myList.insertN(72,2); System.out.println(myList); } }



5. Soal Pratikum nomor 5



45



public static void main(String args[]) { SingleLinkList myList = new SingleLinkList(); assert myList.isEmpty(); // input data dari depan myList.insertHead(11); myList.insertHead(3); myList.insertHead(90); myList.insertHead(6); myList.insertHead(33); System.out.println(myList); myList.deleteHead(); System.out.println(myList); myList.deleteTail(); System.out.println(myList); myList.insertN(72,2); System.out.println(myList); myList.deleteN(1); System.out.println(myList); } }



46