Keuntungan :
1) Linked list menggunakan ukarn yang dinamis.
2) Linked list mudah untuk dihapus maupun ditambahkan.
3) Penggunaan memor inke list dapat disesaikan secara dinamis.
Kekurangan :
1)Linked List menggunakan memory lebih besar.
2)Proses mengakses lebih panjang karena tidak bisa langsung mengakses data dengan indeks, hars diakes dari linked list yang paling besar.
Untuk menggunakan linked list diperlukan memory allocation.
Linked List memunyai dua tipe, yaitu:
- Single link list
Single linked list terdiri dari:
1) current data
2) Pointer ke next node.
Dalam bahasa C, node dapat diiplementasikan menggunakan structure. contoh :
- Double link list
Double Linked List mempunyai pointer tambahan,yaitu, prev yang bersatu dengan pointer next dan data yang ada di dalam single linked list.
Dalam linked list, kita mengenal 2 istilah yaitu, push dan pop. push merupakan fungsi untuk memasukan data kedalam linked list. sedangkan pop adalah fungsi untuk menghapus data dalam suatu linked list.
Untuk membuat suatu linked list, kita membutuhkan 3 pointer yaitu :
1. Head : awal dari suatu linked list,
2. Current : data yang sedang/akan kita olah,
3. Tail : akhir dar suatu linked list.
Push
Push merupakan suatu fungsi untuk menambahkan pumya sata pada linked list yang kita punya. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). Saat kita menstruct data, kita harus membuat pointer di dalam struct, yaitu 1 pointer untuk single linked list, dan 2 pointer untuk double linked list.
Pop
Pop merupakan fungsi untuk menghapus data dalam suatu linked list. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). setelah kita melakukan menghapus, kita harus free untuk menghapus malloc yang telah kita lakukan, karena jika kita tidak free data akan terus mengambil tempat tanpa bisa di akses.
contoh coding:
Hashing
Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi.Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai key yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Hash Function
Ada banyak cara untuk hash sebuah string menjadi sebuah key. berikut cara penting untuk membuat sebuah hash function:
Mid Square
Kuadratkan string/identifier, lalu kita mengambil angka tengah dari kuadrat identifier sebagai hash key.
Function : h(k) = s
k = key, s = hash key yang didapatkan dari mengambil tengah dari k^2
Division
String/identifier dibagi dengan menggunakan modulus.
Function : h(z) = z mod M
z = key, M = angka yang digunakan untuk membagi key (biasanya menggunakan angka prima)
Folding
Langkah :
- bagi key value menjadi beberapa bagian
- jumlahkan bagian individal(usually last carry is ignored)
Digit Extraction
Beberapa bagian digit dari angka dijadikan sebagai hash address.
Contoh :
x=14568. Jika kita Mengambil angka ke 1,3, dan 5, kita akan mendapatkan hashcode : 158.
Rotating hash
Gunakan hash mehod apa saja, lalu kita balik(angka perama menjad angka terakhir, dst.
Hashing table didalam block chain digunakan untuk cryptocurrencies, yaitu sebuah teknologi membuat mata uang digital. Teknologi ini menggunakan kriptografi untuk keamanan yang membuatnya tidak dapat dipalsukan. transaksi dengan panjang bervariasi dijalankan melalui algoritma hashing yang diberikan, dan menghaslkan output dengan panjang yang tetap terlepas dari panjang transaksi input. Output adalah sebuah hash.
Tree dan binary tree
Tree adalah non linear data sructure yang mempunyai tingkatan dari data objek. seperti struktur organisasi, dll. data diubungkan dengan pointer.
Tree concept :
Root : Node di paling atas
Edge: Garis yang menghubungkan parent dengan child
Leaf: node yang tidak mempunyai anak
Siblings: node yang mempnyai parent yang sama
Degree: total subtree dari sebuah node
Height/depth: maksimum degree dari sebuah tree
jika ada garis yang menghubungkan p kepada q, p disebut ancestor dari q dan q adalah descendant dari p.
Binary Tree adalah Tree yang hanya memiliki maksimal 2 anak.
Binary search tree merupakan binary tree yang sudah tersortir. Kebanyakan Binary Search Tree menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.
Binary Search Tree mempuyai beberapa operasi dasar yaitu :
•>Find : Fungsi untuk mencari angka di dalam sebuah Binary Search Tree. Dilakukan dengan fungsi rekrusif dari root sampai meneukan angka yang kita inginkan. Konsepnya adalah dimulai dari root, jika root merupakan angka yang kita cari, return root. Jika angka yang kita cari lebih kecildaripada root, rekrusive fungsi ke subtree sebelah kiri. Jika angka yang kita cari lebih besar dari root, rekrusive fungsi ke subtree sebelah kanan.
•> Remove : Fungsi untuk menghapus suatu node dari sebuah Binary Search Tree. Dilakukan dengan mencari data yang akan dihapus dalam tree. Jika sudah dihapus maka, yang akan menggantikan data yang dihapus adalah:
1. Jika data yang dihapus adalah parent dengan single children maka, yang akan menggantikannya adalah childrennya.
2. Jika data yang dihapus adalah leaf maka, langsung dihapus saja.
3. Jika data yang dihapus adalah parent dengan 2 children maka, yang akan menggantikannya adalah subtree sebelah kanan nya yang paling kiri atau subtree sebelah kiri yang paling kanan tergantung dengan pembuat treenya.
Tipe Binary tree:
Perfect Binary Tree : Binary tree yang semua level mempunyai depth yang sama.
Complete Binary Tree : binary tree yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.
Skewed Binary Tree : binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.
Balanced Binary tree : bianry tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.
Binary tree dapat diterapkan menggunaakan array maupun linked list
Array :
Index on array represents node number
Index 0 is Root node
Index Left Child is 2p + 1, where p is parent index
Index Right Child is 2p + 2
Index Parent is (p-1)/2
Linked List :
Expression Tree Concept
Menggunakan konsep matematika dalam penggunaan nya. Antara lain dalam penggunaan prefix, postfix dan infix.
Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)
Threaded binary tree adalah binary tree yang memiliki cara menunjuk pointer NULL yang berbeda dengan binary tree.
Binary tree tanpa threading:
Binary tree dengan menggunakan threading:
Terlihat perbedaan pointer NULL yang ada.
Ada 2 tipe threading:
1. Yang menggunakan threading 1 arah yang berarti masing masing pointer hanya menunjuk satu arah
2. Yang menggunakan threading 2 arah yang berarti masing masing pointer bisa menunjuk arah
Terlihat perbedaan pointer NULL yang ada.
Ada 2 tipe threading:
1. Yang menggunakan threading 1 arah yang berarti masing masing pointer hanya menunjuk satu arah
2. Yang menggunakan threading 2 arah yang berarti masing masing pointer bisa menunjuk arah
