Review mid semester

I. Pointer

Pointer merupakan suatu tipe data yang menyimpan suatu address. Suatu variable yang disimpan oleh compiler akan disimpan ke dalam RAM(Random Access Memory). Untuk melacak tempat penyimpanan suatu variable, maka dibentuklah address(alamat) sehingga kita dapat memanggil value dari variable tersebut. Dengan adanya pointer, kita dapat menyimpan address dari suatu variable. Pointer dilambangkan dengan lambang asterix(*). Biasa pointer yang sering dipakai adalah single pointer dan double pointer. Dapat dilihat dari contoh dibawah ini

II. Array 

Array merupakan suatu kumpulan data yang memiliki tipe data yang sama. Kita harus menginisiasi jumlah data yang akan masuk ke dalam array. Maka dari itu Array disebut sebagai static . Dia akan mereserve tempat sebanyak jumlah inisiasi dikali dengan ukuran dari tipe data tersebut. Data yang direserve berurutan. Perhatikan contoh di bawah ini

III. Linked List

Linked List sebenarnya sama dengan Array namun yang membedakan dari Array adalah Linked List ini merupakan bersifat dynamic. Jika kita ingin memasukan data, maka baru dialokasikan memorinya. Linked List memiliki beberapa keuntungan seperti :

• Hemat memori
• Bersifat dynamic
• Bisa menampung struct sehingga dapat menyimpan berbagai tipe data(walaupun array juga bisa)

Kelemahannya adalah :

• Searchingnya harus menggunakan linear search
• Tidak menggunakan index sehingga sulit mencari data yang

 Ada dua tipe Linked List

1. Single Link list
2. Double Link List

Konsep dari linked list adalah suatu memory menyimpan beberapa value dari berbagai tipe data dalam bentuk struct lalu ditambah dengan suatu pointer yang menyimpan alamat dari data berikutnya atau sebelumnya.

 1. Single Link List

Single Link List menyimpan beberapa value dan hanya menyimpan alamat data setelahnya.

 2. Double Link List

Single Link List menyimpan beberapa value dan menyimpan alamat data setelahnya dan sebelumnya.

Hash Table

hash table adalah struktur data uang didesign menggunakan sebuah function baru ayng digunakan untuk mempetakan value dengan memberikan sebuah index yang unik(key) supaya mempercepat pencarian elemen. Biasanya dalam programming, Hash table menggunakan array dalam aksesnya.

Beberapa tipe Pembuatan key

1. Middle-Square
   Mengambil key dengan cara mengambil value yang ada di tengah untuk menjadikan dia sebagai key
2. Division(Paling sering dipakai)
   menentukan key dari hasil sisa bagi angka tersebut dengan suatu angka
3. Digit Extraction
   mengambil ke dengan menentukan digit yang akan diambil.
   Contoh : (ditentukan bahwa akan mengambil digit ke 1,3,5)
   x = 12345
   maka keynya = 1,3,5
4. Rotating Hash
   mengambil key dengan menukar posisi dari suatu value
   Contoh : x = 12345
   maka keynya 54321

Praktek Dalam Pembuatan Struktur Data Dengan Konsep Hash

Dari beberapa cara pembuatan key yang sudah saya sebutkan di atas, saya akan mencontohkan menggunakan pengambilan key division. Karena menurut saya teknik division lebih mudah dan juga sudah cukup mengelompokan value yang akan diberikan.

Chaining

Data yang di store akan saya buatkan array 1 dimensi dengan max data 20. Setiap index bisa diisi dengan berbagai macam data lagi. Dapat saya simulasikan dengan foto dibawah ini (Sumber BinusMaya)

Chaining yang akan saya contohkan menggunakan single linked list(Sumber : Kodingan training Asisten Labolatorium NAR 20-1).

Mulai dengan membuat struct. Dalam kasus ini saya hanya memasukan 1 data saja.

setelah itu buat table dengan array of pointer node.

variable SIZE sudah saya dideklarasi di preprossesornya

supaya tidak error, inisiasi semua index di table dengan null

setelah itu hash key dengan membaginya dengan SIZE(teknik division)

Lalu berikut adalah cara untuk memasukan datanya. Konsep yang saya pake adalah single linked list

Penjelasan : 

Setelah memory sudah dialokasi dengan fungsi newNode, maka linked list akan di 'tempel' pada table yang ingin dipakai.

Demikian penjelasan saya mengenai hash table.

Sumber : PPT Binus maya, https://www.geeksforgeeks.org/index-mapping-or-trivial-hashing-with-negatives-allowed/ , Kodingan training Asisten Labolatorium NAR 20-1

Binary Search Tree

Binary Search Tree adalah sebuah struktur data yang menerapkan konsep 'pohon' dengan memiliki root dan subtreenya. sebuah root akan memiliki 2 subtree yaitu left and right. value di kiri subtree akan lebih kecil dari value di subtree yang ada di kanan.

Keuntungan BST

• Pencarian data lebih cepat dari pada linear seacrh (Ologn).
• Algoritma yang simple dan tidak rumit
• Data lebih terstruktur

Implementasinya dalam koding c

berikut adalah source code untuk fungsi insert data dalam bst

struct Node{

int value; 

struct Node *left, *right; 

};

struct Node{

int value; 

struct Node *left, *right; 

};

struct Node *createNode(int value){

struct Node *temp = (struct Node*)malloc(sizeof(struct Node)); 

temp->value = value; 

temp->left = NULL;

temp->right = NULL; 

return temp; 

}

struct Node *insertNode(struct Node *root , int value){

if(root == NULL){

return createNode(value); 

}

else if(root->value < value){

root->right = insertNode(root->right, value); 

}

else if(root->value > value){

root->left = insertNode(root->left, value); 

}else{

printf("Value already exists"); 

}

return root; 

}