RANGKUMAN DATA STRUCTURE
Pointer adalah tipe data yang valuenya menunjuk ke value lain yang tersimpan pada memory computer menggunakan addresnya.
Dalam menggunakan pointer wajib menggunakan operator & dan *.
Array merupakan koleksi data yang memiliki element yang sama/homogenous. element array disimpan menggunakan index, index mulai dari angka 0.
Structure/ Struct adalah user defined data yang dapat menyimpan informasi yang berhubungan walaupun berbeda tipe data. sedangkan array hanya dapat menyimpan entities yang memiliki element /tipe data yang sama.
contoh:
pointer : int *ptr;
array: int arr[5];
struct:
Struct data{
int age;
char nama[100]
};

linked list: kumpulan data dimana element bisa ditambah atau dihapus darimanapun.
Single linked list :
untuk membuat linked list sebelumnya harus define node structure untuk list.
untuk menambah value, kita harus allocate node baru , assign value ke node baru kemudian sambungkan dengan linked list yang sudah ada. 
untuk menghapus value kita harus mencari lokasi node yang ingin dihapus, hapus kemudian sambungkan kembali linked list yang sudah ada.

Circular Linked list :
node terakhir = pointer untuk node pertama, dalam ciricular linked list tidak terdapat value null. circular doubly linked list memiliki perbedaan pada node memiliki 2 pointer.

Doubly Linked list merupakan linked list yang memiliki 2 pointer yaitu pointer head dan pointer tail.
declare double linked list:
struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};

struct tnode *head = NULL;
struct tnode *tail = NULL;

Header linked list merupakan tipe linked list spesial yang mengandung header node di awal list, dalam header linked list header tidak menunjuk pada node pertama teteapi berisi address dari header node.

Stack adalah kumpulan data yang memiliki urutan dan membentuk tumpukan. pada stack kita dapat menambah atau mengurangkan data dari data yang paling atas. stack dapat diimplementasikan menggunakan array ataupun linked list dan menggunakan konsep first in last out yang artinya data yang dimasukkan pertama akan dikeluarkan terakhir atau data yang terakhir ditambahkan yang pertama dikeluarkan. untuk memasukkan data ke dalam stack menggunakan operasi push, sedangkan untuk mengeluarkan data menggunakan operasi pop.

Queue merupakan kumpulan data yang memiliki urutan dan membentuk seperti antrian. queue menggunakan konsep first in first out yang artinya data yang dimasukkan pertama akan dikeluarkan pertama juga dan data yang dimasukkan terakhir akan dikeluarkan terakhir juga. terdapat 2 operasi dalam queue yaitu enqueue untuk memasukkan data dan dequeue untuk menghapus data.

terdapat beberapa perbedaan antara stack dan queue. Pertama stack menggunakan konsep first in last out sedangkan queue menggunakan konsep first in first out. stack merupakan kumpulan data yang membentuk tumpukan sedangkan queue membentuk antrian.

Hashing merupakan teknik untuk menyimpan data,mencari,menambahkan data pada array dengan cepat ,supaya cepat teknik hashing mengubah string menjadi value index tetap yang lebih pendek karena lebih mudah dan cepat untuk mencari data dengan value yang lebih kecil dibandingkan value originalnya.

Hash table adalah struktur data yang menyimpan data dengan cara yang assosiative, data disimpan dengan format array,dimana setiap value data memiliki index/value unique tersendiri. dengan adanya index unique tersendiri pengaksesan data lebih cepat apabila kita mengetahui value tersebut.

Hash function adalah method untuk menbentuk fungsi hash:
1. Mid-Square
2. Division
3. Folding
4. Digit extraction
5. Rotating hash
hash function yang paling sering digunakan yaitu metode division.
pada metode division pertama kita menghitung jumlah lokasi memori yang tersedia kemudian dibagi dengan value asli data , dan mengambil sisa hasil bagi sebagai nilai hash.

Terdapat kekurangan pada hash table yaitu kemungkinan terjadinya collision atau data yang bertubrukan, untuk mengatasi collision terdapat 2 cara yaitu :
1. Linear probing, menempatkan string disebelah/setelah tempat terjadinya collision
2. Chaining, menempatkan string pada lokasi collision menggunakan linked list.

Binary tree adalah struktur data berbentuk pohon dimana setiap node memiliki paling banyak 2 anak node (left node,right node). 


Beberapa tipe binary tree:
1. Perfect binary tree , binary tree yang setiap levelnya memiliki kedalaman yang sama
2. Complete binary tree, setiap node kecuali leaf memiliki 2 node anak
3. Skewed binary tree, binary tree yang hanya memiliki 1 node anak kecuali leaf
4. Balanced binary tree,binary tree in dimana the left and right anak node memiliki perbedaan tinggi tidak lebih dari 1.

Binary search tree adalah binary tree yang menggunakan node dan memiliki beberapa properti yaitu:

  1. Node anak kiri berisikan angka lebih kecil dari node induk
  2. Node anak kanan berisikan angka lebih besar dari node induk
  3. Node kanan dan kiri juga harus merupakan binary search tree
  4. tidak boleh ada node yang duplicate /sama
Operasi pada binary search tree:

  1. find(); mencari sebuah angka/data pada binary search tree
  2. insert(): memasukkan angka/data baru pada binary search tree
  3. remove():menghapus angka/data baru pada binary search tree


Comments

Post a Comment

Popular posts from this blog

RANGKUMAN AVL TREE DAN B-TREE AVL TREE Avl tree is a subtype of binary tree, avl tree has the property of self balancing in addition to all the properties exhibited from binary search tree. Properties: 1. Each tree has a root node (at the top). 2. The root node has zero, one or two child nodes. 3. Each child node has zero, one or two child nodes, and so on. 4. Each node has up to two children. 5. For each node, its left descendants are less than the current node, which is less than the right descendants. 6. The difference between the depth of right and left subtrees cannot be more than one. Avl tree will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee. AVL TREE INSERTION When inserting into avl tree we insert using the same as binary search tree then we use left or right rotation to balance the tree. 1. If there is an imbalance in left child of right subtree, then you perform a left-rig...
Read more
Binary search tree adalah binary tree yang menggunakan node dan memiliki beberapa properti yaitu: Node anak kiri berisikan angka lebih kecil dari node induk Node anak kanan berisikan angka lebih besar dari node induk Node kanan dan kiri juga harus merupakan binary search tree tidak boleh ada node yang duplicate /sama Operasi pada binary search tree: find(); mencari sebuah angka/data pada binary search tree insert(): memasukkan angka/data baru pada binary search tree remove():menghapus angka/data baru pada binary search tree Searching: untuk melakukan searching pertama kita mengcompare nodenya , apabila angka/data yang dicari ada pada node maka kita akan return node, apabila angka yang ingin dicari lebih besar makan kita akan mengcompare node anak kanan sedangkan apabila lebih kecil kita akan mengcompare anak node kiri. struct node* search(struct node* root, int key) {     if (root == NULL || root->key == key)        return root; ...
Read more