I Made Yoga Mahendra
2301867633
CD01
Linked List
Pada pertemuan ke 2 saya mempelajari materi tentang Linked List. Linked List adalah salah satu bentuk struktur data yang memuat kumpulan data (node) yang menempati memori dinamis dan setiap node menunjuk kepada node lain melalui pointer sehingga saling berhubungan dengan berurutan.
Pointer adalah Sebuah variabel yang menunjuk variabel lainnya. Pointer adalah sebuah data type.
Circular Single Linked List
* Pada Circular Single Linked List, node terakhir terdapat sebuah pointer yang menunjuk ke node pertama
Doubly Linked List
Double atau two way linked list adalah sebuah linked list data structure yang mempunyai 2 link, yang pertama menunjuk ke data berikutnya dan yang lainnya menunjuk ke data sebelumnya.
Circular Doubly Linked List
Sama seperti circular single linked list, perbedaan terletak pada total pointer di setiap node, pada circular doubly linked list , setiap node mempunyai pointer berjumlah 2
Stack
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP)
Operasi – operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :
1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.
Queue
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-operasi pada Queue
1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.
Notasi Prefix, Infix, dan Postfix
Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.
contoh: A + B * C (infix).
maka notasi prefixnya adalah: +A*BC.
Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
Contoh :
- A + B * C
- (A + B) * C
- A - (B + C) * D ^ E
Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.
Hash Table & Binary Tree
Hashing
Pengertian hasing adalah suatu teknik yang dipakai untuk menyimpan dan mengambul kunci dengan cepat. Dalam hashing, string karakter diubah menjadi nilai yang panjang dan biasanya lebih pendek atau kunci yang mewakili string asli.
Hashing juga dapat diartikan sebagai sebuah konsep mendistribusikan kunci dalam array yang di sebut tabel hash menggunakan fungsi yang telah di tentukan yang disebut sebagai hash function
Hash Table
Pengertian hash table adalah suatu tabel tempat kita menyimpan sstring asli. Indeks tabel adalah hashed key sementara nilainya adalah string asli
Ukuran tabel hash biasanya terdiri dari beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hashed key yang sama
Contoh
kita ingin menyimpan 5 string: define, float, exp, char, atan ke tabel hash dengan ukuran 26. hash
function yang akan kita gunakan adalah "mengubah karakter pertama setiap string menjadi angka antara 0..25 ”
(a akan menjadi 0, b akan menjadi 1, c akan menjadi 2, ..., z akan menjadi 25).
Pada hash function terdapat beberapa cara untuk mengaitkan string menjadi key. Berikut adalah beberapa cara untuk membangun hash function
* Mid-square
Kuadratkan string kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.
Jika key nya adalah string, akan di konversi ke angka
Langkah langkah:
1. kuadratkan nilai pada sebuah key.
2. ekstrak ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.Contoh
nilai = 3121
hasil kuadrat = 3121 * 3121 = 9740641
nilai tengah = 9740641
* Division (most common)
Membagi suatu string dengan memakai operator modulus
Ini adalah metode hashing integer x yang paling sederhana
Function: h(z) = z mod M
z = key
M = nilai yang digunakan untuk membagi key, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.
Contoh
"COBB" akan disimpan di lokasi
(64 + 3 + 64 + 15 + 64 + 2 + 64 + 2)% 97 = 88
* Folding
Metode folding berfungsi dalam dua langkah :
1. Bagilah nilai key menjadi sejumlah bagian di mana disetiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lain
2. Tambahkan bagian individual. Yaitu memperoleh jumlah part1 + part2 + ... + bagian n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.
Contoh
Nilai = 34567
Parts = 34,56, dan 7
Sum = 34 + 56 + 7 = 97
Hash value = 97
* Digit Extraction
Digit extraction adalah digit yang ditentukan sebelumnya dari nomor yang diberikan yang dianggap sebagai hash address
Contoh
X = 14.568
Jika kita mengekstrak digit 1,3, dan 5, kita akan mendapatkan hash code yaitu : 158
* Rotating Hash
Gunakan metode hash (seperti metode pembagian atau mid-square)
Lakukan rotasi
Contoh
Diberikan hash address = 20021
Hasil rotasi = 12002
Impelemntasi Hash Table pada Block Chain
Implementasi hash table pada block chain terdapat pada kriptografi hash, yang berfungsi sebagai penghubung block chain
Implementasi hash table pada block chain terdapat pada kriptografi hash, yang berfungsi sebagai penghubung block chain
Binary Tree
Tree
Pengertian tree adalah suatu data structure non linear yang menggambarkan hubungan antara suatu data dengan objek.
Node di tree dapat disimpan dimana saja dan terhubung dengan pointer
Konsep tree :
1. Node yang paling atas di sebut root
2. Gari yang menghubungkan parent dan child disebut edge
3. Node yang tidak punya child disebut leaf
4. Node yang mempunyai parent yang sama disebut sibling
5. Total sub tree pada sebuah node disebut degree
6. Maksimum degree pada sebuah node disebut height / depth
7. Ancestor dan Descendant
Binary Tree
Mirip dengan tree hanya bedanya kalau binary tree di setiap node paling banyak memiliki 2 child
Tipe tipe Binary Tree
1. Perfect Binary Tree
setiap levelnya memiliki depth yang sama
2. Complete BinaryTree
setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodenya paling panjang kekiri
3. Skewed Binary Tree
setiap nodenya memiliki paling banyak hanya satu child
4. Balance Binary Tree
dimana setiap leafnya sama jauhnya dari root
Binary Search Tree
Binary Search Tree (BST) adalah suatu bentuk struktur data yang menggambarkan hubungan antara elemen satu dengan elemen lainnya. Pada Binary Search Tree hanya dapat memiliki maksimal dua percabangan saja dan memiliki syarat nilai node di kiri harus lebih kecil dari node di kanan.
Keuntungan memakai Binary Search Tree :
1. Proses searching yang jauh lebih cepat
2. Proses sorting yang jauh lebih cepat
3. Mempermudah proses insertion dan deletion
Sebuah Binary Search Tree mempunya 3 fungsi yaitu:
1. Find
2. Insert
3. Remove
Fungsi Search :
1. Searching dimulai dari root, jika nilai x yang dicari, dan x berada di root, maka proses searching selesai
2. Jika nilai x lebih kecil dari root , maka proses searching rekursif ke sebelah kiri
3. Jika nilai x lebih besar dari root, maka proses searching rekursif ke sebelah kanan
Fungsi Insertion :
1. Dimulai dari root
2. Jika nilai x lebih kecil dari key , maka cek dengan sub tree bagian kiri secara rekursif, begitu juga sebaliknya.
3. Ulangi proses tersebut sampai menemukan node yang kosong, untuk insert nilai x
Fungsi Remove :
- Node tanpa child = node dapat langsung dihapus
- Node dengan 1 child = node child akan menggantikan posisinya
- Node dengan 2 child = node akan digantikan oleh node paling kiri dari sub tree kanan , atau dapat juga digantikan oleh child paling kanan dari sub tree kri
Binary Search Tree
Binary Search Tree (BST) adalah suatu bentuk struktur data yang menggambarkan hubungan antara elemen satu dengan elemen lainnya. Pada Binary Search Tree hanya dapat memiliki maksimal dua percabangan saja dan memiliki syarat nilai node di kiri harus lebih kecil dari node di kanan.
Keuntungan memakai Binary Search Tree :
1. Proses searching yang jauh lebih cepat
2. Proses sorting yang jauh lebih cepat
3. Mempermudah proses insertion dan deletion
Sebuah Binary Search Tree mempunya 3 fungsi yaitu:
1. Find
2. Insert
3. Remove
Fungsi Search :
1. Searching dimulai dari root, jika nilai x yang dicari, dan x berada di root, maka proses searching selesai
2. Jika nilai x lebih kecil dari root , maka proses searching rekursif ke sebelah kiri
3. Jika nilai x lebih besar dari root, maka proses searching rekursif ke sebelah kanan
Fungsi Insertion :
1. Dimulai dari root
2. Jika nilai x lebih kecil dari key , maka cek dengan sub tree bagian kiri secara rekursif, begitu juga sebaliknya.
3. Ulangi proses tersebut sampai menemukan node yang kosong, untuk insert nilai x
Fungsi Remove :
- Node tanpa child = node dapat langsung dihapus
- Node dengan 1 child = node child akan menggantikan posisinya
- Node dengan 2 child = node akan digantikan oleh node paling kiri dari sub tree kanan , atau dapat juga digantikan oleh child paling kanan dari sub tree kri
