CA01-006

Linked List

Butuh malloc untuk alokasi value ke memory yang berbeda

Pointer next dibuat untuk menyimpan data setelahnya, struct data untuk recursive

Indikator posisi awal dengan if head==NULL

Pergeseran dilakukan dengan next->curr

Tail->Next==NULL Sebagai penanda akhir list

Next adalah alamat curr setelah bergeser

Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya

Double Linked List
Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya

Keuntungan Double linked List
1.       Implementasinya tidak jauh berbeda dari Single linksed list
2.       Mampu bergeser dua arah
3.       Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan dihapus. Double linked list hanya butuh pointer node yang ingin dihapus
4.       Bisa di allocate dan di deallocate dengan lebih mudah
5.       Salah satu data structures yang paling efisien jika pergeseran dengan dua arah dibutuhkan
Aplikasinya
                Navigasi
                Back/forward pages di browser
                Undo/redo
Stack & Queue

Stack/tumpuk merupakan LIFO (Last In First Out) karena hanya memiliki head/kepala. Jika digambarkan, seperti tumpukan piring.
Jika ditambah, piring paling baru ada di paling atas, dan saat diambil, piring paling atas lah yang terambil terlebih dahulu. Jika diasumsikan hanya dapat mengambil/menambah satu piring secara berurutan, maka Stack hanya mengenal kepala/Top/Head, dan piring-piring setelahnya.

Di sisi lain, Queue merupakan FIFO (First In, First Out), karena memiliki head dan tail, jika digambarkan, seperti barisan piring

Stack
Stack dalam Data Structure merupakan struktur yang cara penambahan/penghapusan melalui satu end saja, yaitu kepala/head. Seperti penjelasan awal, Push/Insert data dimasukkan dari depan, begitu juga Pop/Delete
Kegunaan Stack
konsep Stack dalam aplikasi adalah undo/redo browser. Ketika halaman baru dibuka, maka dilakukan insert, dan ketika undo, maka akan dilakukan pop dari halaman sekarang/head. Konsep Stack untuk undo/redo juga diaplikasikan di beberapa text editor.
Queue
Queue dalam Data Structure merupakan struktur yang cara penambahan/penghapusan melalui dua end, yaitu kepala/head dan ekor/tail.  Push/Insert data dilakukan di head/kepala, dan penghapusan dilakukan di ekor/tail.
Kegunaan Queue
Penggunaan Queue ada dalam CPU Scheduling, Multiprogramming, dan asynchronous data transfer. Dalam sehari-hari, seperti urutan panggilan di call center, dan antrian kasir.

Hashing
Hashing adalah pengubahan dari sebuah string of characters ke sebuah ‘kunci’ yang mewakili string awal. Hashing dilakukan untuk memberikan index dan mengambil item yang ada di suatu database karena pencarian akan lebih cepat melalui hash ‘key’ nya yang sudah disingkat, dibandingkan mencari secara keseluruhan.
            Hashing juga biasa digunakan untuk mengencrypt sebuah data. Hash key yang dibentuk biasanya berdasarkan suatu hitungan matematika. Saqlah satu contohnya adalah dengan message. Dari message yang akan dikirim, akan dibuat sebuah hash, dan juga enkripsi untuk pesan itu sendiri. Pesan yang telah dienkripsi dan hash yang telah dibuat akan diterima di end yang lain. Setetalh diterima, maka receiver akan mendecrypt hash dan pesan tersebut. Setelah itu, receiver akan mengenerate hash sesuai dengan pesan yang didecrypt. Jika hash yang di generate receiver sama dengan hash dari sender, maka keduanya akan tersambung.
            Hash table adalah sebuah array/data structure yang menyimpan isi asli dari data tersebut, index table tersebut adalah hash key dari data tersebut, dan value nya adalah data asli yang membuat hash key.
            Hash Function adalah function untuk memetakan data dari beragam ukuran ke sebuah value yang berukuran sama, biasanya berupa integer. Value yang akan dikembalikan dari function tersebut adalah hash key.

ada kemungkinan hash key yang dihasilkan memiliki nilai yang sama. Misalkan menggunakan digit extraction dengan digit ke-4 dan ke-3. Jika ada 2 integer yaitu 2812 dan 7512, keduanya memiliki hash key yang sama, yaitu 21. Hal ini dinamakan tabrakan/collision.
            Maka dari itu, hash function yang baik harus memiliki ciri-ciri sebagai berikut:
1.      Hash key yang dihasilkan dari hash values yang mirip memberikan hasil yang berbeda
2.      Hash function tersebut mudah dimengerti dan mudah untuk dicompute
3.      Hash key yang dihasilkan harus seragam dalam sebuah array/linked list
4.      Hash function yang baik seharusnya menggunakan semua input data








Binary Tree
Tree dalam data structures adalah sebuah struktur yang memiliki tingkatan/hierarki. Konsep Tree sudah sering digunakan dalam sehari-hari, seperti dalam organisasi, makalah, jurnal, dan lain-lain. Dalam computer sendiri, tree digunakan dalam sistem folder dan subfolder.
Beberapa property dari Binary tree adalah:
1.       Node paling banyak di tingkat x adalah 2x
2.       Jumlah node maksumym yang dimiliki binary tree dengan height h adalah 2h+1-1
3.       Height maksimum dari sebuah binary tree dengan jumlah node n adalah n-1
4.       Height minimu dari sebuah binary tree dengan jumlah node n adalah 2log(n)


BST/ Binary Search Tree
BST adalah sebuah cara untuk mengurutkan data berdasarkan Hieerarki. Karena Binary, masing-masing node hanya punya boleh keturunan maksimum dua. Dalam penyusunannya, data yang lebih besar ada di kanan dan data yang lebih kecil ada di kiri, bisa juga sebaliknya.
Insert: insert dalam BST setelah insert pertama adalah
·         Jika node yang dimasukkan lebih besar dari node atasnya, maka keturunannya akan ada di bawah dan diletakkan di sisi kanan node tersebut.
·         Jika node yang dimasukkan lebih kecil dari node atasnya, maka keturunannya aka nada di bawah dan diletakkan di sisi kiri node tersebut
Pop : Pop dalam BST memiliki aturan sebagai berikut:
·         Jika pop dilakukan pada leaf/ node yang tidak memiliki keturunan maka node tersebut akan langsung di pop
·         Jika pop dilakukan pada node yang memiliki keturunan, maka node tersebut akan mencari angka yang lebih besar dari sisi kiri, tetapi juga lebih besar di sisi kanan
Simulasi BST dapat dilihat di https://www.cs.usfca.edu/~galles/visualization/BST.html


Komentar

Posting Komentar

Postingan populer dari blog ini

CA01-011 Heap & Tries

Gambar
Max Heap : pohon yang parentnya selalu lebih besar dari anaknya Min Heap : pohon yang parentnya selalu lebih kecil dari anaknya Min-Max Heap : Pohon yang selang-seling parentnya Heap biasanya menggunakan array, tapi bisa menggunakan linked list juga. Dimulai dari 1 untuk memudahkan mencari node. Insert dalam heap dilakukan dengan seperti berikut: 1.        Insert node seperti dalam Binary Tree 2.        cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk min heap, lebih kecil dari parentnya untuk max heap) 3.        Jika salah, maka angka tersebut ditukar dengan parentnya 4.        lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root aksi yang dilakukan tersebut disebut Heapify Up untuk delete dilakukan sebagai berikut: 1.        hap...
Baca selengkapnya

CA01-004

BST/ Binary Search Tree BST adalah sebuah cara untuk mengurutkan data berdasarkan Hieerarki. Karena Binary, masing-masing node hanya punya boleh keturunan maksimum dua. Dalam penyusunannya, data yang lebih besar ada di kanan dan data yang lebih kecil ada di kiri, bisa juga sebaliknya. Insert: insert dalam BST setelah insert pertama adalah ·          Jika node yang dimasukkan lebih besar dari node atasnya, maka keturunannya akan ada di bawah dan diletakkan di sisi kanan node tersebut. ·          Jika node yang dimasukkan lebih kecil dari node atasnya, maka keturunannya aka nada di bawah dan diletakkan di sisi kiri node tersebut Pop : Pop dalam BST memiliki aturan sebagai berikut: ·          Jika pop dilakukan pada leaf/ node yang tidak memiliki keturunan maka node tersebut akan langsung di pop ·          Jika pop...
Baca selengkapnya