Summary Data Structure

Linked list

Linked list adalah sebuah data structure yang menyimpan data secara berantai, contohnya seperti gerbong kereta, dimana gerbong baru dapat disambung di ujung kereta

Linked list dapat dibagi menjadi 4, yaitu:
1. Singly Linked List
2. Circular Singly Linked List
3. Doubly Linked List
4. Circular Doubly Linked List

masing - masing memiliki karakteristik yang mirip namun memiliki fungsi yang berbeda.

1. Singly Linked List

    adalah tipe linked list yang hanya menyambung secara satu arah ke node lainnya,
dapat di insert/delete dari depan dan belakang, namun hanya menyambung ke arah belakang.

2. Doubly Linked List

    adalah tipe linked linked list yang menyambung secara dua arah (ke depan & ke belakang), sehingga dapat menutupi kekurangan yang dimiliki oleh Singly Linked List dengan sedikit tambahan biaya memori.

3. Circular Singly Linked List

    adalah tipe Single Linked List yang node terakhirnya (tail) tersambung dengan node pertama (head) secara satu arah. sehingga memiliki kegunaan yang cukup berbeda dengan Single Linked List

4. Circular Doubly Linked List

    adalah tipe Doubly Linked List yang node terakhirnya (tail) menyambung secara dua arah dengan node pertama (head).

    kelebihan menggunakan linked list adalah linked list dapat dialokasikan secara dinamis dan data pada n dapat mengetahui data selanjutnya ataupun sebelumnya (Doubly Linked List).
dan kita juga dapat memasukan data di depan, belakang, ataupun tengah. sama halnya dengan menghapus data dalam Linked List.

Stack, Queue & Priority Queue

    Setelah mempelajari Linked List, ada beberapa Data Structure yang menerapkan sebagian konsep dari Linked List, yakni Stack, Queue, Priority Queue. nah kali ini kita akan membahas apa yang dimaksud dari ketiga Data Structure tersebut.

1. Stack

    Stack adalah suatu tumpukan atau koleksi objek yang menggunakan prinsip Last In First Out (LIFO), yang berarti data yang terakhir kali dimasukkan kedalam Stack akan menjadi data pertama kali keluar dari Stack tersebut. contoh kegunaannya adalah Stack Pointer / Frame Pointer dalam komputer.

2. Queue

    Queue adalah suatu koleksi / antrian objek yg menerapkan prinsip Last In Last Out, yang artinya data yang terakhir dimasukan kedalam Queue akan menjadi data yang terakhir keluar. contoh kegunaan Queue adalah pada CPU Scheduling / Disk Scheduling dimana beberapa proses berjalan secara asynchronous dan dibutuhkan sebuah algoritma untuk men-sinkronisasi transfer data, dimana beberapa algoritma CPU Scheduling mengimplementasikan Queue.

3. Priority Queue

    Priority Queue sama seperti Queue namun data yang dimasukan lebih dulu disortir (valuenya dipertimbangkan) sehingga data yang paling bermakna valuenya akan keluar paling awal. contoh kegunaannya adalah dalam algoritma Dijkstra & A* (A Star) dimana Queuenya harus terurut berdasarkan distance / heuristic.

    Demikian beberapa Data Structure diatas, cukup mirip dengan Linked List bukan? namun stack memiliki implementasi yang cukup berbeda, yakni dengan menggunakan array. sedangkan untuk Queue & Priority Queue dapat menggunakan konsep Linked List sebagai basis implementasinya.

Hash Table & Binary Tree

Hash Table

1. Definisi Hash Table
    Hash Table adalah struktur data yang memetakan kata kunci (hash) kepada sebuah elemen dalam table. Sehingga elemen yang dicari langsung berada pada kata kunci lokasi penyimpanannya. Namun pada kenyataannya sering ditemukan kondisi dimana kata kunci dua elemen atau lebih dapat bertabrakan (Collision).

2. Operasi - Operasi Dalam Hash Table
    Berikut adalah beberapa operasi yang dapat dilakukan dalam suatu hash table:

1. Insert
    Memasukan elemen ke dalam sebuah hash table
2. Lookup
    Mencari elemen dengan kata kunci
3. Remove
    Membuang elemen dengan kata kunci

3. Metode Hashing
    Berikut adalah beberapa cara untuk membuat key / hash dari sebuah kata kunci:

1. Lose Lose Algorithm
    Adalah suatu metode hashing yang sangat simple, yakni dengan menjumlahkan tiap byte dalam kata kunci. misal; "abc" = 294, dimana 'a' = 97, 'b' = 98, 'c' = 99. Metode tersebut bukanlah cara yang baik, karena Collision dapat dengan mudah terjadi.

2. FNV-1
   Fowler-Noll-Vo adalah metode hashing yang diciptakan oleh Glenn Fowler, Landon Curt Noll, dan Kiem-Phong Vo. Metode ini menggunakan Prime dan Basis dari FNV1. berikut adalah contoh pengaplikasiannya.

3. FNV-1a

    FNV-1a adalah variasi dari FNV-1 yakni dengan men-XOR kan byte_of_data terlebih dahulu baru dikalikan dengan FNV Prime.

4. Peran Dalam Blockchain

    Hash table memiliki peran penting dalam blockchain. blockchain menggunakan Distributed Hash Table. Distributed Hash Table (DHT) merupakan bentuk distribusi data Hash ke dalam jaringan peer to peer. yang mana di dalamnya memuat penyimpanan data, pencarian data, dengan penyimpanan berupa Key & Value Pair.

Binary Tree

1. Definisi Binary Tree

    Binary Tree adalah sebuah struktur data yang menyerupai sebuah Tree dan memiliki maksimal dua cabang pada tiap anaknya, yang biasa disebut anak kiri dan anak kanan. 

2. Operasi - Operasi Dalam Binary Tree

1. Insert

    Memasukan data kedalam Binary Tree, data yang dimasukan harus mengikuti aturan dalam Binary Tree yakni:

- tidak ada data yang bernilai sama.

- jika nilai data lebih kecil dari parent, maka data masuk ke anak kiri

- jika nilai data lebih besar dari parent, maka data masuk ke anak kanan

2. Delete

    Membuang data dalam Binary Tree, jika data yang dibuang memiliki anak, maka harus dilakukan salah satu dari dua cara untuk menyambungkan kembali anak tersebut, yakni dengan metode Predecessor atau metode Successor.

3. Print Semua Data

    Untuk mengeprint semua data ada tiga metode yang dapat dilakukan:

- Post-Order

- Pre-Order

- In-Order

Binary Search Tree Implementation

Contoh implementasi Binary Search Tree:

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

struct Node
{
int value;
Node *left, *right;
};

Node *root;

Node *createNode(int value)
{
Node* node = (Node*)malloc(sizeof(Node));
node->value = value;
node->left = node->right = NULL;
return node;
}

Node *insert(Node *root, int value)
{
if (!root)
return createNode(value);

if (root->value > value)
root->left = insert(root->left, value);
else if (root->value < value)
root->right = insert(root->right, value);

return root;
}

Node* remove(Node *root, int value)
{
if (!root)
return root;

if (root->value > value)
root->left = remove(root->left, value);
else if (root->value < value)
root->right = remove(root->right, value);
else if (root->value == value)
{
if (root->left == NULL || root->right == NULL)
{
Node *node = root->left != NULL ? root->left : root->right;

if (node)
*root = *node;
else
free(node);
}
else
{
Node* node = root->left;
while (node->right)
node = node->right;
root->left = remove(root->left, node->value);
}
}

return root;
}

void printPreOrder(Node *root) {
if (root) {
printf("%d ", root->value);
printPreOrder(root->left);
printPreOrder(root->right);
}
}

void printInOrder(Node *root) {
if (root) {
printInOrder(root->left);
printf("%d ", root->value);
printInOrder(root->right);
}
}

void printPostOrder(Node *root) {
if (root) {
printPostOrder(root->left);
printPostOrder(root->right);
printf("%d ", root->value);
}
}

int main() {
root = insert(root, 4);
root = insert(root, 5);
root = insert(root, 3);
root = remove(root, 3);

printPreOrder(root);
printInOrder(root);
printPostOrder(root);
}