Rangkuman belajar semester 2

Linked List

          Linked List adalah struktur data yang tersusun oleh record-record data yang berurutan maupun tidak berurutan dan tiap-tiap record data tersebut memiliki field yang menyimpan alamat dari record selanjutnya atau sebelumnya. record-record data yang dihubungkan dengan link disebut juga Node. Dalam suatu Linked List memiliki 2 jenis istilah yang penting yaitu Head dan Tail. Head adalah Node pertama dalam suatu Linked List dan Tail adalah Node terakhir dalam suatu Linked List.

    Macam - Macam Linked List :

• Circular Single Linked List :
  
    Circular atau siklus memiliki arti yaitu tidak berujung. Sehingga dapat kita ketahui bahwa Circular Single Linked List adalah Single Linked List yang dimana Tail (Node Terakhir) dari Linked List tersebut menunjuk(menyimpan alamat) pada Head (Node Pertama) dari Linked Linked List tersebut.

• Double Linked List:                                                                                                                    Jika kita ketahui Single Linked List adalah Linked List dimana node-nodenya hanya    menunjuk(menyimpan alamat)  ke 1 arah (ke depan atau belakang) maka di Double Linked List ini node-node yang terdapat di linked list ini menunjuk(menyimpan alamat) pada 2 arah yaitu ke node yang berada di depan dan belakang node tersebut.                                                                 

              Contoh Coding dari Double Linked List :

              

              General :

              struct List{

                      int number;

                      struct List *Next;

                      struct List *Prev;

              };

• Circular Double Linked List:                                                                                                           Circular Double Linked List hampir sama dengan Circular Single Linked List, perbedaannya adalah pada Circular Double Linked List Head (Node Pertama) menunjuk(menyimpan alamat) pada Tail(Node Terakhir) begitu juga Tail, Tail menunjuk pada Head dalam Linked List tersebut sehingga adanya 2 pointer dan Linked List tersebut tidak memiliki ujung.

Hashing Table & Binary Tree

   Hashing adalah proses pengeluaran Output Data dari Input Data yang memiliki panjang berbeda-beda menjadi memiliki panjang yang tetap dan sama. Teknik Hashing ini sangat tidak asing di bidang Blockchain dimana kegunaan dari Hashing ini adalah seperti meengenkripsi suata data yang kita kirim, bedanya dengan enkripsi biasa adalah Hashing tidak dapat menghasilkan suatu dokumen, karena memang Hashing diciptakan untuk melihat integritas dari suatu data. Contoh yang dapat kita lihat adalah NSA(National Security Agency) milik Amerika Serikat yang mematenkan Secure Hash Algorithm yang sampai sekarang masih digunakan di Bitcoin dan lain sebagainya.

             Hashing Table adalah sebuah struktur data yang menyimpan data-data yang ada secara unik, yaitu memberi nilai-nilai index yang berbeda-beda antara 1 data dengan data lainnya. Akses menuju suatu data akan menjadi sangat cepat ketika kita mengetahui nilai index data tersebut. Hashing Table sangatlah cepat tidak peduli seberapa besar data yang ada karena Hashing Table menggunakan teknik Hashing sehingga panjang dari Input maupun Output Data akan selalu sama.

Contoh :

Penyimpanan data:

struct DataItem {
   int data;
   int key;
};

Deklarasi Fungsi Hash:

int hashCode(int key){
   return key % SIZE;
}

Fungsi Searching:

struct DataItem *search(int key) {
     int hashIndex = hashCode(key);
 
      while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
   
       ++hashIndex;
  
      hashIndex %= SIZE;
   }

   return NULL;        
}

Fungsi Insert:

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   hashArray[hashIndex] = item;        
}

Fungsi Delete :

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
 
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
   
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
  
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }  
 
   return NULL;        
}

             Binary Tree (Pohon Biner) adalah sebuah pohon di struktur data yang bersifat hirarkis(one to many). Binary Tree dapat juga disebut kumpulan simpul yang memiliki maksimal 2 anak simpul di tiap simpulnya. 

Binary Search Tree

               Binary Search Tree (BST) adalah sebuah struktur data yang dibuat agar pencarian(searching), pengurutan(sorting), pemasukkan(insertion) dan penghapusan(deleteion) dapat dilakukan lebih cepat dan juga lebih mudah. Binary Search Tree juga seringkali disebut sorted version of Binary Tree atau dapat kita artikan sebagai Binary Tree yang diurutkan. Binary Search Tree biasanya dibuat dengan skema sebagai berikut :  

• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih kecil dibanding nilai yang ada di node atasnya diletakkan di node sebelah kiri
• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih besar dibanding nilai yang ada di node atasnya diletakkan di node sebelah kanan
• *diasumsikan nilai dari node-node berbeda-beda

Operasi-operasi pada Binary Search Tree 

• Searching: Pencarian suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                          berikut:    1. Mulai dari node teratas atau root  

                                             2. Cek apakah node teratas atau root adalah nilai yang dicari(jika iya,                                                         maka program telah selesai, jika tidak lanjutkan ke langkah 3)

                                             3. JIka nilai yang dicari lebih kecil dibanding node atasnya atau root

                                                 maka lakukan pencarian secara recursive ke kiri dan sebaliknya jika

                                                 jIka nilai yang dicari lebih besar dibanding node atasnya atau root 

                                                 maka lakukan pencarian ke kanan secara recursive

• Insertion: Memasukkan suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                     berikut:       1. Mulai dari node teratas atau root  

                                              2. Jika nilai yang ingin dimasukkan lebih kecil dibanding node atasnya                                                      atau root masukkan angka ke subtree sebelah kiri dari root dan

                                                  sebaliknya jika nilai yang ingin dimasukkan lebih besar dibanding

                                                  node atasnya atau root  masukkan angka ke subtree sebelah kanan dari

                                                  root

                                               3. Ulangi sampai nilai yang ingin dimasukkan menemukan tempat

                                                   kosong untuk dapat nilai tersebut tempati

• Deletion: Menghapus suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                         berikut:        1. Cek node-node yang ada, jika node yang ingin dihapus idak                                                         memiliki subtree atau anak, hapus langsung node tersebut.
                                       2. Jika node yang ingin dihapus memiliki 1 subtree atau anak, hapus                                                langsung node tersebut, lalu sambungkan subtree atau anak node                                                   tersebut dengan node di atasnya atau parent. 

                                                3. Jika node yang ingin dihapus memiliki 2 subtree atau anak, cari anak

                                                    dari node tersebut yang menempati posisi di paling kanan subtree

                                                    bagian kiri lalu tempatkan anak tersebut di node yang ingin dihapus,

                                                    lalu hapus posisi anak tersebut secara recursive.