Rangkuman Semester 2
I.Pointer
Pointer merupakan suatu tipe data yang digunakan untuk mengambil suatu address/alamat.Suatu variabel akan disimpan dalam memori RAM (Random Access Memory) dimana isi dari variabel tersebut akan disimpan sesuai dengan alamat dari variabel tersebut.Untuk mengakses data variabel tersebut,dibutuhkan pointer yang biasa ditandakan dengan aestrisk(*).
A.Single Linked List
Single Linked List merupakan struktur data yang terhubung satu sama lain melalui pointer dimana pointer tersebut akan menunjuk ke struktur data / node lainnya. Ilustrasinya sebagai berikut :
disebut dengan Single Linked List karena hanya memiliki single link untuk menunjuk alamat ke struktur data / node selanjutnya. Node terakhir menunjuk alamat ke NULL dimana NULL digunakan sebagai kondisi berhenti saat pembacaan isi dari linked list tersebut.
 |
| Contoh Single Linked List. |
disebut dengan Single Linked List karena hanya memiliki single link untuk menunjuk alamat ke struktur data / node selanjutnya. Node terakhir menunjuk alamat ke NULL dimana NULL digunakan sebagai kondisi berhenti saat pembacaan isi dari linked list tersebut.
 |
| Memasukan node ke awal barisan. |
 |
| Contoh Circular Single List |
B.DOUBLY LINKED LIST
Doubly Linked List mirip dengan Singly Linked List namun perbedaan nya adalah Doubly Linked List mengambil 2 alamat dari struktur data/ node lainnya (yaitu prev & next).Untuk penjelasan yang lebih jelas dapat dilihat dari,https://www.geeksforgeeks.org/doubly-linked-list/
Contoh double linked list : Insertion.
 |
| Contoh Doubly Linked List |
 |
| Memasukan data ke linked list.Sumber : https://media.geeksforgeeks.org/wp-content/cdn- uploads/gq/2014/03/DLL_add_front1.png |
Circular double linked list mirip circular single linked list namun, setiap node menyimpan 2 alamat dari node lainnya.
 |
| Contoh Circular Double Linked List.source =https://media.geeksforgeeks.org/wp-content/uploads/Circular-doubly-linked-list.png |
Stack and Queue
I.Stack
Stack merupakan basic dari data structure yang merepresentasikan tumpukan /stack aslinya ,dimana yang terakhir dimasukan,keluar pertama kali.Sebagai ilustrasinya,dapat dibayangkan dengan tumpukan buku dimana kita hanya dapat mengambil buku teratas untuk memindahkan ke sesuatu tempat.Implementasi dari stack juga disebut dengan LIFO(Last In First Out). Konsep stack digunakan pada DFS(Depth First Search) yang merupakan algoritma untuk mencari suatu data pada trees. Terdapat 3 operan dasar di stack yaitu,push (memasukan suatu data),pop (delete data teratas) ,peek (melihat data teratas).
 |
| Operan dasar di Stack. Sumber :https://cdn.journaldev.com/wp-content/uploads/2018/05/swift-stacks-diagram.png |
Prefix,Infix,Postfix
Terdapat 3 notasi operasi untuk suatu aritmatika yaitu,prefix,infix,dan postfix.Sebelummemahami tentang notasi operasi untuk suatu aritmatika, perlu dipahami terlebih dahulu terjadinya notasi dalam struktur data.Notasi terbentuk dari operan dan operator.Operan merupakan data /nilai dalam suatu proses.Sedangkan Operator merupakan fungsi yang digunakan.Contohnya: A + B. Operan adalah A,B sedangkan Operator adalah +.
1. Infix
Merupakan notasi yang sering dijumpai oleh orang orang.Urutan infix yaitu (Operand,Operator,Operand). Seperti contohnya (1+5)*(6/2)^3.
2.Prefix
Merupakan notasi yang terbentuk dari (Operator,Operand Operand) sehingga bentuk infix dapat diubah menjadi sebagai berikut : * + 1 5 ^ / 6 2 3.
Cara untuk mengubah infix ke prefix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
= (+ 1 5) * (/ 6 2) ^ 3
= (+ 1 5) * (^ / 6 2 3)
= * + 1 5 ^ / 6 2 3.
3.Postfix
Merupakan notasi yang terbentuk dari (Operand,Operand,Operator) sehingga bentuk infix dapat diubah menjadi sebagai berikut : 1 5 + 6 2 / 3 ^ *.
Cara untuk mengubah infix ke postfix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
= (1 5 +) * (6 2 /) ^3
= (1 5 + ) * (6 2 / 3 ^)
= 1 5 + 6 2 / 3 ^ *
II.Queue
Merupakan linear data struktur seperti stack.Namun queue merepresentasikan antrian dimana yang pertama kali masuk,pertama kali keluar.Queue juga dikenal dengan FIFO(First In First Out).Ilustrasi yang baik untuk mempelajari queue adalah saat mengantri untuk memesan makanan.Pastinya pelanggan pertama akan mendapatkan makanan terlebih dahulu.Konsep queue digunakan pada BFS(Breadth First Search) yang merupakan algoritma untuk mencari suatu data tree.Perbedaan dengan DFS(Depth First Search) adalah DFS menggunakan konsep stack,sedangkan BFS menggunakan konsep queue.Terdapat 3 operan dasar pada queue yaitu Enqueue (memasukan data pada queue) , Dequeue (Menghapus data awal data pada queue) ,dan peek (Melihat data ter-awal).
Hash tables adalah suatu table / array dimana tempat menyimpan string yang original.Ukuran hash table biasanya lebih sedikit dari jumlah string yang mungkin sehingga beberapa string memiliki hashed key yang sama.
Merupakan notasi yang sering dijumpai oleh orang orang.Urutan infix yaitu (Operand,Operator,Operand). Seperti contohnya (1+5)*(6/2)^3.
2.Prefix
Merupakan notasi yang terbentuk dari (Operator,Operand Operand) sehingga bentuk infix dapat diubah menjadi sebagai berikut : * + 1 5 ^ / 6 2 3.
Cara untuk mengubah infix ke prefix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
= (+ 1 5) * (/ 6 2) ^ 3
= (+ 1 5) * (^ / 6 2 3)
= * + 1 5 ^ / 6 2 3.
3.Postfix
Merupakan notasi yang terbentuk dari (Operand,Operand,Operator) sehingga bentuk infix dapat diubah menjadi sebagai berikut : 1 5 + 6 2 / 3 ^ *.
Cara untuk mengubah infix ke postfix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
= (1 5 +) * (6 2 /) ^3
= (1 5 + ) * (6 2 / 3 ^)
= 1 5 + 6 2 / 3 ^ *
II.Queue
Merupakan linear data struktur seperti stack.Namun queue merepresentasikan antrian dimana yang pertama kali masuk,pertama kali keluar.Queue juga dikenal dengan FIFO(First In First Out).Ilustrasi yang baik untuk mempelajari queue adalah saat mengantri untuk memesan makanan.Pastinya pelanggan pertama akan mendapatkan makanan terlebih dahulu.Konsep queue digunakan pada BFS(Breadth First Search) yang merupakan algoritma untuk mencari suatu data tree.Perbedaan dengan DFS(Depth First Search) adalah DFS menggunakan konsep stack,sedangkan BFS menggunakan konsep queue.Terdapat 3 operan dasar pada queue yaitu Enqueue (memasukan data pada queue) , Dequeue (Menghapus data awal data pada queue) ,dan peek (Melihat data ter-awal).
 |
| Contoh dasar queue.Sumber : https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/02/Queue.png |
Hashing,Hash Tables,Trees and Binary Tree
Hashing
Hashing merupakan tehnik untuk menyimpan dan mengambil kunci dengan cepat.Hashing mengubah panjang input ke string dengan ukuran tetap.Artinya,seberapa banyak panjang input yang diberikan,dapat diubah menjadi array dari string dan angka melalui suatu algoritma.Pesan yang akan di hashing adalah input,algoritma yang akan digunakan untuk hashing disebut hash function dan hasilnya disebut hash value.
Hash Tables
Hash Function
Ada banyak cara untuk mengubah suatu string ke key,yaitu bisa dengan :
a).Mid - square : Mengkuadratkan suatu string,lalu gunakan digit tengah sebagai hash key.Seperti contohnya nilai = 3121. Di kuadratkan menjadi 9740641 lalu diambil digit tengah yaitu 406 sebagai hash keynya.
b).Division : Membagi suatu string menggunakan operator modul.Seperti contohnya : "HELLO" akan di masukan di lokasi (64+8+64+5+64+10+64+10+64+15) % 97 = 77
c).Folding : Mempartisi string ke beberapa bagian,lalu tambahkan partnya untuk mendapatkan hash keynya.Seperti contohnya 123.Membagi menjadi 1 dan 23 sehingga hash keynya menjadi 24.(anggap lokasi ada 50).Apabila melebihi 50, seperti contohnya 56,biarkan angka awalannya sehingga menjadi 6.
d).Digit Extraction : Digit yang telah ditentukan dari yang diberikan akan dijadikan alamat hash.Seperti contohnya 123456. Apabila mengambil di bagian ke 2 ,ke 3 dan ke 4, akan mendapatkan 234 sehingga hash key nya adalah 234.
e).Rotating Hash : Menggunakan cara hash apapun seperti division atau mid-square.Setelah mendapatkan hash code dari cara hash tersebut,lakukan rotasi.Dimana rotasi dilakukan dengan men-shift kan dikit menjadi alamat hash.Seperti contohnya 123456,dengan rotasi ,akan didapatkan menjadi 654321 sebagai alamat hash yang baru.
Collision : Collision terjadi ketika 2 data yang memiliki hash value yang sama.Untuk itu,terdapat 2 cara untuk menangani collision yaitu dengan cara :
a).Linear Probing
Dilakukan dengan cara mencari slot yang kosong dan memasukan string tersebut disana.
b).Chaining
Memasukan string di slot sebagai linked list.
Trees
Trees merupakan non linear struktur data yang merepresentasikan hirarki hubungan antar objek data.Node di dalam tree dapat dimasukan dimana saja dan terhubung dengan pointer.Sebuah tree dapat di definisikan secara rekursif sebagai koleksi node yang di mulai di akar node/root node dimana setiap node mengandung suatu value bersama dengan merujuk ke node lainnya.
Konsep Tree
a).Root = Node paling atas
b).Edge = garis yang menghubungkan parent ke child
c).Leaf = Node yang tidak memiliki child
d).Degree of node = Degree suatu node adalah total sub-tree pada node
e).Sibling = Node yang memiliki parent yang sama
f).Height/Depth = maksimum degree pada suatu node
g).Ancestor & Descendant = Jika terdapat garis yang menghubungkan node p ke node q,maka p disebut ancestor dan q adalah descendant dari p.
Binary Tree
Binary tree merupakan tree yang memiliki dua child di setiap nodenya(child kiri & child kanan).
Terdapat tipe Binary tree yaitu :
a).Perfect Binary Tree = binary tree yang setiap levelnya memiliki kedalaman yang sama.
b).Complete Binary Tree =binary tree yang setiap levelnya kecuali yang kemungkinan terakhir,terisi dan setiap nodenya paling panjang ke kiri.Perfect Binary Tree termasuk dengan Complete Binary Tree.
c).Skewed Binary Tree = binary tree yang memiliki setiap node paling banyak 1 child.
d).Balanced Binary Tree = binary tree yang dimana tidak ada leaf yang paling jauh dari root dibanding leaf lainnya.
a).Insert
-Menghilangkan suatu node dengan memiliki dua anak/child : Menghapus node tersebut dan menggantinya dengan child/anak tsb.Dapat menggunakan 2 cara untuk mengganti nya yaitu dengan mencari sub-tree ke kiri child paling kanan (leafnya) atau dengan mencari sub tree ke kanan child paling kiri(leafnya)
Ada banyak cara untuk mengubah suatu string ke key,yaitu bisa dengan :
a).Mid - square : Mengkuadratkan suatu string,lalu gunakan digit tengah sebagai hash key.Seperti contohnya nilai = 3121. Di kuadratkan menjadi 9740641 lalu diambil digit tengah yaitu 406 sebagai hash keynya.
b).Division : Membagi suatu string menggunakan operator modul.Seperti contohnya : "HELLO" akan di masukan di lokasi (64+8+64+5+64+10+64+10+64+15) % 97 = 77
c).Folding : Mempartisi string ke beberapa bagian,lalu tambahkan partnya untuk mendapatkan hash keynya.Seperti contohnya 123.Membagi menjadi 1 dan 23 sehingga hash keynya menjadi 24.(anggap lokasi ada 50).Apabila melebihi 50, seperti contohnya 56,biarkan angka awalannya sehingga menjadi 6.
d).Digit Extraction : Digit yang telah ditentukan dari yang diberikan akan dijadikan alamat hash.Seperti contohnya 123456. Apabila mengambil di bagian ke 2 ,ke 3 dan ke 4, akan mendapatkan 234 sehingga hash key nya adalah 234.
e).Rotating Hash : Menggunakan cara hash apapun seperti division atau mid-square.Setelah mendapatkan hash code dari cara hash tersebut,lakukan rotasi.Dimana rotasi dilakukan dengan men-shift kan dikit menjadi alamat hash.Seperti contohnya 123456,dengan rotasi ,akan didapatkan menjadi 654321 sebagai alamat hash yang baru.
Collision : Collision terjadi ketika 2 data yang memiliki hash value yang sama.Untuk itu,terdapat 2 cara untuk menangani collision yaitu dengan cara :
a).Linear Probing
Dilakukan dengan cara mencari slot yang kosong dan memasukan string tersebut disana.
b).Chaining
Memasukan string di slot sebagai linked list.
 |
| Contoh Chaining.Sumber:https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2015/07/hashChaining1.png |
Trees merupakan non linear struktur data yang merepresentasikan hirarki hubungan antar objek data.Node di dalam tree dapat dimasukan dimana saja dan terhubung dengan pointer.Sebuah tree dapat di definisikan secara rekursif sebagai koleksi node yang di mulai di akar node/root node dimana setiap node mengandung suatu value bersama dengan merujuk ke node lainnya.
Konsep Tree
a).Root = Node paling atas
b).Edge = garis yang menghubungkan parent ke child
c).Leaf = Node yang tidak memiliki child
d).Degree of node = Degree suatu node adalah total sub-tree pada node
e).Sibling = Node yang memiliki parent yang sama
f).Height/Depth = maksimum degree pada suatu node
g).Ancestor & Descendant = Jika terdapat garis yang menghubungkan node p ke node q,maka p disebut ancestor dan q adalah descendant dari p.
Binary Tree
Binary tree merupakan tree yang memiliki dua child di setiap nodenya(child kiri & child kanan).
Terdapat tipe Binary tree yaitu :
a).Perfect Binary Tree = binary tree yang setiap levelnya memiliki kedalaman yang sama.
b).Complete Binary Tree =binary tree yang setiap levelnya kecuali yang kemungkinan terakhir,terisi dan setiap nodenya paling panjang ke kiri.Perfect Binary Tree termasuk dengan Complete Binary Tree.
c).Skewed Binary Tree = binary tree yang memiliki setiap node paling banyak 1 child.
 |
| sumber :https://www.gatevidyalay.com/wp-content/uploads/2018/07/Skewed-Binary-Tree-Example.png |
 |
| sumber :https://www.baeldung.com/wp-content/uploads/2019/11/Zrzut-ekranu-2019-10-31-o-15.31.40.png |
Binary Search Tree
Binary Search Tree (BST) merupakan sebuah struktur data yang digunakan untuk menyimpan suatu barang (seperti angka,nama dan lain lainnya) dalam suatu memori. Binary Search Tree menyimpan kunci mereka secara tersortir.Disebut Binary Tree karena setiap tree nya memiliki maximum 2 anak / child dan disebut search tree karena dapat mencari suatu angka dalam waktu O(Log (n)).Yang membedakan dari Binary Search tree dan Binary Tree adalah,sebelah kiri sub tree dari suatu node harus lebih kecil dari node tersebut.Dan sebelah kanan sub tree dari suatu node harus lebih besar dari node tersebut.Terdapat operasi basic dari Binary Search Tree yaitu :
a).Insert
Memasukan sebuah data ke dalam BST.Apabila suatu data lebih kecil dari node data/key nya,maka melakukan pengecekan secara berulang.Sedangkan apabila suatu data lebih besar dari node data/key nya maka akan melakukan suatu pengecekan secara berulang.Ulangi sampai menemukan node yang kosong untuk dimasukan oleh data tersebut.
 |
| Contoh Insert pada BST.sumber :https://www.techiedelight.com/wp-content/uploads/Insert-into-BST.png |
b).Search
Mencari suatu data dalam BST.Apabila data root itu yang dicari,maka berhenti.Apabila data yang dicari lebih besar dari root maka lakukan pengecekan ke arah kanan secara rekursif.Sedangkan apabila yang dicari lebih kecil dari root maka lakukan pengecekan ke arah kiri.
 |
| Contoh Search pada Binary Search Tree.Sumber:https://cdn.programiz.com/sites/tutorial2program/files/bst-downward-recursion-step.jpg |
c).Delete
Terdapat 3 kasus yang perlu dipikirkan yaitu:
-Menghilangkan suatu node tanpa memiliki child : langsung menghapus node tersebut.
-Menghilangkan suatu node dengan memiliki satu child/anak : Menghapus node tersebut dan menggantinya dengan child/anak tersebut.
 |
| Contoh Linear probing.Sumber :https://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/FIGS/map44b.gif |
 |
| Delete Node Sumber:https://media.geeksforgeeks.org/wp-content/uploads/deletion-in-binary-tree.png |
Comments
Post a Comment