SUMMARY DATA STRUCT

Linked List adalah salah satu bentuk struktur data yang memuat kumpulan data (node) yang menempati memori dinamis dan setiap node menunjuk kepada node lain melalui pointer sehingga saling berhubungan dengan berurutan.

Single Linked List merupakan linked list yang setiap nodenya mempunyai 2 field yaitu field yang berisi data dan field yang berisi pointer ke node berikutnya, sehingga pointer bergerak hanya ke satu arah saja. 

Double Linked List benar-benar mirip seperti Single Linked List, opeasi yang dilakukan pun mirip seperti Single Linked List. Perbedaannya hanya pada setiap nodenya memiliki tambahan 1 field yang berisi pointer ke node sebelumnya, sehingga pointer bergerak kedua arah.

Stack merupakan struktur data linear yang beroperasi seperti tumpukan, yaitu Last In First Out (LIFO) dimana elemen yang terakhir masuk (berada di paling atas) akan terlebih dahulu diproses lalu dikeluarkan dari stack. 

Queue merupakan struktur data linear yang beroperasi seperti antrian, yaitu First In First Out (FIFO) dimana elemen yang pertama masuk (berapa di paling depan) akan diterlebih dahulu diproses lalu dikeluarkan dari queue. 

Hashing merupakan teknik untuk menyimpan data-data dan secara unik mengidentifikasi data tertentu dari sekelompok data serupa. Teknik hashing memudahkan saat ingin melakukan pencarian data karena teknik ini memetakan Hash Key dalam tabel Hash Table menggunakan fungsi yang sudah ditentukan yaitu Hash Function. Konsep hashing digunakan dalam database untuk menyimpan banyak data dan setiap data dimasukkan ke setiap index dalam Hash Table. 

1. Mid - Square : Teknik ini menguadratkan key yang akan dimasukkan ke hash table, lalu mengambil angka tengah dari hasil yang sudah dikuadratkan sebagai hash key.

2. Division : Teknik ini mencari sisa bagi dari jumlah karakter yang ingin disimpan (ASCII).

3. Folding :  Teknik ini membagi key menjadi beberapa kelompok digit lalu dijumlahkan dan diambil beberapa digit dari hasil perhitungan untuk dijadikan hash key.

4. Digit Extraction : Teknik ini mengekstrak digit key yang ditentukan untuk mendapat hash key.

5. Rotating Hash : Teknik ini dilakukan dengan menggeser digit terakhir ke paling awal untuk menjadi hash key.

Collision berarti terdapat lebih dari satu data yang memiliki hash index yang sama, padahal seharusnya hanya satu index array yang hanya dapat menyimpan satu data.

Terdapat 2 cara untuk mengatasi Collision:
1. Linear Probing (Open Addresing)
Yaitu mencari index lain dengan bergeser 1 slot selanjutnya.

2. Chaining
Yaitu setiap index hash table membuat linked list.

Binary Tree merupakan salah satu struktur data dimana setiap simpul memiliki paling banyak 2 anak, yaitu anak kiri (left child node) dan anak kanan (right child node). Node yang tidak memiliki anak disebut leaf.

1. Perfect Binary Tree adalah binary tree yang setiap levelnya memiliki kedalaman yang sama.

2. Complete Binary Tree adalah binary tree yang setiap levelnya, kecuali yang terakhir, terisi semua dan semua node kiri terisi. Perfect binary tree disebut juga complete binary tree.

3. Skewed Binary Tree adalah binary tree yang setiap node memiliki paling banyak 1 child node.

4. Balanced Binary Tree adalah binary tree dimana perbedaan antara ketinggian subtree kiri dan subtree kanan pada setiap node tidak lebih dari satu.

Binary Search Tree (BST) merupakan salah satu struktur data yang digunakan untuk menyimpan data yang mempermudah proses pencarian data (searching), memasukkan data berurut (insertion) dan menghapus data (deletion). Binary Search Tree memiliki bentuk seperti Tree dan setiap data harus memiliki nilai yang berbeda dimana data disebut dengan Node. 

Node yang berada diposisi paling atas disebut dengan Root. Dalam BST, node akan terhubung dengan node lainnya sebanyak maksimalnya 2. Kedua node memiliki nama left subtree dan right subtree. Left subtree harus memiliki nilai lebih kecil dari nilai di node dan right subtree harus memiliki nilai lebih besar dari node. Node yang tidak memiliki left maupun right subtree disebut leaf.

Searching

Misalkan ingin mencari integer dengan value n.

Searching dimulai dari Root. Apabila n bernilai sama dengan Root, pencarian data akan berhenti karena data sudah ditemukan. Namun, apabila n bernilai lebih kecil dari Root, maka pencarian berlanjut ke left subtree dan sebaliknya apabila n lebih besar, maka pencarian berlanjut ke right subtree sampai data ditemukan.

Insertion

Misalkan ingin memasukkan integer dengan value n.

Jika Root masih kosong, maka data akan menjadi Root.

Jika n bernilai lebih kecil dari Root, n akan menjadi left subtree. Sebaliknya, jika n bernilai lebih besar dari Root, n akan menjadi right subtree. Dan seterusnya hingga menemukan tempat kosong dan data yang baru dimasukkan akan selalu menjadi leaf.

Deletion
Misalkan ingin menghapus integer dengan value n.
Jika n terdapat pada Root, maka dapat mengambil data pada leaf yang memiliki nilai paling besar dari left subtree atau pada leaf yang memiliki nilai paling kecil dari right subtree. Maka data tersebut akan menggantikan n dan leaf tempat sebelumnnya akan dihapus. Apabila n terdapat pada leaf, maka dapat langsung dihapus leafnya.