Mid Semester Summary

Rangkuman Mid Semester

Pada kali ini, kita akan mereview ulang semua yang kita telah belajar dalam jangka waktu setengah semester ini. Rangkuman ini akan meliputi Linked list, stack and queue, hash table, dan juga binary search tree.

Linked List

1. Single Linked List

Single Linked list adalah salah satu bentuk Linked list. Seperti yang kita ketahui, linked list bentuknya dinamis, itu artinya ukuran linked list tidak terbatas. linked list bisa dibilang mirip dengan array, salah satu data struktur, tetapi array mempunyai ukuran yang statis atau tidak bisa diubah setelah diberitahu ukurannya.

Single linked list menggunakan teknik allocation memory, dimana kita mengalokasi sebuah memori untuk menyimpan data-data kita. Nah, memori-memori ini nantinya akan dihubung dengan menggunakan satu pointer. Itulah mengapa data struktur ini disebut single linked list. Berikut adalah contoh single linked list.

2. Double Linked List

Double linked list merupakan bentuk lain dari linked list. Jika single linked list mempunya hanya satu pointer untuk menyimpan alamat memori node selanjutnya. Maka, double linked list mempunyai dua pointer untuk menyimpan data selanjutnya dan sebelumnya. Berikut adalah contoh double linked list.

3. Circular Linked List

Circular linked list adalah bentuk lain dari Single linked list. Jika pada single linked list kita lihat bahwa data paling akhir mempunyai pointer yang tidak menyimpan alamat, maka di circular linked list data terakhir selalu menyimpan alamat data yang paling pertama, sehingga kita bisa melakukan traversal secara circular. Berikut adalah perbedaan Si ngle linked list dengan circular linked list.

Stack and Queue

1. Stack

Stack adalah suatu konsep dalam data struktur. Stack mempunyai bentuk seperti tumpukan piring dan menganut prinsip First In Last Out (FILO). Berikut contoh penggunaan Stack.

2. Queue

Queue adalah konsep sebuah data struktur. Jika stack merupakan tumpukan piring, maka queue adalah sebuah antrian. queue menganut prinsip First In First Out (FIFO). Berikut contoh queue.

Hash Table

Hash tables adalah suatu bentuk data struktur yang berguna untuk memetakan suatu value dengan mengassignkan key ke value tersebut. Hash tables berguna lebih banyak untuk tujuan keamanan, karena esensi dari hash table adalah mengenkripsi suatu petunjuk dari sebuah data agar tidak mudah diakses.

Untuk menciptakan key dari data yang akan di hash, maka dibutuhkanlah sebuah hash function. Ada berbagai banyak hash function, tetapi yang paling banyak digunakan adalah method division. Setelah kita mendapatkan key dari hasil hash function tersebut. maka kita bisa menggunakan key tersebut untuk memasukkannya ke dalam index key dalam array hashtable.

Disini kita bisa lihat ada keys yang berupa string. Kemudian key tersebut kita akan masukkan ke dalam hash function. Setelah itu, akan dikeluarkanlah nomor yang berupa index dari hashtable. Keys tersebut akan kita masukkan ke dalam hashtable sesuai dengan index yang diproduksi oleh hash function.

Binary Search Tree

Binary search tree (BST) adalah suatu data struktur yang memanfaatkan binary tree sebagai strukturnya. Konsep binary search tree sangatlah simple, jika binary tree data tidak disortir, pada binary search tree data akan disortir.

Bisa kita lihat pada contoh diatas setiap tangan kiri suatu node akan lebih kecil dari node. 

1. Tangan kiri dari node 8 adalah node 3, dimana 8 lebih kecil daripada 3.  

2. Tangan kiri 3 adalah 1, dimana 1 lebih kecil daripada 3.

3. Dan seterusnya...

Kita juga dapat lihat bawah setiap tangan kanan dari sebuah node adalah bilangan yang lebih besar daripada node.

1. Tangan kanan dari node 8 adalah 10, dimana 10 lebih besar daripada 8.

2. Tangan kanan 10 adalah 14, dimana 14 lebih besar daripada 10.

3. Dan seterusnya...

Nah, itulah definisi dari Binary search tree, pada umumnya tangan kiri akan lebih kecil daripada node, tangan kanan lebih besar daripasa node, tetapi hal itu bisa dibalik sesuai dengan sang programmer yang memprogramnya dan juga kebutuhannya.

Lalu, Apa perbedaan dari Binary search tree daripada binary tree biasa?

1. Data yang disortir akan terlihat rapi.

2. Pencarian data akan lebih mudah, dengan bisa menggunakan binary search.

3. Pembuatan binary search tree lebih rumit daripada binary tree.

4. Data akan terstruktur.

Berikut adalah link tugas coding supermarket saya: Click Here