Review Summary

Linked list (Senarai berantai) adalah sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam senarai dilakukan secara lebih efektif.

Linked list terdiri dari 3 jenis: Singly, Doubly, dan Circular.

> Singly Linked List
Linked List yang hanya memiliki rujukan pada node berikutnya, node terakhir diberi rujukan NULL.



> Doubly Linked List
Berbeda dengan senarai tunggal, pada senarai ganda, struktur data atas setiap node memiliki rujukan pada node sebelum dan berikutnya.
 

> Circular Linked List
Berbeda dengan 2 jenis Linked List sebelumnya, Circular sama sekali tidak memiliki rujukan NULL.




Berikut adalah source code yang berisi Single Linked List (dalam bahasa C)

struct data{
 int value;
 struct data *next;
}*head=NULL, *curr, *tail=NULL;

Dalam Linked List, kita dapat melakukan instruksi push dan pop.

Push yang artinya kita memasukkan data baru ke dalam Linked List sedangkan Pop merupakan kebalikannya, yaitu menghapus data yang ada di dalam Linked List.

Berikut adalah algoritma untuk metode push dalam Single Linked List

void push (int x){
 curr = (struct data*)malloc(sizeof(struct data);
 curr->value = x;
 if(head == NULL){
  head = tail = curr;
 } else {
  tail->next = curr;
  tail = curr;
 }
 curr->next = NULL;
}

Berikut adalah algoritma untuk metode pop dalam Single Linked List

void pop () {
 curr = head;
 if(head == tail){
  head = tail = NULL;
  free(head);
 } else {
  while(curr->next != NULL){
   curr = curr->next;
  }
  free(tail);
  tail = curr;
  tail->next = NULL;
 }
}  

• Hashing & Hash Table

Hashing merupakan teknik yang digunakan untuk mengubah sebuah string menjadi angka (kunci). Kumpulan karakter dalam sebuah string diubah dalam bentuk nilai/kunci yang lebih pendek yang mempresentasikan string original. Benefit yang kita dapatkan dari menggunakan Hashing adalah kita dapat mengakses database yang kita miliki lebih cepat sehingga memungkinan untuk melakukan proses yang lain. Hash Table merupakan table (array) dimana kita menyimpan string original. Indeks Hash Table merupakan kunci sedangkan nilainya merupakan string original.

Misalkan kita memiliki Array of String (randomstuff) berisikan Mayahi, Ozone, Lu, Add, Djanu. Kita bisa membuat Hash Table dari mengubah huruf pertama setiap String menjadi sebuah angka dari range 0 hingga 25.

• Hash Function

Berikut adalah metode hashing yang dapat kita gunakan dalam mengubah string menjadi kunci:

1. Mid-Square
String/Identifier dikuadratkan kemudian mengambil beberapa angka hasil kuadrat (yang berada ditengah) untuk dijadikan sebagai hash key


2. Division
Membagi String/Identifier menggunakan operasi Modulus (% || mod). Angka yang digunakan biasany merupakan bilangan primer.

Contoh: "ABCD" akan disimpan pada lokasi 76
Perhitungannya adalah 64(1+2+3+4) mod 97


3. Folding 
Partisi String/Identifier menjadi beberapa bagian, kemudian menjumlahkan bagian tersebut membentuk sebuah hash key


4. Digit Extraction
Mengambil beberapa bagian dari String/Identifier dan menjadikanny sebagai hash key
Contoh: Budi mempunyai nilai x yaitu 472659485, maka kita bisa mengambil angka genap sebagai hash key yaitu 42648

5. Rotating Hash
Gunakan metode Hashing seperti Mid-Square atau Division, kemudian membalikkan hash key dari belakang ke depan.
Contoh: Jika hash key adalah 438573976 maka rotated hash key adalah 679375834

<> Collision
Collision merupakan tabrakan antar hash key, dimana terdapat lebih dari 1 data yang memiliki hash key yang sama.

Linear Probing Method
(very bad search complexity)

Solusi apabila terjadi Collision adalah Linear Probing dan Chaining.
1. Linear Probing = Mencari tempat kosong dan mengisi string di lokasi tersebut.
Misalkan kita mempunyai Array of String (morerandom) yang berisikan Zul, Lu, Add, Djanu, Chotto, Alyx, Dedede

Linked List (Chaining)

 2. Chaining = Membuat Linked List dan menyambungkan string di slot yang sama

•  Binary Tree 

Tree merupakan struktur data non-linear yang mempresentasikan hubungan antar data. Konsep Tree adalah kumpulan dari 1 node atau lebih.

- Node yang berada paling atas merupakan root
- Node yang tidak memiliki child merupakan leaf 
- Node yang memiliki parent yang sama merupakan sibling
- Jika ada garis yang menghubungkan X ke Y, maka X merupakan ancestor dari Y dan Y merupakan descendant dari X

Binary Tree merupakan Tree dimana setiap node memiliki paling banyak 2 child.
C merupakan parent dari F dan G. F dan G merupakan child dari C.



Binary Search Tree adalah sebuah pohon biner struktur data yang dimana:
- Semua simpul mempunyai nilai
- Sub pohon kiri mempunyai nilai yang lebih kecil daripada nilai simpul
- Sub pohon kanan mempunyai nilai yang lebih besar daripada nilai simpul

Operasi yang dapat dilakukan untuk suatu Binary Search Tree adalah Find, Insert, dan Remove.

1. Find
- Pencarian dimulai di akar, apabila nilai akar sama dengan nilai yang kita cari maka proses pencarian langsung stop.

- Jika nilai yang kita cari lebih kecil daripada nilai akar, lakukan pencarian secara rekursif ke bagian kiri sub pohon biner. Namun, jika nilai yang kita cari lebih besar daripada nilai akar, lakukan pencarian secara rekursif ke bagian kanan sub pohon biner.

2. Insert
- Dimulai dari akar
- Jika nilai yang kita input lebih besar daripada nilai akar, maka masuk ke sub pohon kanan. Namun, jika nilai yang kita input lebih kecil daripada nilai akar, maka masuk ke sub pohon kiri. Step ini diulangi hingga kita menemukan tempat kosong dimana kita menaruh nilai yang kita input disitu.

3. Deletion
Terdapat 3 kondisi yang harus diperhatikan:
- Jika nilai yang kita ingin hapus berada pada di daun, maka kita tinggal delete langsung.
- Jika nilai yang kita ingin hapus terdapat dalam simpul yang memiliki 1 anak, maka kita hapus nilai tersebut dan menggantikannya dengan cara menghubungkan anak ke orang tuanya
- Jika nilai yang kita ingin hapus terdapat dalam simpul yang memiliki 2 anak. cari anak yang paling kanan dari sub pohon kiri, menggantikan posisi anak dengan nilai yang kita inginkan kemudian menghapus nilai yang kita inginkan secara rekursif