Circular single linked list:
Node terakhir mengandung pointer ke node awal
Double linked list:
Two way Linked list data struct dengan 2 hubungan.1 menunjuk tentang data berikutnya.yang lainnya menunjuk data sebelumnya
Cth: if (head) = null;{
node -> value = x
node -> next = null;
node -> prev = null;
head = node;
tail = node;
}
else{
node -> value = x;
node -> next = null;
node ->prev = tall;
tail -> next = node;
tail = node;
}
//Free in Node
while(head){
head = head -> next;
free ( head -> prev);
head -> prev = null;
Linked List II Double Pointer
Linked list adalah struktur data abstrak yang terdiri dari kumpulan node (atau elemen). Daftar node diakses dengan cara akses sekuensial - mereka diakses dalam urutan yang dipesan / ditentukan sebelumnya.
Linked List menggunakan Double Pointer
Ketika kami melewatkan pointer sebagai parameter dalam suatu fungsi dan ingin memperbarui dalam pointer yang sama, kami menggunakan double pointer. Di sisi lain jika kita melewatkan pointer sebagai parameter dalam suatu fungsi dan menangkapnya dalam single pointer maka kita harus mengembalikan hasilnya ke fungsi panggil kembali untuk menggunakan hasilnya.
Double Pointer (Pointer ke Pointer) di C. Pointer digunakan untuk menyimpan alamat variabel. Jadi, ketika kita mendefinisikan sebuah pointer ke pointer, pointer pertama digunakan untuk menyimpan alamat dari pointer kedua. Dengan demikian dikenal sebagai pointer ganda.
Perty(Stack And Queue)
Queue = Ngantri, yang masuk duluan keluar duluan
Stack = yang jalan duluan yang paling akhir keluar
• Array punya kelemahan yaitu kalau kita book 9 tempat kita cuma bisa tempatin 9 tempat itu aja.
• But, kalau pake linked list kita bisa booking kapanpun kita mau atau misalnya 1 orang mau booking tempat dimana saja dan kapan saja itu bisa terjadi.
• Karena dunia ini gabisa diprediksi mungkin aja dalam suatu masalah tempat ada orang yang bertambah dan kurang tempat.Di saat ini lah, kita menggunakan Linked List.
Stack Operation
1. Push (x) = menambah data, yaitu data paling atas
2. Pop (x) = menghilangkan data yang paling atas
3. Top (x) = mengambil data paling atas
Contoh Stack
Pertama masuk terakhir keluar
Terakhir masuk pertama keluar
4*10 OPD OPR OPD
Infix * 4 10 OPR OPD OPD
Cosfix 4 10 * OPD OPD OPR
Contoh:
((1 + 3) / ( 100 * 5 ) ^ 30)
Prefix
/ + 1 3 ^ * 100 5 30
Postfix
30 100 5 * ^ 1 3 + /
Infix
1 + 3 / 100 * 5 ^ 30
Depth First search -> Stack
Breadth First search -> Queue
Queue Operation
Push
Pop
Front
Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa.
Dalam hashing, kunci besar dikonversi menjadi kunci kecil dengan menggunakan fungsi hash.
Nilai-nilai ini kemudian disimpan dalam struktur data yang disebut tabel hash.
Tabel hash adalah struktur data acak yang mendukung operasi INSERT, DELETE, dan FIND dalam waktu O (1) yang diharapkan.
Ide inti di balik tabel hash adalah menggunakan fungsi hash yang memetakan ruang tombol yang besar ke domain indeks array yang lebih kecil, dan kemudian menggunakan operasi array konstan-waktu untuk menyimpan dan mengambil data.
Hash Function
Hash Function adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.
Untuk mencapai mekanisme hashing yang baik, penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:
Easy to compute: Seharusnya mudah dikomputasi dan tidak harus menjadi algoritma itu sendiri.
Uniform distribution: Ini harus menyediakan distribusi seragam di seluruh tabel hash dan tidak boleh menghasilkan pengelompokan.
Less Colission: Tabrakan terjadi ketika pasangan elemen dipetakan ke nilai hash yang sama. Ini harus dihindari.
Apakah blockchain memerlukan hash table?
A hash table menggunakan fungsi hash untuk menghitung indeks ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan. tetapi block chain adalah buku besar digital di mana transaksi yang dilakukan dalam bitcoin atau mata uang digital lain dicatat secara kronologis dan terbuka.
Binary Search Tree
Di Binary Search Tree, nilai semua node di sub-pohon kiri kurang dari nilai root.
Demikian pula, nilai semua node di sub-pohon kanan lebih besar atau sama dengan nilai root.
Aturan ini akan diterapkan secara rekursif ke semua sub-pohon kiri dan kanan root.
A Binary Search Tree ditunjukkan pada gambar di atas. Sebagai kendala yang diterapkan pada BST, kita dapat melihat bahwa simpul root 30 tidak mengandung nilai lebih besar atau sama dengan 30 di sub-pohon kirinya dan juga tidak mengandung nilai kurang dari 30 di sub kanannya -pohon.
Keuntungan menggunakan Binary Search Tree
Pencarian menjadi sangat efisien dalam Binary Search Tree karena, kami mendapatkan petunjuk di setiap langkah, tentang sub-pohon mana yang mengandung elemen yang diinginkan.
Binary Search Tree dianggap sebagai struktur data yang efisien dibandingkan dengan array dan daftar tertaut. Dalam proses pencarian, ia menghapus setengah sub-pohon di setiap langkah. Mencari elemen dalam Binary Search Tree membutuhkan waktu (log2n). Dalam kasus terburuk, waktu yang dibutuhkan untuk mencari elemen adalah 0 (n).
Ini juga mempercepat operasi penyisipan dan penghapusan dibandingkan dengan yang ada di array dan daftar tertaut.
Q. Buat pohon pencarian biner menggunakan elemen data berikut.
43, 10, 79, 90, 12, 54, 11, 9, 50
Masukkan 43 ke dalam pohon sebagai akar pohon.
Baca elemen berikutnya, jika lebih rendah dari elemen root node, masukkan sebagai root dari sub-tree kiri.
Kalau tidak, masukkan sebagai akar kanan sub-pohon kanan.
Operasi pada Binary Search Tree
Ada banyak operasi yang dapat dilakukan pada Binary Search Tree.
1 Mencari di BST = Mencari lokasi beberapa elemen tertentu dalam pohon pencarian biner.
2 Penyisipan dalam BST = Menambahkan elemen baru ke pohon pencarian biner di lokasi yang sesuai sehingga properti BST tidak melanggar.
3 Penghapusan dalam BST = Menghapus beberapa node tertentu dari pohon pencarian biner. Namun, bisa ada berbagai kasus dalam penghapusan tergantung pada jumlah anak, simpul miliki.
No comments:
Post a Comment