Summary

Linked List

Linked list merupakan struktur data yang terdiri dari urutan catatan data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan. Dari penegertian ini, dapat di simpulkan suatu linked list memiliki ciri ciri yaitu  berurutan (sequence), berisi referensi ke catatan berikutnya, memliki posisi yang acak.

Sebernarnya pengunaan linked list dengan array hampir sama tetapi linked list dan array memiliki beberapa perbedaaan yaitu :

1. Pada linked list ukuran data bisa bertambah sesuai kebutuhan sedangkan dengan  pada array ukuran data tidak dapat bertambah atau pas sesuai yang kita panggil di awal.
2. Pada linked list posisi data acak sedangkan pada array posisi data berurutan.

Linked list terdiri dari dua tipe yaitu :

1. Single linked list  
2. Double linked list

Stack & Queue

Stack :

1. Tumpukan .
2. Last In First Out (LIFO).
3. Bisa diimplementasikan dengan :
• Array (ada batasan , bisa looping di awal)
• Linked list (tidak ad batasan, tidak bisa looping diawal).

Operasi pada stack:

1. Push (x) : menambah data dari paling atas.
2. Pop ( ) : membuang data dari paling atas.
3. Top ( ) : mengambil data dari paling atas. 

Pada stack kita juga di perkenalkan dengan :

1. Prefix (* 4 10) :
•  Operator sebelum angka atau operand.
2. Infinix (4 * 10) : 
• Operator diantara operand atau angka.
3. Postfix (4 10 *) : 
• Operator di akhir. 

Ketiga hal ini merupakan bahasa komputer untuk proses perhitungan . Prefix, postfix dan infinix tidak menbutuhkan tanda kurung untuk setiap operasinya.

DFS (  Depth First Search)

DFS merupakam sebuah algoritma untuk melintasi atau mencari di pohon atau grafik. DFS dapat di implementasikan dengan fungsi rekursif atau prosedur berulang dari stack .Meskipun kedua hasilny agak berbeda karena proses jalannya tetapi keduanya menunjukkan hasil yang benar.

Queue :

1. Antrian.
2. Sistem First In First Out (FIFO).
3. Diimplementasikan dengan : 
•  Array 
• Linked list
  

Operasi pada stack:

1. Push (x) : menambah data dari paling belakang.
2. Pop ( ) : membuang data dari paling depan.
3. Top ( ) : mengambil data dari paling depan. 

Circular Queue :

Circular queue digunakan untuk menanggulangi kekurangan dari Queue dengan meminimalisir pergeseran pada Queue linear.

Deque : 

Deque adalah sebuah daftar yang dimana elemennya bisa dimasukkan atau dihapus di kedua ujungnya.Deque terdiri dari dua jenis yaitu :

1. Deque input terbatas : 
• Dalam deque ini penyisipan hanya dapat dilakukan di salah satu salah satu ujungnya, sementara penghapusan dapat dilakukan dari kedua ujungnya.
2. Deque output terbatas : 

• Dalam deque ini penghapusan  hanya dapat dilakukan di salah satu ujungnya sementara penyisipan dapat dilakukan pada kedua ujungnya.

Priority Queue :

Priority Queue adalah sebuah tipe data abstrak di mana masing-masing elemen diberi prioritas.

BFS (Breadth First Search) :

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Pada BFS menggunakan sistem dari Queue atau FIFO.

Hash Table & Binary Tree

Hash Table

Hashing

Sebelum mempelajari hash table kita harus mengetahui hashing terlebih dahulu. Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil data dalam waktu yang cepat. Dalam kasus ini teknik hashing mengubah sebuah karakter string menjadi ukuran yang lebih kecil atau sebuah kunci yang merepresentasikan string aslinya. hashing juga dapat diartikan sebagai pembagian kunci ke sebuah array yang disebut hash table dengan menggunakan fungsi yaitu hash function.

Hash table

hash table merupakan suatu tempat atau array dimana digunakan sebagai tempat penyipanan string aslinya. di hash table kita menyimpan data sebagai array yang dimana setaip datanya memiliki sebuah indeksnya masing - masing. Jadi karena hal ini kita dapat mengakses data dengan sangat cepat. 

Operasi dasar pada hash table

1. Insert 
• diberikan sebuah key dan nilai, insert nilai pada table.
2. Find 
• diberikan sebuah key , temukan nilai sebuah key.
3. Remove
•  diberikan sebuah key , temukan sebuah key, menghapus key tersebut.
4. GetIterator 
• mengembalikan iterator,yang mengecek nilai satu persatu.

Hash Fucntion

fungsi - fungsi pada hash yaitu :

1. Mid - Square
• memiliki dua step untuk melakukannya yaitu :
• kuadratkan nilai pada sebuah key.
• ekstrak  ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.
• jika nilai merupakan string ini akan di ubah menjadi angka.
• Contoh 1 :
• nilai = 3121
• hasil kuadrat = 3121 * 3121 = 9740641
• nilai tengah = 9740641
• Contoh 2 :
• nilai  = 2121
• hasil kuadrat = 2121 * 2121 = 4498641
• nilai tengah = 4498641
2. Division
• membagi string / identifier dengan menggunakan operator modulo.
• ini merupakan hash function paling simpel.
• menggunakan rumus H(K) = K mod N
• dimana : 
• K = nilai pada key.
• N = pembagi nilai , biasanya bilang prima, ukuran memori yang digunakan.
3. Folding
• membagi string / identifier menjadi beberapa bagian, lalu jumlahkan semuanya untuk mendapatkan hash key.
• step dalam folding :
• membagi nilai key menjadi beberapa bagian
• jumlahkan bagian yang sendiri.
• contoh : 
• nilai = 5678.
• parts = 56 dan 78.
• sum / add = 124.
• hash key = 24. 
4. Digit Extraction
• digit yang sudah di tentukan sebelumnya dianggap sebagai hash address.
5. Rotation Hash
• Gunakan hash function lain untuk mendapatkan hash address
• Lalu lakukan rotasi.
• Contoh :
• hash address = 30312.
• hasil rotasi = 21303.
6. Collision
• Keadaan dimana ketika ada beberapa nilai pada sebuah key sama.
• untuk mengatasi hal tersebut ada 2 cara yaitu :
• Linear Probing
• cari tempat yang kosong lalu tempat kan salah satu nilai yang sama ke tempat kosong itu.
• hal ini mempunyai banyak kelemahan jika banyak nilai yang sam pada sebuah key.
• Chaining
• kita menyimpan nilai yang sama pada sebuah key ke sebuah linked list.

Implementasi Hashing Table pada Blockchain

implementasi hash table pada blockchain yaitu pada kriptographi hash. kriptographi hash ini digunakan untuk menghubungkan blockchain.

 Binary Tree

Tree 

• Suatu data structure yang non linear yang menggambarkan hubungan hierarki antara data dengan objek.
• Beberapa hubungan tree dapat dilihat di struktur direktori atau hierarki sebuah organisasi.
• Node di tree dapat disimpan dimana saja dan terhubung dengan pointer.

Konsep tree

Bagian pada suatu tree :

1. Root 
• Node yang berada paling atas.
2. Edge 
• Garis yang menghubungkan parent dan child.
3. Leaf 
• Node yang tidak punya child.
4. Sibling
•  Node yang mempunya parent yang sama.
5. Degree
•  total Sub tree pada sebuah node.
6. Height / Depth
•  Maksimum degree pada sebuah node.
7. Ancestor dan Descendant

Binary Tree

• Hampir sama dengan tree hanya bedanya kalau binary tree setiap node paling banyak memiliki 2 child.

Tipe tipe binary tree :

1. Perfect Binary Tree 
• Binary tree yang setiap levelnya memiliki depth yang sama.
  
2. Complete Binary Tree 
• Binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
  
3. Skewed Binary Tree 
• Binary tree yang dimana setiap nodesnya memiliki paling banyak satu child.
4. Balance Binary Tree 
• Binary tree yang dimana yang setiap leafnya sama jauhnya dari root.
  

Property binary tree :

1. Nodes maksimum di level k adalah 2^k.
2. Nodes maksimum  di binary tree dengan height h adalah -1+2^h+1.
3. Height minimum dari sebuah binary tree dengan nodes n adalah 2^log(n).
4. Height maksimum dari sebuah binary tree dengan nodes n adalah n - 1.

Representasi dari tree mengunakan 2 cara yaitu :

1. Array
   
2. Linked list
   

Pengekspresian konsep tree dengan notasi aritmatika : 

1. prefix.
2. prefix tranversal.
• di prefix kalian harus print terlebih dahulu baru proses childnya.
3. infix.
4. infix tranversal.
5. postfix.
6. postfix traversal.
• di postfix kalian print setelah proses childnya.