Summary
Rangkuman sebelum UTS
Linked List
Linked List adalah sebuah struktur data linear dimana setiap unsur merupakan objek yang berbeda. Kenapa kita lebih disarahkan untuk menggunakan linked list? Hal ini disebabkan karena array hanya dapat digunakan untuk menyimpan data linear yang sejenis. Selain itu, array juga memiliki beberapa batasan-batasan di antaranya sebagai berikut
1. Ukuran dari array terbatas. ukurannya selalu tetap karena alokasinya telah dilakukan pada saat array didefinisikan.
2. Bila penambahan dan pengurangan dilakukan secara terus menerus akan memakan banyak waktu pada saat terjadinya komputasi sehingga tidak efesien
Oleh karena itu lebih disarankan untuk menggunakan linked list.
Berikut ini kelebihan-kelebihan dari linked list:
- Memiliki fleksibilitas yang tinggi
- Alokasi memori yang akan digunakan bersifat dinamis.
Macam-macam linked list adalah sebagai berikut:
1.Circular Single Linked List
Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List
tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node
terdepannya.
2.Doubly Linked List
Double linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list
3.Circular Doubly Linked List
Double 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.
STACKS AND QUEUE
Summary About Stack and Queue
1. Stack (tumpukan)
Adalah sebuah konsep penyimpanan data secara linear yang bersifat Last In First Out(LIFO) yang berarti data yang terakhir masuk adalah data yang pertama keluar.
*Ciri-ciri stack sebagai berikut :
· Elemen Top/puncak diketahui
· Penyisipan dan Penghapusan selalu dilakukan di TOP
· LIFO
*Operasi Stack yang biasa digunakan diantaranya yaitu :
· Push
Untuk memasukkan atau menginputkan data
· Pop
Untuk mengapus data top
· isFull
Untuk mengetahui jika tumpukan sudah penuh
· isEmpty
Untuk mengetahui tumpukan yang kosong
· Clear
Untuk menghapus seluruh data
2. Queue(Antrian)
Adalah salah satu contoh konsep aplikasi dari pembuatan double linked list yang sering ditemui dalam kehidupan sehari-hari. Queue merupakan struktur data yang bersifat FIFO(First in First out) yang artinya, data yang pertama kali masuk merupakan data yang akan keluar paling awal.
*Dalam kehidupan sehari-hari, ada banyak sekali tentang Queue atau antrian. Contohnya adalah sebagai berikut :
· Saat seseorang mengantri di sebuah Bank
· Antrian Loket pembelian sebuah tiket Pesawat, Kereta Api, dan lainnya
· Pembayaran Tol dan sebagainya.
*Operasi Queue yang biasa digunakan diantaranya yaitu :
· EnQueue
Untuk memasukkan data kedalam Antrian
· DeQueue
Untuk mengeluarkan data kedalam Antrian.
· IsFull
Untuk memeriksa apakah antrian Penuh
· IsEmpety
Untuk memeriksa apakah antrian Kosong
· Clear
Untuk menghapus seluruh Antrian.
HASHING TABLE AND BINARY TREE
Summary about Hashing Table and Binary Tree
Adalah sebuah pohon dalam sebuah struktur data yang bersifat hirarkis (berhubungan satu dengan yang lain). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan.
Binary tree memiliki syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul) yang disebut kiri dan kanan.
Binary Search Tree
Adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap anaka 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. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.
Aturan Binary Search Tree :
-Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
-Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Kenapa harus membedakan kiri dan kanan sesuai nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturannya, proses search akan lebih cepat.
Insert node pada BST:
Memasukan data pada Binary Search Tree ketentuan umumnya adalah inputan yang mempunyai nilai kecil diletakan pada sebelah kiri root / node, dan sebaliknya. (inputan pertama otomatis menjadi root).
Delete node pada BST:
Terdapat 3 kemungkinan yang ada saat ingin menghapus node :
1) Node to be deleted is leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
Hash Table
Adalah sebuah struktur data yang berfungsi untuk menyimpan keys/value. Hash table ini menggunakan function hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari.
HashingHash Function
Adalah sebuah function yang dapat digunakan untuk memetakan kumpulan data dari ukuran yang bebas menjadi kumpulan data dengan ukuran tetap.
Untuk mendapatkan mekanik hashing yang baik. Penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:
- Dapat dihitung secara efisien
- Distribusi secara seragam
- Menghindari tabrakan yang terjadi antar elemen
Apakah Hash Table diimplementasikan pada Blockchain?
Menurut saya tidak, blockchain juga merupakan struktur data tetapi tujuannya sangat berbeda dari hash table.
Dalam blockchain, setiap node jaringan menyimpan data lengkap. Jadi sama sekali bukan ide yang sama dengan hash table di mana data dibagi di antara node. Setiap entri baru dalam blockchain harus divalidasi oleh proses yang disebut penambangan.
Hash table bertujuan untuk menyediakan struktur yang efisien untuk membagi data pada jaringan sedangkan blockchain bertujuan untuk menyediakan struktur data yang tahan-rusak.
Binary tree
Tidak seperti Array, Linked List, Stack dan antrian, yang merupakan struktur data linier, pohon adalah struktur data hierarkis.
Binary Tree adalah struktur data pohon di mana setiap simpul memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Ini diimplementasikan terutama menggunakan Links.
Node Pohon Biner berisi bagian-bagian berikut.
1.Data
2.Pointer ke anak kiri
3.Pointer ke kanan anak
geeksforgeeks.org
Tree adalah struktur data hierarkis. Kegunaan utama tree termasuk mempertahankan data hierarkis, menyediakan akses cukup dan menyisipkan / menghapus operasi. Binary tree adalah kasus khusus pohon di mana setiap simpul memiliki paling banyak dua anak.
BINARY SEARCH TREE
Summary about Binay Search Tree
Adalah sebuah pohon dalam sebuah struktur data yang bersifat hirarkis (berhubungan satu dengan yang lain). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan.
Binary tree memiliki syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul) yang disebut kiri dan kanan.
Binary Search Tree
Adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap anaka 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. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.
Aturan Binary Search Tree :
-Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
-Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Kenapa harus membedakan kiri dan kanan sesuai nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturannya, proses search akan lebih cepat.
Insert node pada BST:
Memasukan data pada Binary Search Tree ketentuan umumnya adalah inputan yang mempunyai nilai kecil diletakan pada sebelah kiri root / node, dan sebaliknya. (inputan pertama otomatis menjadi root).
Delete node pada BST:
Terdapat 3 kemungkinan yang ada saat ingin menghapus node :
1) Node to be deleted is leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
Comments
Post a Comment