Hashing Data Structure

Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Let a hash function H(x) maps the value  at the index x%10 in an Array. For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively. 

struct DataItem {
   int data;
   int key;
};

BlockChain technology employs Hashing Algorithms as the building blocks to create secure Blocks of data.

In a overly simplified explination, it does this by asking the following question

Given a hashed output with some criteria, can you determine what input will generate that output? i.e. What input string, when passed through a hashing function (eg. SHA256), will generate an output string that ends in …..abc276

Given the nature of hashing algorithms (i.e. hashing algorithms are one-way), we know that to answer this question is difficult, and will possibly require brute force approach, which would translate to a great deal of computing power. After trying several million different combinations of inputs, finally one input string may generate an output string like ed892349837abd2349abc276, which will finally match the criteria.

Binary Tree Data Structure

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

A Binary Tree node contains following parts.

Data

Pointer to left child

Pointer to right child

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

link list

STRUKTUR DATA - Linked List

Linked List

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ada beberapa macam Linked List, yaitu :

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

contoh :

contoh codingannya :

struct Mahasiswa{
      char nama[25];
      int usia;
      struct Mahasiswa *next;
}*head,*tail;

Double Linked List

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

contoh :

contoh codingannya :

struct Mahasiwa{
     char nama[25];
     int usia;
     struct Mahasiswa *next,*prev;
}*head,*tail;

Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

• Circular Single Linked List

• Circular Double Linked List

Multiple Linked List

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. contoh :

Linked List Vs Array

Memory Allocation

Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut. 

contoh penggunaan malloc:

int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));


contoh penggunaan free:

free(curr);

Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah node/data baru.

Insert dan Delete Node dalam Single Linked List

Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert (Push)

Contoh codingan push depan :

Contoh codingan push belakang :

Delete (Pop)

Contoh codingan pop depan :

Contoh codingan pop belakang :

Insert dan Delete Node dalam Double Linked List

Insert (push) dan delete (pop) node pada linked list dapat dilakukan pada posisi depan (head), tengah (mid) dan belakang (tail)

Insert (Push)

Contoh codingan push depan :

Contoh codingan push belakang :

Delete (Pop)

Contoh codingan pop depan :

Contoh codingan pop belakang :

Header Linked List

Selain ke-4 jenis Linked List diatas, ada juga jenis lain yaitu header linked list. Header linked list merupakan header spesial yang terdiri dari node headernya. Jadi, linked list jenis ini tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.

Priority Queue

Priority Queue mirip dengan queue biasa yang telah dijelaskan pada Array, Pointer dan Struktur Data yang dipost sebelumnya. Hanya saja queue ini di urutkan berdasarkan prioritasnya. Misalnya kita ingin membuat queue berdasarkan umur yang paling muda ke tua. Maka umur menjadi prioritas. Penyusunan node ini mungkin mirip seperti sorting.

contoh codingan priority queue :