Selasa, 10 Maret 2020

Data Structure GSLC March 10th, 2020

Hashing and Hash Tables, Trees, & Binary Tree

1. Hashing and Hash Tables

Jadi, Hashing adalah metode untuk menyimpan dan mengambil kembali data dengan cepat karena dalam hashing, data yang disimpan diberikan kode (selanjutnya disebut key) yang lebih pendek dari data tersebut. Key tersebut bisa didapatkan dengan beberapa metode yang nanti akan dibahas selanjutnya pada laman ini. Nah, hashing ini digunakan karena akan lebih gampang untuk mengakses database saat ingin mencari data ketika kita menggunakan key dibandingkan nilai data yang asli. Hash table adalah array yang menyimpan key sebagai index dan value sebagai data asli. Hash function adalah fungsi yang mengubah data awal (string), menjadi key. Berikut adalah beberapa hash function yang umumnya dipakai:

A. Mid-Square

Jika datanya dalam bentuk string maka kita harus mengubahnya dahulu menjadi angka.
Berikut adalah langkah-langkahnya:
  • pangkat 2 kan nilai dari key.
  • Kemudian, ambil r bits tengah dari hasil pangkat 2 tadi.
Contohnya:
  Data      squared value     middle part
  3121         9740641              406
  3122         9746884              468
  3123         9753129              531

Dari hasil tersebut dapatlah key yang akan kita pakai

B. Division

Metode ini sering dipakai untuk menghash data berupa integer.
      Function: h(z) = z mod M
                          z  = key
                         M = the value using to divide the key, usually using a prime number
                                 the table size or the size of memory used.
contohnya: M=97 maka,
“COBB” would be stored at the location
  ( 64+3 + 64+15 + 64+2 + 64+2) % 97 = 88
“HIKE” would be stored at the location
  ( 64+8 + 64+9 + 64+11 + 64+5) % 97 = 2
“PPQQ” would be stored at the location
  ( 64+16 + 64+16 + 64+17 + 64+17) % 97 = 35
“ABCD” would be stored at the location
              ( 64+1 + 64+2 + 64+3 + 64+4) % 97 = 76 

C. Folding

Cara untuk metode ini cukup mudah, hanya dengan membagi key menjadi beberapa bagian (terserah) yang terdiri dari beberapa digit (terserah). Kemudian, bagian-bagian tersebut dijumlahkan hingga hash yang didapat muat dalam jangkauan hash table tersebut. 
Contohnya: hash tablenya ada 100 lokasi, keynya kita akan bagi ke beberapa bagian yang terdiri dari 2 digit.

    Key                           6789                     321                    34567
    Parts                     67 and 89            32 and 1           34, 56, and 7
    Sum                           156                       33                        97
    Hash value                 56                        33                        97
                            (ignore last carry)

D. Digit Extraction

Hash addressnya ditentukan oleh digit tertentu. Contohnya:
If we extract the 1st, 3rd, and 5th digit, we will get a hash code of : 158.

E. Rotating Hash

Hash key value dengan metode Mid-square atau Division, kemudian hasilnya di putar (rotasikan).
Contohnya:
– Given hash address = 20021
– Rotation result: 12002 (fold the digits)

F. Collision

Ketika kita menyimpan data, kemudian terjadi penindihan data maka ada 2 hal yang bisa kita lakukan yaitu, Linear probing dan Chaining.
Linear probing dilakukan dalam array. Lokasi alternatif bagi data yang memiliki key yang sama adalah menempatkannya di lokasi kosong terdekat.
Chaining adalah cara menggunakan linked list untuk menghubungkan data yang sudah ada terebih dahulu pada key tersebut dengan data yang baru yang memiliki key yang sama.

2. Tree & Binary Tree

Tree adalah Data Structure non-linear yang menunjukkan tingkat dari tiap data.

Contohnya pada gambar disamping, bisa kita lihat bahwa ada hubungan hierarki/ tingkatan antara tiap data dalam konteks ini, node.

Data yang berada di tingkatan yang paling atas(level 0), adalah akar. Sedangkan semua
sub-node yang bercabang dari sebuah node disebut child. Jumlah cabang dari sebuah node disebut degree. Jumlah degree maksimal sebuah node dalam tree disebut depth.
Binary Tree adalah tree yang tiap nodenya paling banyak memiliki 2 child. Node yang tidak memiliki child disebut leaf. Contohnya pada gambar disamping.










Binary Tree memiliki beberapa tipe, antara lain:
1. Perfect Binary tree. Binary tree yang tiap tingkatannya memiliki depth yang sama.
2. Complete Binary tree. Binary tree yang tiap levelnya terisi lengkap (2 node), namun pada level terakhir hanya ada child kiri dan child kanan tidak ada.
3. Skewed Binary tree. Binary tree yang tiap nodenya memiliki paling banyak 1 child.
























Diposting oleh di Tidak ada komentar:

Selasa, 03 Maret 2020

Data structure March 3rd, 2020

Linked list

1. Insert

Untuk menambahkan node pada sebuah linked list, terdapat 3 cara yang bisa dilakukan, yaitu:

A. Push Head

Pada metode yang ini seperti namanya, kita akan menambahkan node baru yang akan menjadi head yang baru. Contoh source codenya seperti berikut:

void pushHead(int number){
curr = (struct data*) malloc (sizeof(struct data));
curr->value = number;
if(head == NULL){
tail = head = curr;
tail->next = NULL;
}
else{
curr->next = head;
head = curr;
}
}

pada potongan code tersebut, kita bisa melihat bahwa fungsi tersebut bisa dibagi menjadi 3 fase.
Pertama fase pemesanan memori: curr = (struct data*) malloc (sizeof(struct data));
kedua, fase pengisian nilai/value: curr->value = number;
ketiga, fase koneksi:  if(head == NULL){
                tail = head = curr;
                tail->next = NULL;
                        }
                        else{
                     curr->next = head;
                     head = curr;
                              }

Pada fase ketiga kita harus membagi ketika head belum ada ,dan ketika head sudah ada.
Jika head sudah ada, maka alamat next dari curr yang telah kita buat harus kita hubungkan dengan head terlebih dahulu kemudian merubah posisi head ke posisi curr.

B. Push Tail

Pada cara yang ini, kita akan menambahkan node baru setelah tail, kemudian memindahkan tail yang lama ke node yang baru saja dihubungkan agar menjadi tail yang baru. Contoh source codenya seperti berikut:

void pushTail(int number){
curr = (struct data*) malloc(sizeof(struct data));
curr->value = number;
if(tail == NULL){
tail = head = curr;
tail->next = NULL;
}
else{
tail->next=curr;
tail=curr;
tail->next=NULL;
}
}

Pada potongan code ini, cara kerjanya mirip seperti cara kerja fingsi pushHead namun perbedaannya terdapat pada bagian:
else{
tail->next=curr;
tail=curr;
tail->next=NULL;
}
Dimana ketika node baru telah dibuat, maka tail yang lama akan dihubungkan dengan node yang baru dibuat, kemudian memindahkan tail ke node tersebut dan tidak lupa untuk meng-assign NULL sebagai alamat next dari tail agar kita bisa tahu bahwa itu adalah ujung dari linked list tersebut.

C. Push Middle

Untuk cara push yang ini, cara kerjanya agak sedikit berbeda dari 2 cara push sebelumnya.
kita harus meng-validasi posisi dari node yang akan ditambah tersebut. Contohnya, kita akan membuat suatu linked list yang terurut secara ascending(asumsi linked listnya telah jadi dan sudah terurut) kemudian kita akan menambahkan suatu node yang nilainya berada di bagian tengah list tersebut. Maka kita akan membuat fungsinya seperti berikut,

void pushMiddle(int number){
curr = (struct data*) malloc(sizeof(struct data));
curr->value = number;
if(head == NULL){
head = tail = curr;
tail->next = NULL;
}
else if(number < head->value){
curr->next = head;
head = curr;
}
else if(number >= tail->value){
tail->next = curr;
tail = curr;
tail->next = NULL;
}
else{
struct data *tmp = head;
while(number >= tmp->next->value){
tmp = tmp->next;
}
curr->next = tmp->next;
tmp->next = curr; 
}
}

Pada tiap tahap validasi yang ada pada potongan kode tersebut menentukan posisi dari node yang baru. Contohnya pada bagian else yang paling terakhir, adalah tahap dimana nilai dalam node diketahui bukan yang terkecil maupun yang terbesar sehingga kita harus melooping untuk mencari posisi node tersebut.

2. Delete

Untuk menghapus sebuah node dari sebuah linked list kita harus menggunakan salah satu dari 3 cara yaitu: 
a. Pop depan: menghapus head lalu menjadikan node setelah head, menjadi head yang baru.
b. Pop belakang: menghapus tail lalu menjadikan node sebelum tail, menjadi tail yang baru.
c. Pop tengah: menghapus node yang berada di tengah.

Logika codingan untuk pop ini sangat mirip dengan push namun alih-alih kita memesan suatu blok memori, kita membebaskan memori tersebut dan memutuskan hubungan memori tersebut dengan list yang kita miliki. Kita membebaskan memori tersebut dengan syntax "free(apa yg mau di free);".
Contohnya potongan kode berikut yang merupakan fungsi yang menghapus head/pop depan:

void popHead(struct Data **head, struct Data **tail)
{
if (*head == NULL)
printf ("No Data to Delete!\n");
else if (*head == *tail)
{
free(*head);
*head = *tail = NULL;
}
else
{
struct Data *curr = *head;
*head = (*head)->next;
free(curr);
}
}

Pada potongan program diatas, digunakan passing by reference sehingga variable yang digunakan merupakan double pointer(**).





Diposting oleh di Tidak ada komentar:

Selasa, 25 Februari 2020

Data Structure GSLC February 25th, 2020

LINKED LIST


   Linked list adalah sebuah data structure, suatu cara untuk mengalokasikan data. Pada array, kita menyimpan atau mereservasi beberapa memori yang saling bersebelahan untuk digunakan sebagai penyimpanan data. Namun, array memiliki kelemahan yang cukup mengganggu pada beberapa kasus. Contohnya, ketika kita membuat array yang akan menampung data berupa angka tapi kita tidak tahu seberapa banyak data yang akan disimpan. Biasanya, hal ini kita selesaikan dengan membuat ukuran array yang sangat besar. Namun, pada kenyataannya tidak semua kasus ketika kita menyimpan jumlah data sebesar ukuran array yang kita deklarasikan. Hal inilah yang membuat linked list sangat berguna. Tidak seperti array, linked list tidak harus megalokasikan data pada memori yang bersebelahan namun, dihubungkan oleh sebuah pointer dan dijadikan seperti list. Linked list biasa, juga sering disebut single linked list atau singly linked list. Pada linked list, elemen pertama atau node(sebutan yang diberikan oleh para programmer) pertama biasanya disebut sebagai head dan node terakhir disebut tail. Tiap elemen dihubungkan dengan pointer yang biasa dinamakan next. Semua node, dari head hingga tail dihubungkan dengan pointer next yang menunjuk alamat node berikut setelah node tersebut dan pointer yang menunjuk node setelah tail menunjuk ke NULL atau bisa dibilang tidak menunjuk ke apa-apa. Kelemahan dari single linked list ini adalah kita tidak bisa langsung membuka data yang kita inginkan karena informasi yang kita pegang hanyalah alamat dari head dan alamat node yang ditunjuk oleh node sebelumnya. Kelemahan single linked list lainnya adalah informasi alamat node yang kita tahu hanyalah alamat node yang sedang kita lihat dan alamat node berikutnya yang ditunjukkan pointer pada node saat ini. Contohnya, jika kita memiliki linked list: head->nodeA->nodeB->tail->NULL dan posisi kita sekarang ada pada nodeB, maka kita hanya bisa mengakses nodeB hingga tail.

1. Circular Single Linked List

   Circular single linked list memiliki cara kerja yang sama persis seperti single linked list namun kita bisa lebih bebas dalam mengakses data. Jika pada single linked list akhir dari list tersebut dimana node terakhir atau tail memiliki pointer yang menunjuk ke NULL, maka pada circular single linked list pointer pada tail bukan menunjuk NULL, akan tetapi menunjuk alamat head. Pada circular single linked list juga, posisi dari head dan tail lebih fleksibel karena list tersebut terus terhubung dan tidak berujung sehingga patokan tersebut tidak diperlukan.

2. Doubly Linked List

   Doubly linked list adalah linked list yang memungkinkan kita mengakses data pada node sebelumnya. Pada single linked list kita tidak bisa mengakses data pada node sebelumnya dan pada circular single linked list kita bisa mengakses data pada node sebelumnya hanya jika kita melakukan looping sehingga dibutuhkan waktu yang lebih lama untuk mengakses data pada node sebelum node yang sedang kita lihat. Bagaimana caranya sehingga doubly linked list ini bisa mengakses data sebelumnya? caranya adalah dengan menambahkan satu lagi pointer yang disebut prev(previous).
Jika pointer next menunjuk alamat node berikutnya, maka prev menunjuk node sebelumnya. pointer prev pada node pertama atau head menunjuk pada NULL.

3. Circular Doubly Linked List

  Circular doubly linked list adalah doubly linked list yang pointer prev pada head menunjuk alamat tail dan pointer next pada tail menunjuk alamat head sehingga linked list tersebut saling terhubung.

Untuk source code dan penjelasan lebih lanjut ketiga linked list diatas bisa dilihat pada youtube:
a. Circular Doubly Linked List: https://youtu.be/zmoLA97B85Y
b. Circular Single Linked List: https://youtu.be/BFYLS0uPnJk
c. Doubly Linked List: https://youtu.be/elZQCUWSpbM







Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)