Heap and Tries

Linked List

Linked List (senarai berantai) adalah struktur data yang terdiri dari urutan record data. Dimana setiap recordnya memiliki field untuk menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

·        Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

·        Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Macam - Macam Linked List

     1. Singly Linked List :

     Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang             berisi data. Pembuatan Single Linked List dapat menggunakan 2 metode:

·        LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

·        FIFO (First In First Out), aplikasinya : Queue (Antrean)

2. Double Linked List adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. 

3.  Circular double linked list next dan prev nya menunjuk kedirinya sendiri secara circular (membentuk pola bundar). Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk kedirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya. Semua sel yang terdapat pada list disambungkan dengan pointer, sedangkan setiap sel. memiliki tiga komponen yaitu value, pointer ke sel berikutnya.

4. Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. contoh :

Operasi yang Ada Pada Linked List

1. Insert : Fungsi untuk menambah sebuah simpul baru pada linked list                                                               

2. IsEmpty : Fungsi untuk menentukan apakah linked list isi atau tidak

3. FindFirst : Fungsi untuk mencari elemen pertama dari linked list

4. Find Next : Fungsi untuk mencari elemen sesudah elemen yang ditunjuk oleh now 

5. Retrive : Fungsi untuk mengambil elemen yang ditunjuk oleh now dengan isi dari sesuatu

6. Update : Fungsi untuk mengubah elemen yang ditunjuk now dengan diisi sesuatu

7. Delete Now : Fungsi untuk menghapus elemen yang ditunjuk now

8. Delete Head : Fungsi untuk menghapus elemen yang ditunjuk head

9. Clear : Fungsi untuk menghapus linked list

Stack and Queue

1. Stack

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Operasi pada Stack :

• Operasi push, berfungsi memasukkan sebuah nilai atau data ke dalam stack. Sebelum itu, nilai atau data dimasukkan ke dalamstack, dengan cara menaikkan posisi top satu level ke atas. ilustrasi kerja pada operasi push:

• Operasi pop, berfungsi umengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah. Berikut ilustrasi kerja pada operasi pop: 

• Operasi clear : digunakan untuk mengosongkan Stack.
• Operasi create stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
• Operasi makeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
• Operasi IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
• Operasi Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

2. Queue 

Queue merupakan suatu struktur data linear. Perbedaannya dengan stack adalah operasi penambahan dan penghapusan pada ujung berbeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Tumpukan pada queue disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. 

Operasi pada Queue :

• Operasi enqueue, berfungsi memasukkan sebuah data atau nilai ke dalam queue. Pada proses enqueue, tail -lah yang berjalan seiring masuknya data baru ke dalam antrian, sedangkan head akan tetap pada posisi ke-1.

• Operasi dequeue, digunakan untuk menghapuskan sebuah data atau nilai yang paling awal masuk ke dalam queue. Operasi ini menaikkan nilai head satu level.

Operasi Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong

• Operasi Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

Hashing Table

Pengertian Hash Tabel

Hash Table merupakan struktur data yang terdiri atas sebuah tabel dan fungsi. Bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Keunggulan dari struktur hash table ini :

• waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
• Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record tidak sama tetapi dapat dibangkitkan dengan angka hash yang sama).      

Operasi Pada Hash Tabel

•            insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
•       find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
•     remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
•       getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Pengaplikasian

   Berikut contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m)

Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).

Dengan hash function tersebut didapat :

Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..

Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.

Misal : mencari data 25 → h = 25 (mod 13) = 12

Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.

Binary Tree

 Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

Lalu, ada lagi yang namanya Binary Tree. Apa bedanya? Sebenarnya sama sama konsepnya dengan Tree. Hanya saja, kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan). Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja. Untuk lebih jelasnya, lihat gambar di bawah ini.

Lanjut lagi, sekarang kita akan memasuki pembelajaran intinya yaitu Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Pseucode dalam C

Hash In Blokchain

Struktur data adalah cara khusus menyimpan data. Ada dua properti struktur data yang sangat penting jika Anda ingin memahami cara kerja blockchain. Mereka:

1.     Pointer.

2.     Daftar Tertaut.

Pointer

Pointer adalah variabel dalam pemrograman yang menyimpan alamat variabel lain. Biasanya variabel normal dalam bahasa pemrograman menyimpan data.

Misalnya. int a = 10, berarti ada variabel “a” yang menyimpan nilai integer. Dalam hal ini, ia menyimpan nilai integer yaitu 10. Ini adalah variabel normal.

Pointer, bagaimanapun, bukannya menyimpan nilai akan menyimpan alamat variabel lain. Itulah sebabnya mereka disebut pointer, karena mereka secara harfiah menunjuk ke lokasi variabel lain.

Daftar Tertaut

Daftar tertaut adalah salah satu item paling penting dalam struktur data. Seperti inilah daftar tertaut:

Ini adalah urutan blok, masing-masing berisi data yang ditautkan ke blok berikutnya melalui pointer. Variabel pointer, dalam hal ini, berisi alamat node berikutnya di dalamnya dan karenanya koneksi dibuat. Node terakhir, seperti yang Anda lihat, memiliki pointer nol yang berarti tidak memiliki nilai.

Satu hal penting yang perlu diperhatikan di sini, pointer di dalam setiap blok berisi alamat dari blok berikutnya. Itulah bagaimana pointing dicapai. Blok pertama disebut “blok genesis” dan penunjuknya terletak pada sistem itu sendiri. Ini terlihat seperti ini:

struktur blockchain:

Blockchain adalah daftar tertaut yang berisi data dan pointer hash yang menunjuk ke blok sebelumnya, sehingga menciptakan rantai. Apa itu hash pointer? Sebuah pointer hash mirip dengan sebuah pointer, tetapi bukan hanya berisi alamat dari blok sebelumnya tetapi juga berisi hash dari data di dalam blok sebelumnya . Tweak kecil ini adalah apa yang membuat blockchains sangat luar biasa andal dan trailblazing.

Bayangkan ini sebentar, seorang hacker menyerang blok 3 dan mencoba mengubah data. Karena sifat fungsi hash, sedikit perubahan dalam data akan mengubah hash secara drastis. Ini berarti bahwa setiap perubahan kecil yang dibuat di blok 3, akan mengubah hash yang disimpan di blok 2, sekarang pada gilirannya akan mengubah data dan hash blok 2 yang akan menghasilkan perubahan di blok 1 dan seterusnya dan seterusnya . Ini sepenuhnya akan mengubah rantai, yang tidak mungkin. Inilah tepatnya bagaimana blockchain mencapai keabadian.

Header blok berisi:

§  Versi: Nomor versi blokir.

§  Waktu: cap waktu saat ini.

§  Target sulit saat ini. (Lebih lanjut tentang ini nanti).

§  Hash dari blok sebelumnya.

§  Nonce (lebih lanjut tentang ini nanti).

§  Hash dari Merkle Root.

Binary Search Tree

Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. 

Ada tiga cara kunjungan dalam tree:

1. Pre-order

a. Print data pada root

b. Secara rekursif mencetak seluruh data pada subpohon kiri

c. Secara rekursif mencetak seluruh data pada subpohon kanan

2. In-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Print data pada root

c. Secara rekursif mencetak seluruh data pada subpohon kanan

3. Post-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Print data pada root