Semester 2 Review / Summary

Review / Summary Semester 2

1. Linked List

Circular Single Linked List

    Circular linked list adalah variasi dari linked list dimana setiap node tidak memiliki ruang NULL dan diganti oleh ruang untuk menunjuk node selanjutnya dan node paling terakhir akan menunjuk node yang pertama dan seterusnya, sehingga terbentuk sebuah siklus.

Double Linked List

     Double Linked List adalah variasi dari linked list yang bisa bergerak bolak-balik dimana setiap node memiliki 3 ruang, perbedaan node pertama, node tengah dan node terakhir adalah di node pertama, di ruang pertama adalah NULL dan ruang ketiga untuk menunjuk node selanjutnya, untuk node di tengah, ruang pertama untuk menunjuk node sebelumnya dan ruang ketiga untuk menunjuk node selanjutnya, dan di node terakhir, ruang pertama untuk menunjuk node sebelumnya dan ruang ketiga adalah NULL.

Circular Doubly Linked List

     Circular Doubly Linked List adalah linked list gabungan dari circular single linked list dan double linked list, dimana setiap node bisa menunjuk node selanjutnya maupun sebelumnya dan node terakhir akan menunjuk node pertama, dan akan membentuk sebuah siklus.

Push dan Pop di Single Linked List

Push

void push(int a)

{

    curr = (struct Data*)malloc(sizeof(struct Data));

    curr->value = a;

    

    if(head==NULL){

        head = tail = curr;

    }

    else{

        curr->next = head;

        head = curr;

    }

}

Pop

void pop()

{

    curr = head;

    

    if(curr == tail){

        free(curr);

        head = tail = NULL;

    }

    else if(curr != NULL)

    {

        head = head->next;

        free(curr);

}

Push dan Pop di Double Linked List

Push

void push(int a)

{

    curr = (struct Data*)malloc(sizeof(struct Data));

    curr->value = a;

    

    if(head==NULL){

        head = tail = curr;

    }

    else{

        tail->next = curr;

        curr->prev = tail;

        tail = curr;

    }

    head->prev = tail->next = NULL;

}

Pop

void pop()

{

    curr = head;

    

    if(tail == head){

        free(curr);

        tail = head = curr = NULL;

    }

    else

    {

        while(curr->next!=tail){

            curr = curr->next;

        }

        free(tail);

        tail = curr;

        tail->next = NULL;

    }

}

Hashing Table and Binary Tree

Hashing Table

Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diinginkan. Dengan demikian, itu menjadi struktur data di mana operasi penyisipan dan pencarian sangat cepat terlepas dari ukuran data. Tabel hash menggunakan array sebagai media penyimpanan dan menggunakan teknik hash untuk menghasilkan indeks di mana elemen yang akan dimasukkan atau harus ditempatkan dari.

Hubungan Hashtable dan Blockchain

• Hash adalah fungsi yang memenuhi tuntutan terenkripsi yang diperlukan untuk menyelesaikan perhitungan blockchain
• Hash seperti solusi atau tulang punggung jaringan blockchain
• Hash memiliki panjang yang tetap dan hampir tidak mungkin untuk ditebak panjangnya jika seseorang mencoba untuk memecahkan atau mencoba masuk ke blockchain

Salah satu teknologi blockchain yang menggunakan hash adalah Bitcoin. Di dalam Bitcoin, hash berfungsi untuk menulis transaksi baru ke dalam blockchain melalui proses penambangan. Hash menjadi kebutuhan/kekuatan pemrosesan dalam jumlah besar yang bearti bitcoin baru ditambang dalam jangka waktu yang lama, tidak secara sekaligus.

Binary Tree

Binary tree adalah pohon khusus dimana disetiap node atau vertex bisa tidak memiliki cabang atau juga bisa memiliki 1 atau 2 cabang dan setiap cabang bisa bercabang lagi dan memiliki sifat yang sama. Binary tree digunakan untuk mewakili struktur data nonlinear. Pohon biner memiliki peran penting dalam software application dan salah satu hal paling penting dari Binary Tree adalah searching dalam algoritma.

Algorithm

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
   
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
    
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
} 

Semoga rangkuman ini dapat bermanfaat untuk yang membaca, mohon maaf jika ada yang kurang ataupun salah.

Terima kasih.


Raymond Andilsim
2301906533