Review

Linked list adalah struktur data yang terdiri dari urutan rekaman data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan.

Linked list memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.

Perbedaan saat penggunaan Array dengan Linked List.

Array:

• Koleksi linear elemen data.
• Simpan nilai di lokasi memori berurutan.
• Dapat acak dalam mengakses data.

Linked List:

• Kumpulan node linear.
• Tidak menyimpan simpulnya di lokasi memori berurutan.
• Hanya dapat diakses secara berurutan.

Macam-macam Linked List: 

1. Circular Single Linked List

    Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

2. Doubly Linked List

   Doubly Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.

3. Circular Doubly Linked List
    Circular Doubly Linked List mirip dengan Single Linked List, namun jumlah pointer pada setiap node adalah 2. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya.

4. Multiple Linked List
    Multiple linked list merupakan daftar berantai yang memiliki link atau pointer lebih dari satu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doublylinked list.

Stack  adalah kumpulan elemen-elemen data yang kemudian disimpan. Hanya boleh diakses pada satu lokasi saja yaitu posisi atas tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Operasi-operasi pada Stack :
1. Push : digunakan untuk menambah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack yang ada.
4. Create Stack : membuat Tumpukan baru, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Queue adalah suatu struktur data linear. yang memiliki konsep hampir menyerupai dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan dan penambahan berlaku pada bagian belakang. Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.


Hashing and Hash Table

Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli.
Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.
Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

Hash Table
Tabel hash adalah tabel (larik) tempat kami menyimpan string asli. Indeks tabel adalah kunci hash sementara nilainya adalah string asli.
Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.
Misalnya, ada 267 (8.031.810.176) string dengan panjang 7 karakter hanya terdiri dari huruf kecil saja.

Hash Function
Ada banyak cara untuk memotong string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun fungsi hash.

• Mid-square, Metode kuadrat menghasilkan kode hash yang masuk akal jika tidak ada banyak angka nol di depan atau di belakang. Ini adalah varian dari hashing multiplikasi, tetapi tidak sebagus kunci arbitrer bukan pengganda yang baik.
• Division (paling umum), Teknik standar adalah dengan menggunakan fungsi modulo pada kunci, dengan memilih pembagi M yang merupakan bilangan prima yang dekat dengan ukuran tabel, jadi h (K) = K  mod M.
• Folding, Kode hash lipat dihasilkan dengan membagi input menjadi n bagian m bit, di mana 2 ^ m adalah ukuran tabel, dan menggunakan operasi bitwise yang mempertahankan paritas seperti ADD atau XOR, untuk menggabungkan bagian.
• Digit Extraction, digit yang dipilih diekstraksi dari kunci dan digunakan sebagai alamat.
• Rotating Hash, Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Binary Search Tree

Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah. BST juga dikenal berbagai versi pohon biner Untuk simpul x dalam BST T,

• Subtree kiri (left) x berisi elemen yang lebih kecil dari yang disimpan dalam x 
• Subtree kanan (right) x berisi semua elemen yang lebih besar dari yang disimpan dalam x

Operasi: Penghapusan

Ada 3 kasus yang harus dipertimbangkan:

• Jika kunci ada di leaf, hapus saja node tersebut.

• Jika kuncinya ada di node yang memiliki dua child, temukan child paling kanan dari subtree kirinya (node P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih child  paling kiri dari sub pohon kanannya).

• Jika kunci ada di node yang memiliki satu child, hapus node itu dan sambungkan child-nya ke parent-nya.