Rangkuman Akhir Data Structure

Rangkuman Data Structure Final

Nama: Julian Andhika Diputra

NIM: 2301858023 

Kelas: CB01

Nama Dosen:  

- Ferdinand Ariandy Luwinda (D4522)
- Henry Chong (D4460)

Kelas: LB08

Nama Dosen:

- Diana (D4458)

AWAL SEMESTER - TENGAH SEMESTER

LINKED LIST

Linked List adalah data structure linear (Array) yang berisi data – data record yang berkoneksi dengan record di sequence selanjutnya. Linked list pun tidak menyimpan elemen dalam lokasi memori yang berdekatan. Linked list sendiri memiliki beberapa keuntungan dan kekurangan.

Keuntungan linked list adalah data struktur yang dinamik, pemasukan dan penghapusan node yang lebih mudah, dan juga data struktur lebih mudah diemplementasi menggunakan linked list. Kekurangannya adalah pengunaan memori lebih banyak, transferal antara node lebih susah, dan juga pengaksesan node harus dimulai dari node pertama, tidak boleh random.

Dalam pembelajaran kali ini, Linked list dibagi menjadi 3, yaitu Circular single linked list, Doubly Linked List, dan Circular Doubly Linked List.

1. Circular Single Linked List, adalah linked list yang paling umum, dimana node terakhir linked list ini memiliki pointer yang mempoint ke node pertama. Setiap node memiliki data dan pointer ke node selanjutnya seperti linked list lainnya. Dalam Circular Single Linked List dan Circular Double Linked List tidak memiliki storing NULL value didalam list tersebut.
2. Doubly Linked List, disebut juga sebagai two-way linked list adalah linked list dimana data structurenya memiliki dua link, satu yang memiliki referensi ke data selanjutnya dan satu lagi yang memiliki referensi ke data sebelumnya. Transfersal data bisa bergerak kedepan ataupun ke belakang. Ketika ingin menginsert sebuah node, kita harus memberikan value kedalam node tersebut, baru mengconnectnya ke node sebelumnya. 
3. Circular Doubly Linked List, mirip dengan Circular single linked list tetapi pointernya ada dua. Circular Doubly Linked List secara tidak langsung adalah gabungan antara Circular Single Linked List dan juga DOubly Linked List.
   

Ketika ingin mendelete jangan lupa tentang:

• Node yang ingin di delete adalah node salah satunya
•  Node yang ingin didelete adalah head
•  Node yang ingin didelete adalah tail
•  Node yang ingin dididelete bukanlah head ataupun tail

LINKED LIST(II)

Linked list sendiri terbagi menjadi 2, Single Linked List dan Double Linked List. Single Linked List menggunakan koneksi ke node dibelakangnya/didepannya saja sedangkan Double Linked List menggunakan koneksi ke kedua node yaitu kedepannya dan dibelakangnya.

Dalam pembuatan linked list sendiri terdapat banyak fungsi yang dapat dibuat, salah satu contohnya adalah Push dan Pop.

Dalam pembuatan coding Linked list kita harus memulai dengan meninisialisasi / membuat struct. Hal ini dilakukan untuk membuat structure data tersebut.

Push 

Push adalah  aksi/fungsi menambahkan sebuah node baru. Bisa dilakukan push kedepan node ataupun kebelakang node. Dalam Double Linked List, Push dapat dilakukan ketengah node.

1.    Push Depan, adalah aksi melakukan penambahan node didepan node pertama/head. Contoh codingnya dalam Single Linked List adalah sebagai berikut.

2.    Push Belakang, adalah aksi melakukan penambahan node di node paling belakang / tail. Contoh codingnya dalam Single Linked List adalah sebagai berikut.

3.    Push Node, adalah aksi yang bisa dilakukan di Double Linked List, yaitu menambahkan sebuah node ditengah - tengah node - node lain. Contoh codingnya dalam Double Linked List adalah sebagai berikut.

Pop

Pop yaitu aksi/fungsi menghilangkan sebuah node. Bisa dilakukan pop node didepan dan juga dalam Double Linked List dapat dilakukan pop node kebelakang ataupun node manapun yang diinginkan. Ada juga fungsi popall yaitu, adalah fungsi dimana kita menghapus semua node yang ada.

1.    Pop Depan, adalah aksi melakukan penghapusan node paling depan / head. Contoh codingnya dalam Single Linked List adalah sebagai berikut. 

2.    Pop Belakang, adalah aksi melakukan penghapusan node paling belakang / tail. Contoh codingnya dalam Double Linked List adalah sebagai berikut. 

3.    Pop Node, adalah aksi melakukan penghapusan sebuah node spesifik yang diminta. Contoh codingnya dalam Double Linked List adalah sebagai berikut. 

4.    Pop All, adalah aksi melakukan penghapusan semua node yang ada. Contoh codingnya dalam Double Linked List adalah sebagai berikut. 

Ketika sudah melakukan operasi yang diinginkan, bisa kita cetak melakukan contoh coding sebagai berikut.

HASHING DAN BINARY TREE

HASHING

Hashing adalah sebuah fungsi yang bisa digunakan dalam Data Structure, yang dapat digunakan untuk menggunakan sebuah fungsi khusus yaitu Hash Function. Hash function sendiri digunakan untuk memetakan sebuah nilai dengan key tertentu agar lebih mudah untuk diakses. Dalam Hashing, sebuah string character diubah menjadi string character yang lebih pendek atau sebuah key yang mewakili string awalnya. Ada juga Hash Table yaitu sebuah array dimana kita menyimpan string awalnya. Index table itu adalah keynya sedangkan valuenya adalah string awalnya.

Ada beberapa cara untuk meng-hash sebuah string menjadi key;

1. Mid-Square
2. Division
3. Folding
4. Digit Extraction
5. Rotating Hash

Mid-Square

Mid-Square adalah Teknik hashing dimana key hashing di-generate secara unik. Dalam Teknik ini, sebuah string diambil dan dikuadratkan. Lalu beberapa digit dari tengah diambil, yang nanti akan menjadi sebuah key baru. Teknik ini dapat membuat key dengan keacakan yang tinggi, jika digitnya besar. Jika key itu adalah sebuah string, akan diubah menjadi sebuah nomor.

Step:

1. Kuadratkan value sebuah key
2. Ambil bit tengah dari hasil yang didapatkan di step 1

Division

Division adalah Teknik hashing dimana sebuah string/identifier dibagi menggunakan operator modulus. Teknik ini merupakan Teknik hashing yang paling mudah.

Folding

Folding adalah Teknik hashing dimana sebuah string/identifier dipartisikan menjadi berbagai bagian, lalu kita menambahkan semua part tersebut untuk mendapatkan sebuah hash key.

Step:

1. Bagi value sebuah key menjadi berbagai bagian
2. Tambahkan setiap individual key ( carry terakhir diabaikan )

Digit Extraction

Digit Extraction adalah Teknik hashing dimana sebuah digit yang ditentukan dari nomor yang diberikan akan dijadikan sebagai alamat hash

Contoh:

Bayangkan X=14,568. Jika kita mengambil digit 1,3, dan 5, kita akan mendapatkan kode hash = 158.

Rotating Hash

Rotating Hash adalah salah satu Teknik hashing. Sebelum menggunakan Rotating Hash, kita harus menggunakan hash method yang lain. Setelah mendapatkan Hash code dari hash method yang lain, lakukanlah rotation. Rotation dilakukan dengan mengubah posisi digit untuk mendapatkan hash code/address baru.

Contoh:

Bayangkan hash address = 20021. Setelah dilakukan rotation, akan didapatkan hash address = 12002.

Collision

Apakah yang terjadi jika terjadi tabrakan antara hash-key yang satu dengan hash-key yang lain. Hal ini disebut sebagai Collision. Ada dua cara untuk menangani Collision.

1. Linear Probing :Mencari slot kosong selanjutnya dan menaruh string disana. Linear probing akan mengalami beberapa masalah jika terjadi banyak Collision.    
2. Chaining: Masukkan string di slot sebagai chained list (linked list). Dalam chaining ini, kita menyimpan setiap string dalam sebuah chain. Jika terjadi Collision, kita tingal mengubah chain/linked list tersebut.

BINARY TREE

Binary tree adalah sebuah data structure yang non linear yang merepresentasikan hubungan hirearki antara objek.

• Node dipaling atas disebut root 
• Garis yang menghubungkan sebuah parent dengan child disebut edge
• Node yang tidak memiliki children disebut leaf 
• Node yang memiliki parent yang sama disebut sibling 
• Degree dari sebuah node adalah total sub tree dari node tersebut 
• Height/Depth adalah maximum degree dari sebuah node dalam tree 
• Jika ada sebuah garis yang menghubungi p ke q, maka p disebut sebagai ancestor dari q, dan q adalah descendant dari p. 

Konsep Binary Tree

1. Perfect Binary Tree : Adalah sebuah tree dimana setiap level memiliki depth yang sama
2. Complete Binary Tree : Adalah sebuah tree dimana setiap level, kecuali mungkin yang terakhir, dipenuhi, dan semua node ditaruh dipaling kiri. Perfect binary tree juga disebut sebagai complete binary tree
3. Skewed Binary Tree : Adalah sebuah tree dimana setiap node memiliki satu child
4. Balanced Binary Tree : Adalah sebuah tree dimana tidak ada leaf yang lebih jauh dari root daripada leaf lain.

BLOCKHAIN DAN HASHING

Blockchain adalah salah satu cara melakukan cryptography yang sangatlah popular, terutama dalam bitcoin atau cryptocurrency. Dalam pembayaran cryptocurrency, butuhlah digunakan pengamanan yang kuat. Salah satu fungsi yang digunakan dalam Blockchain adalah hashing.

Setiap block dalam blockchain memiliki ribuan transaksi, dan akan sangatlah tidak efisien ketika ingin menyimpan data dalam setiap block. Oleh karena itu, digunakanlah merkle tree yaitu salah satu implementasi hashing, agar lebih efisien dalam mengetahui apakah pengunaan sebuah transaksi ditaruh di block yang mana. Setiap block yang dibuat selanjutnya, akan mempoint ke hash yang ada sebelumnya.

Sebagai kesimpulan, Blockchain tidak akan ada tanpa adanya hashing. Hashing ada sehingga blockchain tersebut tidak tercorrupt  atau dikompromosikan.

BINARY SEARCH TREE

Binary Search Tree

Binary Search Tree adalah salah satu data structure yang mensupport searching lebih cepat, sorting yang lebih baik, dan insertion dan deletion yang mudah. Dalam Binary Search Tree, setiap node disorting. Untuk Node X, elemen yang dikiri tree, adalah element yang lebih kecil dari yang Node X. Sedangkan elemen yang diakanan tree, adalah element yang lebih besar dari Node X.

Dalam Binary Search Tree ada beberapa operasi basic;

1. Find adalah operasi untuk mencari sebuah element dalam tree. Untuk mencari element, dimulai dari root sebuah tree. Jika yang dicari lebih kecil daripada root, maka dia mencari di bagian kiri. Sedangkan, jika yang dicari lebih besar daripada root, maka dia mencari di bagian kanan. 
2. Insert adalah operasi untuk menambah sebuah element dalam tree. Untuk menambah element, dimulai dari root sebuah tree. Jika yang ingin ditambah lebih kecil dari key, maka akan ditambah di bagian kiri. Selain itu, akan ditambah di bagian kanan. Teruskan ini sampai kita mendapatkan node kosong untuk ditaruh.
3. Delete adalah operasi untuk mendelete sebuah element dalam tree. Untuk mendelete sebuah tree ada beberapa cara. 

• Jika key itu leaf, bisa langsung di delete. 
• Jika key itu itu memiliki satu child, delete node tersebut, lalu connect parent node tersebut dengan child tersebut. 
• Jika key itu dalam sebuah node yang memiliki dua child, cari node terkanan dari bagian kiri, lalu ganti node tersebut dengan node yang didapatkan.

TENGAH SEMESTER - AKHIR SEMESTER
AVL TREE
AVL Tree adalah sebuah self-balancing binary tree yang pertama kali dibuat. Self-balancing binary tree adalah salah binary tree yang bisa membalance dirinya sendiri. Sebuah binary tree yang balanced tidak boleh memiliki subtree yang lebih besar daripada subtree yang lain lebih dari 1. Dalam binary tree ada yang disebut balanced factor. Balanced factor adalah hal yang menunjukkan berapa perbedaan antara subtree kiri dan subtree kanan.

Berikut dapat dilihat bahwa pada node 17, AVL mengalami kesalahan karena di subtree kanan terdapat 2 depth, sedangkan di subtree kiri terdapat 1 depth yang menyebabkan ketidak-seimbangan. Hal ini dapat kita benarkan dengan melakukan rotation.

Single Rotation

Single rotation adalah aksi melakukan rotasi di salah satu node sehingga node tersebut dapat menjadi seimbang.

Dari contoh tersebut, kita dapat melihat ketika kita ingin menambah node 12, terdapat ketidak-seimbangan. Oleh sebab itu kita melakukan rotation terhadap node ke 30 dan node ke 22. Hal ini menyebabkan node ke 30 menjadi subtree kanan dan node ke 22 menjadi root. Anak dari node ke 30 pun tetap menjadi subtree di kanan, sedangkan anak kanan dari node ke 22 menjadi anak dari 30 subtree kiri.

Double Rotation

Double rotation dilakukan ketika ketidak-seimbangan terjadi tetapi bukan garis lurus dari root. 

Contohnya disini terdapat ketidak seimbangan dari subtree kiri dan subtree kanan, tetapi ketidakseimbangannya tidak lurus. Oleh sebab itu, kita dapat melakukan single rotation dulu pada node ke 22, sehingga node ke 27 menjadi root dari subtree kiri. Setelah itu lakukan rotation lagi dari node 27 dan 30 sehingga seimbang.

Deletion

Deletion dilakukan seperti biasa, yaitu adalah melakukan pergantian dengan node paling kiri yang paling kanan atau anak kanan yang paling di kiri, tetapi jika setelah didelete terdapat ketidak-seimbangan maka harus dilakukan rotasi.

HEAP AND TRIES

Heap adalah sebuah data structure tree. Heap dibagi menjadi dua tipe:

A. Min-heap: Semua node yang terdapat di tree tersebut harus lebih besar dari node di root tree tersebut. Jadi root pertamanya adalah node paling kecil. Hal itu akan secara rekursif di semua sub tree binary tree.

B. Max-heap: Semua node yang terdapat di tree tersebut harus lebih kecil dari node di root tree tersebut. Jadi root pertamanya adalah node paling besar. Hal itu akan secara rekursif di semua sub tree binary tree. 
C. Min-Max Heap: Min-max heap adalah gabungan dari kegunaan min-heap dan kegunaan max-heap. Min-Max Heap ini biasa diimplementasikan dalam sebuah array.

Min-Heap

Insertion:

a. Masukkan elemen seperti dalam binary tree, yaitu jika node lebih
kecil taruh di kiri, dan jika node lebih besar taruh di kanan.
b. Jika elemen yang di-insert lebih kecil dari node parentnya, tukar
elemen tersebut dengan parentnya.
c. Lakukan terus sampai node tersebut sudah sampai ke posisi yang
benar. Jika sudah, stop operasi tersebut.

Deletion:

a. Ambil elemen yang berada di root tree tersebut, yaitu elemen terkecil.
b. Ambil elemen terakhir yang ditambah di tree tersebut, dan tukar
dengan root tersebut.
c. Jika elemen yang ditukar tersebut lebih besar dari node anaknya, tukar dengan node anak terkecilnya.
d. Lakukan terus sampai node tersebut sudah sampai ke posisi yang
benar. Jika sudah, stop operasi tersebut.

Max-Heap

Insertion:

a. Masukkan elemen seperti dalam binary tree, yaitu jika node lebih
kecil taruh di kiri, dan jika node lebih besar taruh di kanan.
b. Jika elemen yang di-insert lebih besar dari node parentnya, tukar
elemen tersebut dengan parentnya.
c. Lakukan terus sampai node tersebut sudah sampai ke posisi yang
benar. Jika sudah, stop operasi tersebut.

Deletion:

a. Ambil elemen yang berada di root tree tersebut, yaitu elemen terbesar.
b. Ambil elemen terakhir yang ditambah di tree tersebut, dan tukar
dengan root tersebut.
c. Jika elemen yang ditukar tersebut lebih kecil dari node anaknya, tukar dengan node anak terbesarnya.

d. Lakukan terus sampai node tersebut sudah sampai ke posisi yang
benar. Jika sudah, stop operasi tersebut.

Implementasi Min-Max Heap:

1. Gunakan array untuk store data, tapi mulai dari dari index 1

2. Untuk semua node di posisi i:

- Left Child = 2*i

- Right Child = 2*i+1

- Parent Node = i/2

Tries

Trie adalah sebuah contoh data structure yang dibuat berdasarkan sebuah prefix dari string. Tries ini digunakan untuk menyimpan sebuah string yang divisualisasi seperti sebuah grafik. Setiap node memiliki maximal 26 anak.