Data Structure Summary

Data Structure Summary

Materi yang saya pelajari selama 1 semester adalah linked list,hashing,hash table,dan binary tree.

pertama linked list yaitu salah satu struktur data digunakan untuk menyimpan beberapa objek data, secara terurut.

linked mempunyai 2 elemen yaitu:

1.Head elemen adalah elemen yang terletak di posisi pertama dalam suatu linked list.

2.Tail elemen adalah elemen yang terletak di posisi terakhir dalam suatu linked list.

linked list juga memiliki Jenis-Jenis/Macam-macam yaitu

 1.single linked list(linked list tunggal)

struktur data satu node yang memiliki satu tautan atas node selanjutnya dalam sebuah list, jadi  list tersebut dinamakan sebagai list tunggal.

 2. Double Linked List(dua linked list )

Double Linked List adalah linked list yang biasanya menggunakan pointer, setiap node memiliki 3 field, yaitu 1 field pointer yang mengarah ke pointer berkutnya , 1 field menunjuk pointer sebelumnya , dan 1 field yang berisi data untuk node tersebut.

 
 3. Circular Linked List (linked list yang berputar atau mengulang)

 Circular linked list adalah linked list yang elemen tail/ekor (node terakhir) mengarah ke elemen head/kepala (node pertama). Jadi jika ada pointer menunjuk pada NULL.

kedua hashing,hashtable dan binary tree 

Hashing adalah teknik yang digunakan untuk mengubah sebuah string menjadi angka (kunci). Kumpulan karakter dalam sebuah string diubah dalam bentuk nilai/kunci yang lebih pendek yang mempresentasikan string original.Hash Table adalah table (array) untuk menyimpan string original. Indeks Hash Table merupakan kunci sedangkan nilainya merupakan string original.
 

Hash Function 
 metode hashing yang dapat gunakan dalam mengubah string menjadi kunci:

1. Mid-Square
String/Identifier dikuadratkan setelah itu mengambil beberapa angka hasil kuadrat (yang berada ditengah) untuk dijadikan sebagai hash key


2. Division
Membagi String/Identifier menggunakan operasi Modulus (% || mod). Angka yang digunakan biasany merupakan bilangan primer.

Contoh: "ABCD" akan disimpan pada lokasi 76
Perhitungannya adalah 64(1+2+3+4) mod 97


3. Folding 
Partisi String/Identifier menjadi beberapa bagian, kemudian menjumlahkan bagian tersebut membentuk sebuah hash key


4. Digit Extraction
Mengambil beberapa bagian dari String/Identifier dan menjadikanny sebagai hash key
Contoh: Budi mempunyai nilai x yaitu 472659485, maka kita bisa mengambil angka genap sebagai hash key yaitu 42648

5. Rotating Hash
Gunakan metode Hashing seperti Mid-Square atau Division, kemudian membalikkan hash key dari belakang ke depan.
Contoh: Jika hash key adalah 438573976 maka rotated hash key adalah 679375834

 Collision

Collision adalah tabrakan antar hash key, dimana terdapat lebih dari 1 data yang memiliki hashkey yang sama.

Solusi apabila terjadi Collision adalah Linear Probing dan Chaining.
1. Linear Probing = Mencari tempat kosong dan mengisi string di lokasi tersebut.

2. Chaining = Membuat Linked List dan menyambungkan string di slot yang sama.

Binary Tree

Binary Tree adalah struktur data non-linear yang mempresentasikan hubungan antar data. Konsep Tree adalah kumpulan dari 1 node atau lebih.

itu adalah materi yang saya pelajari selama 1 semester ini,terimakasih. 

untuk tugas koding linknya :https://drive.google.com/open?id=1hY-wjBL-HadWiV9H3v9aP7w3gugbbNha