SUMMARY

LINKED LIST

1. Circular single Linked list

Single linked list adalah satu variabel pointer untuk menyimpan data dengan metode linked list. Data disimpan ke dalam node, setiap node memiliki pointer untuk menunjuk ke node berikutnya. Nah, kalau Circular single linked list itu sama seperti single linked list tetapi setiap node awalnya menyambung dengan node akhir seperti lingkaran, selalu menyambung.

Ini adalah ilustrasi perbedaan single linked list (atas) dan circular single linked list(bawah)

2. Doubly linked list

Adalah Linked list yang mempunya dua pointer yaitu pointer prev dan next. Pointer prev digunakan untuk menunjukkan ke data sebelumnya dan sebaliknya kalau pointer next menunjukkan ke data selanjutnya

Contoh code untuk double linked list :

Insert pertama (Dari Depan)

Insert dari depan itu adalah penyisipan yang ada di awal, dan pointer head akan pindah ke elemen / data baru, contohnya:

Insert Terakhir (Dari Belakang)

Insert dari belakang itu adalah penyisipan yang ada di akhir, dan pointer tail akan pindah ke elemen / data baru, contohnya:

Delete satu node

Menghapus node apabila hanya ada satu node saja dapat menguunakan:

Delete Depan

Delete atau menghapus yang ada di awal list, pointer yang ada di head akan pindah ke data / elemen selanjutnya, contohnya :

Delete Akhir

Delete atau menghapus yang ada di akhir list, pointer yang ada di tail akan pindah ke data / elemen sebelumnya, contohnya :

Print

Untuk meperlihatkan atau print link listnya dapat dicontohkan sebagai berikut:

3. Circular Doubly Linked List

Doubly linked list yang mempunyai 3 field pointer, maksudnya seperti biasa doubly mempunyai pointer prev dan next tetapi kalau circular pointer prev dan nextnya selalu menunjuk ke dirinya sendiri sehingga membentuk circular atau selalu saling menyambung. Agar lebih mudah dimengerti dapat melihat Ilustrasi dibawah ini:

Pada pertemuan kedua ini kami dijelaskan tentang linked list dan cara insert, dan juga menghapusnya serta dicontohkan untuk kodenya.

Biasanya di dalam linked list dimulai dengan membuat struct terlebih dahulu seperti berikut: 

1.      Insert

a.     Insert dari depan (pushDepan)

Artinya data yang palling baru yang dimasukkan ada di depan data yang lain

Contoh kodenya adalah seperti berikut:

Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushDepan satu data ‘10’ maka hasilnya menjadi 10, 7, 8, 9.

b.     Insert dari belakang (pushBelakang)

Seperti pushDepan ini adalah kebalikannya, artinya data yang paling baru yang dimasukkan ada di belakang data yang lain.

Contoh kodenya adalah seperti berikut:

Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushBelakang satu data ’10’ maka hasilnya menjadi  7, 8, 9, 10.

c.     Insert dari tengah (pushTengah)

Seperti pushDepan dan pushBelakang, pushTengah yaitu data yang paling baru yang dimasukkan ada di tengah dari data yang lain.

Contoh kodenya adalah sebagai berikut :

Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 10, 11 dan anda ingin menginput dengan pushTengah satu data ‘9’ maka hasilnya menjadi  7, 8, 9, 10, 11.

2.     Delete

a.     Delete dari depan (popDepan)

Artinya data yang dihapus adalah data yang paling depan.

Contoh kodenya adalah seperti berikut:

Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popDepan maka hasilnya menjadi  7, 8, 9.

b.     Delete dari belakang (popBelakang)

Ini merupakan kebalikan dari popdepan, artinya data yang paling belakang adalah data yang dihapus.

Contoh kodenya adalah seperti berikut:

 

Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popBelakang maka hasilnya menjadi  10, 7, 8.

-HASHING AND HASH TABLE, TREES AND BINARY TREE-

Hashing adalah sebuah teknik yang dibuat dengan bertujuan untuk membuat nilai kunci unik agar menjadi hasil yang lebih pendek dan kecil. Hashing dibuat menjadi pendek dan kecil agar mudah dicari dan juga dilokasikan.

Hash Table adalah Tabel yang dibuat dan diisi oleh kunci hash ( index di hash table) dan juga string aslinya (value di hash table). Hash table memiliki beberapa kelebihan salah satunya adalah agar lebih cepat untuk dicari dan lebih mudah untuk dilokasikan. Hash table juga juga dapat memiliki angka/key hash yang sama tetapi terkadang angka hash yang sama bisa juga menjadi menjadi tubrukan. Biasanya ini diatasi dengan membuat kebijakan untuk hash nya.

Contoh:

dibawah ini adalah list dari nama mahasiswa yang ada di kelas 

Anton, Bella, Deni, Galih, Hasan.

dalam hash table yang huruf depannya ‘A’ akan mempunyai index 0, ‘B’  mempunyai index 1, ‘C’ mempunyai index 2, ‘D’ mempunyai index 3 dan seterusnya.

Maka tabel Hashnya akan menjadi  seperti ini :

 

Function Hash : Banyak sekali cara untuk Hashing tetapi cara yang paling pentingnya ada 5 yaitu :

1. Mid-square

Mid square adalah metode hashing dengan mengkuadratkan nilai atau valuenya. Apabila itu string akan dikonversikan ke angka. Sesudah di kuadratkan akan di ambil nilai tengah dari hasil pangkatannya.

Contoh :

Nilai = 1234

Nilai 1234 dikuadratkan menjadi 1522756

Nilai tengah dari hasil kuadrat tersebut adalah 227. Inilah hasil dari Mid-Square Hashing.

2. Division

Division adalah metode hashing yang paling mudah dan  juga metode yang paling terkenal. Caranya adalah dengan me-modulo.

Contoh :

Apabila dibuat tabel yang berisikan 10 dan ada 6 data yaitu 75, 16, 23, 62, 37, 21

Maka dengan division akan menjadi

75 mod 10 =  5 + 1 = 6. Maka data 75 akan dilokasikan ke 6

16 mod 10 =  6 + 1 = 7. Maka data 16 akan dilokasikan ke 7

23 mod 10 =  3 + 1 = 4. Maka data 23 akan dilokasikan ke 4

62 mod 10 =  2 + 1 = 3. Maka data 62 akan dilokasikan ke 3

37 mod 10 =  7 + 1 = 6. Maka data 37 akan dilokasikan ke 8

21 mod 10 =  1 + 1 = 6. Maka data 21 akan dilokasikan ke 2

3. Folding

Folding adalah metode hashing yaitu apabila kita mempunyai data, data akan di bagi 2 dan data yang kedua akan dibalik dan digabungkan dengan data yang pertama.

Contoh :

Ada data Nim mahasiswa yaitu: 235482, 415381, 654321

Maka:

235+284 = 519 maka data 235482 di lokasikan di 519

415+183 = 598 maka data 415381 di lokasikan di 598

654+123 = 777 maka data 654321 di lokasikan di 777

4. Digit Extraction

Digit Extraction adalah metode hashing yang men-ekstrak atau mengambil angka secara terpilih dari data.

Contoh :

Ada data Nim mahasiswa yaitu: 235482, 415381, 654321 dan yang diambil itu angka ke-1, ke-3, dan ke-6 maka:

235482 -> 252 maka data 235482 di lokasikan di 252

415381 -> 451 maka data 415381 di lokasikan di 451

654321 -> 641 maka data 654321 di lokasikan di 641

5. Rotating Hash

Rotating hash adalah metode hashing yang dapat menggunakan metode hashing lainnya sperti Digit Extraction atau Division dan memutarnya.

Contoh:

Apabila Hash yang sudah di division hasilnya 245638 maka hasil dari rotationnya adalah 836542

Collision

Collision adalah apabila nilai atau key-nya sama dan bertubrukan, cara menanggulanginya dapat dengan menggunakan Linear Probing atau Chaining

Linear Probing adalah apabila ada key hash yang sama maka akan ditempatkan di tempat index kosong yang terdekat

Chaining adalah apabila ada key hash yang sama maka akan ditempatkan  disampingnya sehingga membentuk rantai atau Linked list

Trees & Binary Tree

Tree adalah kumpulan dari beberapa node yang dihubungkan oleh pointer. Apabila diibaratkan, node yang paling atas dan mempunyai cabang disebut Parent(root), dan node yang menyambung dengan parent disebut children. Garis yang mengubungkan antara parent dengan childrennya disebut edge. Node yang tidang menyambung lagi atau tidak mempunyai children disebut leaf. Node yang menyambung ke parent yang sama disebut sibling. Dibuat seperti pohon keluarga.

Binary tree adalah tree yang dipastikan hanya memiliki children paling banyak hanya 2. Biasanya anaknya dibedakan dengan right child dan left child. Node yang tidak memepunyai anak disebut leaf. Binary tree paling banyak sampai level 3 atau tingginya 3 tingkatan.

Binary tree juga memiliki beberapa tipe

1. Perfect binary tree

Yaitu binary tree yang mempunyai 2 children yang bercabang dan rata antara yang kanan dan yang kiri.

Contoh:

2. Complete Binary tree

Yaitu binary tree yang mempunyai 2 children tetapi salah satu dari cabang terakhirnya tidak ada dan sisanya terisi semua.

Contoh :

3.Skewed Binary Tree

Yaitu binary tree yang hanya mempunyai paling banyak satu anak.

Contoh:

4. Balenced Binary Tree

Yaitu binary tree yang leaf kanan tidak lebih jauh dari root dengan leaf kirinya sehingga balenced.

Contoh :

Expression Tree

Adalah Binary tree yang mempunyai cabang adalah operatornya dan yang tidak mepunyai cabang atau (leaf) adalah operan(angkanya).

Expression tree mempunyai Prefix, postfix dan infix.

Prefix adalah expression yang operator nya ada terlebih dahulu sebelum operannya.

Contoh : *+WX-YZ

Postfix adalah expression yang operatornya ada di belakang dari operannya.

Contoh : WX+YZ-*

Infix adalah expression yang operatornya beradi di tengah operannya.

Contoh : (W+X)*(Y-Z)

Threaded Binary Tree adalah binary tree tetapi mempunayi pointer yang NULL di kanan dan di kirinya. Ini mempunyai beberapa kelebihan seperti dapat mengunnakan linear traversal dan dapat mengurangi penggunaan stacks sehingga tidak memakan memory yang banyak. Tetapi Threaded binary tree juga memiliki kekurangan seperti lebih sulit untuk membuat binary treenya dan lebih sering mendapat error apabila tidak ada children-nya atau nodenya menunjuk kepada ancestornya.

Contoh Threaded Binary Tree:

Hash Table dalam Block chain dan apakah digunakan dalam blockchain sekarang : Hash table dapat digunakan dalam blockchain karena keduanya (hash table & blockchain) menggunakan data structure yang terdistribusi dan dapat digunakan di dalam blockchain. Tetapi blockchain dan hash table memiliki tujuan yang berbeda, blockchain bertujuan untuk menyediakan data structure yang tahan dengan kerusakan dan untuk menyimpan data yang makin banyak tanpa adanya gangguan atau kerusakan, sedangkan Hash table tujuan utamanya adalah memberikan data structure yang lebih efisien dengan arti lebih cepat dalam mencari dan tidak memakan memory yang besar.

Linkled list dengan double pointer : apabila menggunakan double pointer maka kalau kita ingin merubah head / memperbaharui list, tidak perlu untuk mengembalikan head-nya lagi sedangkan kalau single pointer harus mengembalikan head-nya lagi

Contoh code dengan double pointer:

BST

Binary Search Tree atau biasanya disingkat menjadi BST itu adalah Struktur data Binary Tree yang mempunyai node dan yang berstruktur yaitu (Subtree kiri dan Subtree kanan harus binary tree):

-          Subtree sebelah kiri hanya terdiri dari node yang lebih kecil dari parents dan rootnya

-          Subtree sebelah kanan hanya terdiri dari node yang lebih besar dari parents dan rootnya

Binary Search Tree juga mempunyai kelebihan yaitu lebih cepat dama mencari, lebih cepat untuk sorting data dan juga lebih cepat dan lebih mudah untuk insert data dan delete data.

Berikut adalah contoh dari Binary search tree :

Didalam Binary Search Tree kita dapat melakukan Search, Insert dan juga delete:

Search:

Untuk search dalam Binary Search Tree, pertama-tama harus disamakan dengan root apabila nilainya sama dengan root maka return root-nya. Apabila nilai nya lebih besar daripada root maka cari di sebelah kanan dari Subtreenya, apabila lebih kecil daripada root-nya maka cari disebelah kiri dari rootnya.

Contoh codenya adalah sebagai berikut:

Insert:

Data baru yang di-insert selalu berada di leaf dalam binary tree. Sama seperti search, kita cari apabila datanya lebih kecil daripada root makacari secara recursive ke sebelah kiri dan apabila lebih besar maka kesebalah kanan. Setelah di search dan apabila sudah ketemu tempat yang memenuhi persyaratan maka data barunya menjadi leaf child dari nodenya.

Contoh codenya adalah sebagai berikut:

Delete:

Data yang ingin di-delete dapat berupa leaf, parent yang mempunyai satu child atau parent yang mempunyai dua child. Apabila yang ingin dihapus hanya leaf maka tinggal hapus saja, apabila ynag dihapus parent yang mempunyai satu child maka tinggal copy child-nya ke node dan hapus parentnya, dan apabila yang ingin dihapus parent yang mempunyai dua anak maka cari penerus dari parent tersebut setelah itu maka tinggal hapus dan replace dengan penerus dari parent yang sudah ditemukan

Contoh codenya adalah sebagai berikut: