Struktur Data – Linked List

Soal Pendahuluan

1. Jelaskan perbedaan Linked List dengan Array dan sertai gambar permodelannya! Sebutkan keuntungan dan kerugiannya masin-masing struktur data tersebut!
2. Berikan contoh kasus kapan sebuah Linked List lebih baik digunakan dan kapan sebuah Array lebih baik digunakan serta alasannya!
3. Jelaskan dan pahami definisi Node, Single Linked List, Double Linked List, Single Circular Linked List dan Double Circular Linked List beserta gambar permodelannya!
4. Jelaskan operasi dasar yang dimiliki oleh Linked List berikut :   (Data bertipe int dan dianggap unik setiap menambah node, key yang digunakan adalah nilai integer dari data itu sendiri)

Algoritma dan Source Code Josephus Problem dengan Linked List

Josephus Problem adalah suatu masalah pengeksekusimatian terpidana – terpidana mati pada jaman dahulu kala. Sebenarnya ini bisa dianalogikan dengan jenis permainan anak – anak.

Berikut adalah penjelasan Josephus Problem dengan pendekatan permainan anak – anak yang sejenis :

Ada sebuah permaian yang dilakukan oleh (n) orang secara melingkar. Permainan itu adalah membilang bilangan dari 1 – (r). Barangsiapa memperoleh girilan untuk membilang bilangan r, dia akan kalah dan tidak boleh ikut permainan lagi. Setelah itu penghitungan dilanjtkan mulai dari 1 oleh orang setelahnya. Penghitungan pertama dimulai di player ke-(st). Permainan akan berakhir jika dan hanya jika ada satu orang yang tidak kalah.

Algoritma Dasar :

-          Melakukan penghitungan dimulai dari player ke-n

-          Penghitungan dilanjutkan ke player sebelah kanannya (player.next)

-          Jika mencapai player ke-n, dilanjutkan dengan player pertama (circular)

-          Jika hitungan sudah mencapai range yang telah ditentukan, lakukan proses remove. Player.next dituju ke player sebelah kanan dari player yang tereliminasi. Begitu seterusnya sampai First = Last (tinggal 1 player).

Struktur Data – Macam – macam Linked List

Berikut merupakan macam – macam linked list :

-         Singly Linked List :

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.

Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.

-          Double Linked List :

Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.

-           Single Circular Linked List :

Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

Algoritma – Mengubah Operasi Infix ke Dalam Bentuk PostFix

Program ini merupakan program pengkoversian dari operasi Infix ke dalam operasi postfix.  Algoritma dasar dari program ini adalah bagaimana cara kita membaca atau mengartika bentuk infix tersebut ke dalam betuk postfix. Kemudian jika bertemu dengan tanda kurung, maka akan dilakukan pop semua elemen stack sampai menemukan kurung tutup pasangannya.

Bentuk post Fix merupakan betuk lain dari operasi matematika. Biasanya bentuk ini digunakan oleh mesin penghitung atau computer untuk memproses data yang lebih lanjut.

Berikut meupakan source code dari program ini :

Algoritma – Mengoperasikan Operasi Matematika Bentuk PostFix

Program ini meruapakan program pengitung operasi matematika dalam bentuk PostFix.  Algoritma dalam program ini sama dengan algoritma kita memahami bentuk PostFix itu sendiri.

Jika bertemu dengan angka, maka akan dipush. Jika bertemu dengan operator maka akan dilakukan pop kemudian akan dioperasikan kedua angka terakhir yang  tersimpan di dalam Stack tersebut. Hasil terakhir merupakan angka yang terakhir disimpan di dalam stack.  Jika isi stack masih ada, maka terjadi kesalahan di dalam penulisan input operasi postfix tersebut

Berikut merupakan source code dalam bahasa JAVA :

Algoritma – Mengecek Kurung Dalam Operasi Matematika

Program ini merupakan program untuk memeriksa suatu inputan string yang merupakan suatu operasi matematika apakah sudah mempunyai  jumlah kurung buka dan kurung tutup yang pas dan benar.

Program ini merupakan salah satu program yang mengimplementasikan penggunaan STACK.

Algoritma dasar program ini adalah :

1. Mengecek tiap karakter sampai bertemu NULL

2. Jika bertemu kurung buka, maka akan dilakukan proses push(); namun, sebelum dilakukan proses push, haruslah dicek,   apakah stack masih dapat diisi atau tidak. Sehingga dibutuhkan  fungsi tambahan, dapatDiisi(); untuk mengecek apakah isi stack  sudah penuh atau belum

3. Jika bertemu kurung tutup, maka akan dilakukan proses pop(); yang akan ditampung pada variable tampung. Seperti halnya proses push();, proses pop(); harus dicek terlebih dahulu, apakah   stack masih berisi. Untuk itu, diperlukan fungsi dapatDiambil(); Pada proses pop kali ini juga harus mengecek apakah kurung tutup pada array saat pengecekan sama dengan isi stack array top atau tidak. Jika tidak, maka operasi matematika tersebut tidak valid

Struktur Data – Pengertian Stack

Secara bahasa, Stack berarti tumpukan. Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data yang organisasi atau strukturnya bersifat tumpukan atau menyerupai tumpukan.

Secara ilustrasi, stack dapat digambarkan dengan gambar di samping.

“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatu koleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namun pertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasuki tumpukan namun terakhir saat keluar dari tumpukan.

Di dalam gambar juga terlihat urutan masuk dan keluar yang berkebalikan. Elemen yang masuk pertama akan keluar erakhir dan sebaliknya. Prinsip ini telah dikenal dalam struktur data dengan nama prinsip LIFO (Last In First Out).