Linked List
Linked List memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.
Linked list digunakan dalam banyak algoritma untuk memecahkan masalah real-time, ketika jumlah elemen yang akan disimpan tidak dapat diprediksi dan juga selama akses berurutan elemen.
Kegunaan linked list adalah untuk menunjuk pointer ke alamat lain, terdapat head dan tail.
Tipe linked list:
- Single Linked List
- Double Linked List
Perbedaan Linked List dengan Array:
Array:
- Koleksi linear element data.
- Menyimpan value pada lokasi memory.
- Bisa random mengakses data.
Linked List:
- Koleksi linear node.
- Tidak menyimpan node di lokasi memory.
- Hanya dapat diakses secara berurutan.
Contoh Single Linked List:
Insert
node->next = head;
head=next;
Delete
//if x on head
if(head->value==x){
head = head->next;
free(curr);
}
//if x not on head, find the location
else{
while(curr->next->value!=x)curr=curr->next;
sruct tnode *del = curr->next;
curr->nex = del->next;
free(del);
}
Jenis Linked List:
1. Circular Single Linked List. Node terakhir kembali ke node awal. Tidak menyimpan value null.
2. Doubly Linked List. Linked list 2 arah. Ada prev dan next.
3. Circular Doubly Linked List. Mirip circular single linked list tapi total pointer tiap node ada 2 pointer.
GSLC 10 Maret 2020
Hashing
Hashing adalah teknik utuk menyimpan dan mengambil key dengan cara cepat.
String character diubah menjadi value lebih pendek atau key yang menunjukkan string aslinya.
Hashing digunakan untuk index dan mengambil item di database karena lebih cepat mencari item menggunakan hashed key lebih pendek daripada menggunakan value aslinya.
Hashing dapat dikatakan sebagai konsep yang mendistribusikan key dalam array disebut hash table menggunakan fungsi yang sudah ditentukan yang disebut hash function.
Hash table adalah table array dimana kita menyimpan string asli. Index tablenya adalah hashed key, sementara valuenya adalah string asli.
Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hash key yang sama.
Ada beberapa cara untuk fungsi hash:
- Mid-square.
Mengambil value tengah untuk mempresentasikan value sebuah key.
- Division.
Membagi string menggunakan modulus dari size table tersebut.
- Folding.
Membagi 2 value tiap key lalu ditambah. Jika hasilnya ada 3, ignore angka paling depan.
- Digit Extraction.
Digit yang sudah didefinisikan adalah hash addressnya.
- Rotating Hash.
Gunakan method hash apa saja (seperti division/mid-square method). Lalu melakukan rotasi. Rotasikan angkanya agar menjadi hash address baru.
Collision adalah ketika terjadi 2 hasil address yang sama. Cara menyelesaikannya adalah:
- Linear Probing. Mencari slot kosong selanjutnya dan menaruh stringnya disana.
- Chaining. Menaruh string di slot sebagai chained list menggunakan linked list.
Tree & Binary Tree
Tree adalah struktur data non-linear yang menunjukkan hubungan hirarki terhadap data object.
Root = Node paling atas.
Edge = Garis yang menyambung Parent ke Child.
Leaf = Node yang tidak mempunyai anak.
Sibling = Node yang mempunyai parent sama.
Degree = Total sub tree di node.
Height/Depth = Tinggi maksimal node di sebuah tree.
Binary tree adalah tree yang memiliki akar yang nodenya paling banyak punya 2 anak, kiri dan kanan.
Tipe-tipe Binary Tree:
- Perfect Binary Tree = Binary tree yang tiap levelnya memiliki depth sama.
- Complete Binary Tree = Binary tree yang tiap level, hampir semuanya terisi.
- Skewed Binary Tree = Binary tree yang tiap node hanya memiliki 1 anak
- Balanced Binary Tree = Binary tree yang leafnya tidak jauh dari root.
Comments
Post a Comment