Rangkuman Pembelajaran

Linked List

               Linked list adalah sebuah struktur data yang terdiri dari sebuah tahapan dari rekaman-rekaman data yang setiap datanya itu ada sebuah bidang(field) yang mencakupi suatu referensi mengenai rekaman di tahapan selanjutnya.

               Linked list sangatlah berguna khususnya dalam menyelesaikan masalah dalam waktu nyata atau waktu sebenarnya dimana beberapa unsur yang disimpan ialah tidak terprediksi dan juga saat tahapan akses dari unsur unsur itu.

               Linked list terdiri dari 2 tipe yaitu, single dan double linked list. Single linked list biasanya ditandai dengan memiliki satu jalur hubungan dari suatu senarai(list) penunjuk ke senarai(list) lainnya. sedangkan double linked list adalah linked list struktur data yang memiliki dua link, link yang satu memiliki referensi ke data selanjutnya dan yang satunya lagi memili referensi ke sata sebelumnya.

Linked List Ilustration

              Single Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

• Single linked list terdiri dari suatu unsur utama yang disebut Head
• Single linked list juga memiliki unsur yang dinamakan dengan First
• setiap link membawa suatu field data dan field link yang disebut Next
• Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
• link terakhir membawa link yang berisi null yang menandakan akhir dari list tersebut yang biasa di sebut Tail

              Double Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya dan juga data sebelumnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

• Double linked list terdiri dari suatu unsur utama yang disebut Head
• Double linked list memiliki yang namanya First dan Last
• Setiap link membawa field data dan dua field link yang disebut dengan Next dan Prev
• Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
• Setiap link yang terhubung dengan link seblumnya menggunakan yang namannya Previous Link
• Link terakhir biasanya membawa null yang menandakan akhir dari list tersebut yang disebut dengan Tail

              Operation pada double linked terdapat operasi dasar yaitu, insert dan delete.

>>> Insert

         > Saat ingin menginsert node di belakang tail

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
 
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

         > saat memasukkan node pada posisi setelah suatu node

/* Given a node as prev_node, insert a new node after the given node */

void insertAfter(struct Node* prev_node, int new_data)

{

    /*1. check if the given prev_node is NULL */

    if (prev_node == NULL) {

        printf("the given previous node cannot be NULL");

        return;

    }

  

    /* 2. allocate new node */

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

  

    /* 3. put in the data  */

    new_node->data = new_data;

  

    /* 4. Make next of new node as next of prev_node */

    new_node->next = prev_node->next;

  

    /* 5. Make the next of prev_node as new_node */

    prev_node->next = new_node;

  

    /* 6. Make prev_node as previous of new_node */

    new_node->prev = prev_node;

  

    /* 7. Change previous of new_node's next node */

    if (new_node->next != NULL)

        new_node->next->prev = new_node;

}

>>> Delete

          >Jika node di delete pada bagian head atau yang paling awal maka

head = head->next;

free(head->prev);

head->prev = NULL;

          >Jika node di delete pada bagian tail atau yang paling akhir maka

tail = tail->prev;

free(tail->next);

tail->next = NULL;

          >Jika node di delete pada bagian yang bukan head atau yang paling awal tail atau yang paling akhir maka

struct tnode *curr = head;

while ( curr->next->value != x ) curr = curr->next;

struct tnode *a   = curr;

struct tnode *del = curr->next;

struct tnode *b   = curr->next->next;

a->next = b;

b->prev = a;

free(del);

          >Jika node yang di delete adalah node yang hanya sendiri 

free(head);

head = NULL;

tail = NULL;

Circular Linked List

               Ada juga jenis linked list circular yang mencakupi circular single linked list dan circular double linked list.

1. Circular Single Linked List

               Dalam circular single linked list, node terakhir berisikan penunjuk ke node pertama. Pada circular linked list tidak ada tempat penyempinan nilai null dalam listnya

Biasanya dapat diilustrasikan sebagai berikut

2. Circular Double Linked List

              Dalam circular double linked list, setiap node memiliki dua pointer. Salah satu pointer itu menunjuk ke node yang selanjutnya dan pointer yang lain menunjuk ke node sebelumnya. Pada circular double linked list tidak terdapat nilai null pada pemnyimpanannya maka circular double linked list ini mirip dengan circular single linked list.

Linked List (2.0)

 Pada penggunaan linked list terdapat 2 cara untuk memasukkan data atau menghapus data yang disebut dengan Push dan Pop.
Push bekerja sebagai pemasukkan data sedangkan Pop digunakan untuk menghapus data.
 Push dan Pop ini bekerja pada letak data yang sama yaitu, push depan, push belakang, pop depan dan pop belakang.
 Push dan pop ini pun bekerja pada single linked list maupun double linked list.
 Penggunaan push dan pop biasanya diikuti dengan Memory Allocation(Malloc).

PUSH(Single Linked List)
 Push adalah operasi pada linked list yang digunakan untuk memasukkan atau menambahkan node atau data. push depan biasanya memasukkan data ke yang paling depan sedangkan push belakang memasukkan data ke yang paling belakang.
>>KODING Push Depan

>>KODING Push Belakang

untuk men-Sort datanya diperlukan fungsi lagi seperti ini

POP(Single Linked List)
Pop adalah operasi pada linked list yang digunakan untuk menghapus data-data yang ada atau data yang satu. Pop depan adalah penghapusan data yang berada di depan sedangkan pop belakang adalah penghapusan data yang paling belakang.
>>KODING Pop Depan

>>KODING Pop Belakang

Sort pada pop bisa seperti ini


Ada juga fungsi 1 lagi yaitu, Display. Fungsi ini berfungsi untuk menampilkan data yang telah di sort dari push dan pop.

Hashing Table & Binary Tree

A. Hashing

• Hashing adalah suatu teknik yang digunakan untuk menyimpan dan menggunakan kembali kunci kunci dengan cara yang cepat.
• Dalam hashing, suatu string karakter dapat diubah menjadi panjang nilai yang lebih pendek atau kunci yang mewakili string yang asli.
• Hashing dapat digunakan sebagai index dan mengembaliken barang dalam bentuk database karena lebih cepat untuk mencari barang menggunakan kunci hashed dari pada mencari nilai aslinya.
• Hashing dapat juga diartikan sebagai konsep mendistribusikan kunci-kunci dalam suatu array yang disebut hash table dengan menggunakan fungsi tertentu yang disebut hash function.

>>Hash Function digunakan untuk memetakan sebuah nilai yang diberikan dengan sebuah kunci khusus untuk mempercepat akses dari isi-isinya. Efisiensi dari pemetaan tergantung pada efisiensi penggunaan efisiensi hash function.

Sebuah hash function yang bagus biasanya mencakupi, komputasi yang efisien dan secara seragam mendistribusi tiap kuncinya.

>>Hash table adalah suatu array yang menyimpan poimnter ke record yang sesuai ke nomornya. sebuah masukan ke hash table adalah NULL jika tidak ada nomor yang punya hash function yang nilainya sama dengan index masukan.

ukuran dari hash table juga biasanya sesuai dengan beberapa urutan dari besar kecilnya dari jumlah total dari string yang memungkinkan, sehingga beberapa string dapat memiliki hash key yang sama. 

B. Binary Tree

Tidak seperti array, linked list, stack dan queues, yaitu data struktur linear, trees ini lebih seperti data struktur hierarki. Sebuah binary tree adalah sebua pohon data struktur yang setiap cabangnya memiliki setidaknya 2 anak, yang di referensi sebagai anak kiri dan anakakanan. Biasanya binary tree dipakai dengan menggunakan Links.

Representasi binary tree biasanya seperti suatu pointer dari cabang bagian paling atas sebuah pohon. Jika tree tersebut kosong, maka nilai dari akarnya adalah NULL, sebuah cabang binary tree daoat berisi data, pointer dari anak kiri dan pointer dari anak kanan.

Binary tree dapat dilalui dari kiri-akar-kanan(inorder), preorder(akar-kiri-kanan) dan postorder(kiri-kanan-akar).

C. Implementation

Hashing table digunakan pada blockchain yang bersangkutan dengan proses memasukkan inpun baranng dari panjang yang merefleksi output dari barang dengan panjang yang sesuai. jika kita ambil contoh dari blockchain yang menggunakan cryptocurrencies, transaksi dari panjang yang berbagai macam, dapat melawati sebuah algoritma hashing dan semua memberikan output dengan panjang yang sesuai.

Binary Search Tree

Sebuah Binary Search Tree atau BST singkatnya adalah suatu struktur data yang mendukung cepatnya pencarian, sorting atau peanataan beruntun dan juga masukan dan penghapusan data yang mudah. BST juga dikenal sebagai bentuk yang lebih berurutan dari Binary tree.

Pada BST terdapat juga hal-hal demikian:

  > Subtree kiri  dari suatu node biasanya hanya memiliki keys yang lebih sedikit dari pada key pada nodenya

  > Subtree kanan dari suatu node biasanya memiliki keys yang lebih banyak atau lebih besar dari pada key pada nodenya.

  > Subtree kiri dan kanan,masing-masing harus berbentuk BST dan tidak boleh ada node yang sama.

BST juga memiliki fungsi seperti, find, insert dan remove.

Pada BST biasanya juga disediakan dengan urutannya diantara keys agar dapat memudahkan operasi atau fungsi pencarian seperti mencari nilai minimum dan nilai maksimum. jika tidak ada urutan tersebut maka saat mencari akan dibutuhkan untuk setiap key dicari untuk menemukan kunci yang diperlukan.

Contoh dari BST =

>>

A. Find

Dengan fungsi ini pertama akan dibandingkan key dengan akar dari nodenya, jika key nya terdapat pada akar yang sesuai maka, return akarnya. Jika key nya lebih kecil dari key akarnya, maka kita bisa pindahkan ke subtree bagian kiri. Jika tidak berhasil maka pencarian akan dilemparkan ke bagian sebelah kanan.

B. Insert

>> Dimulai dari awal akarnya

>> Kedua, nilai yang akan ditambahkan akan dibandingkan dengan bagian kiri subtree, dan jika nialinya lebih besar dari bagian kiri subtree maka dimasukkan ke bagian kanan

>> Pengulangan akan terus terjadi hingga terdapat node kosong untuk dimasukkan nilai baru secara rekursif

C. Delete

>> Jika nilainya terdapat di akhir node atau leaf, maka bisa langsung di delete nodenya.

>> Jika key atau nilainya adalah sebuah node maka delete node tersebut dan sambungkan cabang yang berhubungan dengan bagian sebelumnya.

>> Jika key atau nilainya memiliki dua nak cabang maka cari anak paling kiri dari subtree kanan atau juga anak paling kanan dari subtree kiri untuk menggantikannya dan pengulangan terjadi secara rekursif hingga hasil telah didapatkan.

Binary Search Tree

Binary Search Tree

Sebuah Binary Search Tree atau BST singkatnya adalah suatu struktur data yang mendukung cepatnya pencarian, sorting atau peanataan beruntun dan juga masukan dan penghapusan data yang mudah. BST juga dikenal sebagai bentuk yang lebih berurutan dari Binary tree.

Pada BST terdapat juga hal-hal demikian:
  > Subtree kiri  dari suatu node biasanya hanya memiliki keys yang lebih sedikit dari pada key pada nodenya
  > Subtree kanan dari suatu node biasanya memiliki keys yang lebih banyak atau lebih besar dari pada key pada nodenya.
  > Subtree kiri dan kanan,masing-masing harus berbentuk BST dan tidak boleh ada node yang sama.

BST juga memiliki fungsi seperti, find, insert dan remove.

Pada BST biasanya juga disediakan dengan urutannya diantara keys agar dapat memudahkan operasi atau fungsi pencarian seperti mencari nilai minimum dan nilai maksimum. jika tidak ada urutan tersebut maka saat mencari akan dibutuhkan untuk setiap key dicari untuk menemukan kunci yang diperlukan.

Contoh dari BST =
>>

A. Find
Dengan fungsi ini pertama akan dibandingkan key dengan akar dari nodenya, jika key nya terdapat pada akar yang sesuai maka, return akarnya. Jika key nya lebih kecil dari key akarnya, maka kita bisa pindahkan ke subtree bagian kiri. Jika tidak berhasil maka pencarian akan dilemparkan ke bagian sebelah kanan.

B. Insert
>> Dimulai dari awal akarnya
>> Kedua, nilai yang akan ditambahkan akan dibandingkan dengan bagian kiri subtree, dan jika nialinya lebih besar dari bagian kiri subtree maka dimasukkan ke bagian kanan
>> Pengulangan akan terus terjadi hingga terdapat node kosong untuk dimasukkan nilai baru secara rekursif

C. Delete
>> Jika nilainya terdapat di akhir node atau leaf, maka bisa langsung di delete nodenya.
>> Jika key atau nilainya adalah sebuah node maka delete node tersebut dan sambungkan cabang yang berhubungan dengan bagian sebelumnya.
>> Jika key atau nilainya memiliki dua nak cabang maka cari anak paling kiri dari subtree kanan atau juga anak paling kanan dari subtree kiri untuk menggantikannya dan pengulangan terjadi secara rekursif hingga hasil telah didapatkan.