Summary & Review 1

Hi!!
Pada blog kali ini, kita akan mereview materi-materi yang  sudah dipelajari sebelumnya. 

1. Linked List
Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence. 

Single/ Singly Linked List
Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. 

Circular Singly Linked List
Circular Single Linked List adalah suatu linked list dimana tail menuju ke head dan hanya memiliki satu arah, serta tidak memiliki nilai NULL. 

Double/ Doubly Linked List
Double Linked List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan (head) atau belakang (tail).

Circular Doubly Linked List
Circular Doubly Linked List adalah linked list dengan menggunakan pointer, dimana  setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut dengan pointer next dan prve-nya menunjuk ke dirinya sendiri secara circular.


Linked list, baik single linked list, maupun double linked list memiliki dua operasi utama, yaitu push dan pop. Push berarti menambah, insert data, sedangkan pop berarti delete atau menghapus.


2. Stack and Queue
Stack
Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Sistem pengaksesan pada stack menggunakn sistem LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack).

Queue
Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Sistem pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

Untuk lebih jelasnya mengenai code push dan pop, serta stack and queue bisa mengakses link ini : https://data-structure-sheila.blogspot.com/2020/03/linked-list-stack-queue.html


3. Hashing Table and Binary Tree
HASHING TABLE
Hashing adalah teknik untuk melakukan penambahan/insertion, penghapusan/deletion dan pencarian/searching dengan constant average time. Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan array sebagai medium penyimpanan dan menggunakan fungsi hash untuk menghasilkan sebuah indeks dimana suatu elemen harus dimasukkan atau ada. Hal ini menyebabkan waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain. 

Hash Function
Hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Berikut adalah beberapa metode penting hash function:
1. Mid-square
2. Division
3. Folding
4. Digit Extraction
5. Rotating Hash

Collision
Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja. Berikut ini cara-cara yang digunakan untuk mengatasi collision :
1. Closed hashing (Open Addressing) :
a. Linear Probing
b. Quadratic Probing
c. Double hashing
2. Open hashing (Separate Chaining)

BINARY TREE
Tree bisa didefinisikan sebagai kumpulan simpul / node dengan satu elemen khusus yang disebut root dan node lainnya. Subtree adalah tree yang terbagi menjadi himpunan-himpunan yang tak saling berhubungan satu sama lainnya. Binary tree/ pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. 

Tipe Binary Tree
1. PERFECT binary tree adalah pohon biner di mana setiap tingkat berada pada kedalaman yang sama.

2. COMPLETE binary tree adalah pohon biner di mana setiap tingkat, kecuali yang terakhir, sepenuhnya diisi dan semua node yang sejauh mungkin kiri. Sebuah PERFECT binary tree pasti COMPLETE binary tree.

3. SKEWED binary tree adalah pohon biner di mana setiap node memiliki paling banyak satu anak.

4. BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Implementasi Hash Pada Blockchain
Blockchain adalah sistem pencatatan transaksi di banyak database yang tersebar luas di banyak komputer yang masing-masing memuat catatan yang identikal. Blockchain memiliki tiga mekanisme, salah satunya menggunakan teknik hash. Hash berguna untuk mendeteksi perubahan yang terjadi didalam blockchain. Teknik ini membuat blockchain lebih aman dan kredibel dalam menyimpan data-data penting karena jika ada yang mengubah satu blok dalam blockchain maka nilai hashnya akan berubah menjadi tidak valid. Lalu perubahan tersebut akan menyebabkan seluruh blockchain menjadi tidak valid.

Untuk lebih jelasnya mengenai hash table dan binary tree, bisa mengakses link ini : https://data-structure-sheila.blogspot.com/2020/03/hashing-table-binary-tree.html


4. Binary Search Tree (BST)
Binary Search Tree (BST) adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Jadi, Binary Search Tree adalah proses searching berbasis binary tree. 

Tujuan membedakan kiri dan kanan sesuai besaran nilainya adalah untuk memberikan efiesiensi terhadap proses searching sehingga proses search akan lebih cepat. 

Sifat Binary Tree: 
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
1. PreOrder
2. InOrder
3. PostOrder

Operasi BST ada dua, yaitu:
1. Insert
Ketika insert sebuah  node baru perlu diperhatikan operasi pencarian posisi yang sesuai. Dalam hal ini node baru tersebut akan menjadi daun/leaf.

2. Delete
Operasi delete memiliki 3 kemungkinan : 
- Delete terhadap node tanpa anak/child (leaf/daun) : node dapat langsung dihapus
- Delete terhadap node dengan satu anak/child : maka node anak akan menggantikan posisinya.
- Delete terhadap node dengan dua anak/child : maka node akan digantikan oleh node paling kiri dari Sub Tree Kanan atau dapat juga digantikan oleh anak paling kanan dari Sub Tree Kiri.

Untuk lebih jelasnya mengenai BST, dapat mengakses link ini : https://data-structure-sheila.blogspot.com/2020/03/binary-search-tree-bst.html


5. Contoh Code Double Linked List 
Berikut merupakan contoh code dalam Bahasa C, yaitu aplikasi seperti di supermarket. Aplikasi ini memiliki fungsi add item, edit item, delete item, view item, dan checkout. 
atau untuk file .cpp nya bisa mengakses link ini : https://drive.google.com/open?id=16IF9KQfsdpy098GK2osXbmAsgErl_AXu


Dibuat oleh : Sheila Gracia Angelina
NIM : 2301857456

Comments

Post a Comment

Popular posts from this blog

Linked List, Stack, Queue

Image
Pada pertemuan hari ini, kita membahas lebih dalam mengenai coding Single Linked List dan Double Linked List. Pada blog ini saya akan membahas mengenai pelajaran yang telah diajarkan tadi dan menambahkan mengenai stack and queue. LINKED LIST Pada blog sebelumnya, saya pernah menulis mengenai apa itu Single Linked List dan Double Linked List. Sekarang saya akan membahas mengenai coding operasi pada Linked List, yaitu push dan pop pada Single Linked List dan Double Linked List yang paling sederhana. Pertama-tama, kita harus mendefinisikan struct untuk nodenya. Untuk lebih jelasnya bisa dilihat pada gambar di bawah ini. 1. Single Linked List a) PUSH Untuk push pada Single Linked List dapat dilihat pada gambar di bawah ini. Pada coding di atas, kita menggunakan malloc untuk mengalokasikan memori secara dinamis. Setelah itu kita memberikan value kepada curr dengan nilai a . Dilanjutkan dengan kondisi if else. Jika kita baru push sekali, maka nilai pada head...
Read more

Binary Search Tree (BST)

Image
Pada blog sebelumnya saya sudah membahas mengenai Binary Tree. Sekarang kita akan membahas mengenai materi selanjutnya, yaitu Binary Search Tree (BST). Binary Search Tree (BST) adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node . Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Jadi, Binary Search Tree adalah proses searching berbasis binary tree. Tujuan membedakan kiri dan kanan sesuai besaran nilainya adalah untuk memberikan efiesiensi terhadap proses searching sehingga proses search akan lebih cepat. Sifat Binary Tree:  - Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya. - Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya. 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST : - PreOrder a. Cetak data pad...
Read more