RANGKUMAN

Disini saya mau membuat rangkuman dari materi yang telah saya buat.

Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Ada beberapa macam Linked List, yaitu  :

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

SINGLE LINKED LIST

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain.

DOUBLE LINKED LIST

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

CIRCULAR LINKED LIST

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. 

Ada 2 jenis Circular Linked List, yaitu :

1. Circular Single Linked List

2. Circular Double Linked List

MULTIPLE LINKED LIST

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

Hash Table adalah sebuah struktur data yang terdiri atas sebuah table dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap recor(baris) menjadi angka(hash) lokasi record tersebut dalam sebuah table.

     Ada beberapa fungsi hash untuk mengubah string menjadi key:

1. Mid-square
2. Division (most common)
3. Folding
4. Digit Extraction
5. Rotating Hash

     Implementasi hashing table in blockchain

     Hashing table memiliki peranan dalam menajga keamanan data atau disebut crypthographic dan hubungannya dengan blockchain adalah blockhain merupakan catatan traksaksi digital yang dihubungkan dari individu dan dihubungkan ke daftar. Sehingga blockchain sangat memerlukan hashing table untuk menjaga keamanan datanya.

     Salah satu contoh teknologi yang menggunakan blockchain adalah bitcoin. Fungsi dari hash di dalam bitcoin adalah untuk menambahkan data baru ke dalam blockchain dengan cara menambang. Sehingga hash berperan penting agar data yang sedang diproses menjadi lebih aman karena prosesnya yang lama.

      Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkir(hubungan one to many) antar elemen. Tree juga bisa disimpulkan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubung satu sama lain(subtree).

     Binary Tree merupakan tree yang memiliki hanya 2 child disetiap nodenya dan tidak boleh kurang.

    Jenis-jenis binary tree:

    

1. Perfect Binary Tree : binary tree  yang setiap level (kedalaman) nya berada di kondisi  yang sama.
2. Complete Binary Tree : suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja).
3. Skewed binary Tree :Suatu pohon biner yang setiap nodenya hanya memiliki 1 anak.
4. Balanced Binary Tree : suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.

Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Aturan main Binary Search Tree :

• Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
• Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

• PreOrder : Print data, telusur ke kiri, telusur ke kanan
• InOrder : Telusur ke kiri, print data, telusur ke kanan
• Post Order : Telusur ke kiri, telusur ke kanan, print data

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya :

#include <stdio.h>
#include <stdlib.h>

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}

TERIMA KASIH TELAH MEMBACA BLOG SAYA.....