Linked list adalah urutan data structure dimana setiap anggotanya di hubungkan oleh links
Setiap link mengandung hubungan ke link lain
Kelebihan linkedlist
1.fleksibilitas – memasukkan (atau menghapus) dari posisi mana saja dalam waktu yang konstan.
2.Alokasi memori dinamis – tidak perlu mengalokasikan memori.
Kelemahan linked list
1.menggunakan lebih banyak memori dibandingkan array karena menggunakan pointers
2.node dalam linked list harus dibaca dari berurutan dari awal karena linked list itu harus diakses berurutan
3.lebih lama untuk diakses
4.sangat sulit dilakukan ketika ingin di-reverse
Representasi linked list
1.linked list mengandung element link first
2.setiap link ada kolom data dan kolom link next
3.setiap link berhubungan dengan link selanjutnya menggunakan link next
4.link terakhir mengandung sebuah link yang NULL untuk menandai link terakhir
Jenis linked list
1.simple linked list ->cuman bisa maju
2.doubly linked list ->bisa maju dan mundur
3.circular linked list ->item terakhir ada link ke element pertama
Operasi dasar
1.insertion ->menambahkan element di awal list
2.deletion ->menghapus data di awal list
3.display ->menampilkan keseluruhan list
4.search ->mencari sebuah element dengan kunci yang diberikan
5.delete ->menghapus sebuah data dengan kunci yang diberikan
Operasi insertion
Misalnya kita ingin memasukan new node ditengah tengah node sebelah kiri dan node sebelah kanan,maka new node harus menunjuk ke node sebelah kanan.
NewNode.next −> RightNode;
Lalu node sebelah kiri menunjuk ke node yang baru
LeftNode.next −> NewNode;
Langkah langkah ini akan memasukan new node ditengah tengah node kiri dan node kanan.
-jika ingin memasukan new node di bagian depan berarti new node hanya cukup menunjuk ke node pertama dan selesai.
-jika ingin memasukan new node ke bagian paling belakang berarti node terakhir tinggal menunjuk ke new node dan new node menunjuk ke NULL.
Operasi deletion
Langkah pertama melakukan operasi deletion adalah mencari data mana yang ingin dihapus.
Misalkan node yang ditengah ingin dihapus.
Pertama node sebelah kiri ditunjuk ke node sebelah kanan.
LeftNode.next −> TargetNode.next;
lalu target node menunjuk NULL.
TargetNode.next −> NULL;
Langkah ini membuat target node tidak digunakan sama sekali.
HASH TABLE
Dalam pemograman,hash table adalah sebuah data structure yang meng-inplementasikan sebuah “associative array abstract data type”, sebuah structure yang dapat memetakan kata kunci menjadi value .hash table menggunakan fungsi hash untuk mendapatkan sebuah index yang juga disebut hash code ,ke array of buckets atau slots yang dimana value yang dicari bisa ditemukan.
Hashing adalah sebuah Teknik yang mengubah vlue value menjadi sebuah Panjang dari index of array .kita akan mengmodulokan untuk mendapatkan range of key values .anggap contoh dari hash table dengan besar 20 dan item item berkut disimpan item didalam (key,value) format.
- (1,20)
- (2,70)
- (42,80)
- (4,25)
- (12,44)
- (14,32)
- (17,11)
- (13,78)
- (37,98)
Sr.No.
|
Key
|
Hash
|
Array Index
|
1
|
1
|
1 % 20 = 1
|
1
|
2
|
2
|
2 % 20 = 2
|
2
|
3
|
42
|
42 % 20 = 2
|
2
|
4
|
4
|
4 % 20 = 4
|
4
|
5
|
12
|
12 % 20 = 12
|
12
|
6
|
14
|
14 % 20 = 14
|
14
|
7
|
17
|
17 % 20 = 17
|
17
|
8
|
13
|
13 % 20 = 13
|
13
|
9
|
37
|
37 % 20 = 17
|
17
|
Linear probing
Seperti yang kita lihat,kadang kadang hashing Teknik digunakan untuk membuat index of array yang sudah digunakan.dala kasus itu kita bisa mencari lokasi kosong sselanjutnya sampai menemukan tempat kosong .teknik ini dinamakan linear probing.
Sr.No.
|
Key
|
Hash
|
Array Index
|
After Linear Probing, Array Index
|
1
|
1
|
1 % 20 = 1
|
1
|
1
|
2
|
2
|
2 % 20 = 2
|
2
|
2
|
3
|
42
|
42 % 20 = 2
|
2
|
3
|
4
|
4
|
4 % 20 = 4
|
4
|
4
|
5
|
12
|
12 % 20 = 12
|
12
|
12
|
6
|
14
|
14 % 20 = 14
|
14
|
14
|
7
|
17
|
17 % 20 = 17
|
17
|
17
|
8
|
13
|
13 % 20 = 13
|
13
|
13
|
9
|
37
|
37 % 20 = 17
|
17
|
18
|
Secara sederhana,hashing berarti mengubah string dengan Panjang berapa pun dan mengoutputnya dengan output yang punya Panjang sama. Salah satu Cryptocurrency,bitcoin transaksi yang terjadi diambil sebagai input dan algoritma hashing berjalan(bitcoin menggunakan SHA-256) yang memberikan output dangan Panjang tetap.
Dalam pemograman ,binary tree adalah data struktur pohon dimana setiap nodenya mempunyai paling banyak dua anak atau cabang,dimana dinamakan left child dan right child. Binary tree node mempunyai bagian bagian berikut:
1. Data
2. Pointer to left child
3. Pointer to right child
Binary Search Tree
Dalam it ,binary search tree atau biasanya juga disebut ordered/sorted binary trees adalah sebuah data structure yang menyimpan item didalam memory yang disusun dalam bentuk seperti akar pohon dan setiap cabang akar memiliki paling maksimal 2 buah cabang.
Diatas adalah gambar binary tree yang benar,selain berbentuk seperti akar dan memiliki cabang paling maksimal 2,binary search tree juga memiliki syarat lain yaitu data yang lebih besar ditaruh dicabang sebelah kanan dan data yang memiliki nilai lebih kecil ditaruh di cabang sebelah kiri.cara ini memungkikan pencarian data yang lebih cepat karena data sudah diatur sedemikian rupa dan computer akan memulai pencarian daric aba terbawah sebelah kiri.
1.searching
Langkah-langkah:
1.mulai dari root.
Root merupakan bagian teratas dari binary search tree,jadi kita mempunyai 1 variabel yang akan bergerak,kita taruh variable itu di root.
2.bandingkan nilai yang dicari kepada node,jika nilai yang dicari lebih besar maka akan ke kanan jika lebih nilai yang dicari lebih kecil maka ke kiri cara ini dilakukan secara recursif.
3.jika nilai yang dicari sudah sama dengan nilai node maka return true.
2.insertion
Langkah-langkah:
1.mulai dari root
2.bandingkan ke node jika lebih besar maka ke sebelah kanan ,jika lebih kecil maka akan kekiri jika ketika pindah belum ada nilainya maka proses berhenti dan nilai nya di taruh di memory itu.
No comments:
Post a Comment