Summary

Hello guys, so today we'll be doing a quick summary of Linked List, Hashing, and Binary Tree :D

Linked List

If I were to associate it with things, I'll say linked list is sort of like a ton of numbered & locked box, where each box contains an item and a key to the next box. Formally speaking, Linked list is basically a collection, or a structure containing records of data, where each record contain the address or reference to the record next to it (sequencially).
As I suggested before, there's Single Linked List and Double Linked List, right? In following I'll include some basic function from the infamous Double Linked List.

#include<stdlib.h> -> Jangan lupa

struct data{
int value;
struct data *prev, *next;
}*head, *tail, *curr;

void boom(){
head->prev=tail;
tail->next=head;
}

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

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

void pushMid(int a){
curr=(struct data*)malloc(sizeof(struct data));
curr->value=a;
struct data*temp;
temp=head;

while (temp->next->value < curr->value)
temp=temp->next;

curr->next=temp->next;
temp->next->prev=curr;
curr->prev=temp;
temp->next=curr;
}

void pop(int a){
if (head->value==a){
if (head!=tail){
head=head->next;
free(curr);
head->prev=NULL;
}
else{
head=tail=NULL;
free(curr);
}
}
else if (tail->value==a){
curr=tail;
tail=tail->prev;
tail->next=head;
}
else{
curr=head;
do
curr=curr->next;
while (curr->value!=a&&curr!=head);
curr->prev->next=curr->next;
curr->next->prev=curr->prev;
}
free(curr);
boom();
}

void push(int a){
if (head==NULL)
pushHead(a);
else if (a<head->value)
pushHead(a);
else if (a>tail->value)
pushTail(a);
else
pushMid(a);
}

Stack and Queue

So guys, I wont explain in detail, but I just want you to know there's a concept called Stack and Queue okay. Like the name suggests, Stack means Last In First Out (Push tail - Pop tail), and Queue means First In Last Out (Push head - pop head)

Hashing

As explained in the other topic, hashing is all about how you allocate data in a record in a more tidy manner, therefore ease up the process of searching data (in this example, array).

int hashFunction(char text[]){

int sum = 0;

int len = strlen(text);

for(int i = 0; i< len; i++){

// printf("%c: %d\n", text[i], (int)text[i]);

sum += (int) text[i];

}

// printf("SUm : %d\n", sum);

// printf("SUm : %d\n", sum % 10);

return sum % 10;

}

void insert(char nama[], int umur){

int idx = hashFunction(nama);

strcpy(kelas[idx].nama, nama);

kelas[idx].umur = umur;

return;

}

In above code, we allocate the data based on total sum of text's ASCII number modulus by maximum limit of storage (which is 10 in above code). There is a problem however, when you try to hash the string 'ABC', the result will be the same as 'CBA' or even 'AAD' --> collision. So, there was two method introduced, which is called Linear Probing and Chaining. 

- By Linear Probing, we mean to allocate the new data to the neighbouring index, so for example if index 8 is occupied, we move to slot 9, and so on. 

- By Chaining, if a slot/address is occupied, we make a new address and occupy it while retaining the index. So if we were to search for the collided data, all we have to do is count the index with hash and then perform linear search to it, pretty neat right?

Binary Tree

Binary tree is another way of storing data where you basically store the smaller data in the left node and larger one in the right. Look at the example below!

How to insert data in Binary Tree:

struct Node{

int key;

struct Node* left;

struct Node* right;

};

struct Node * root = NULL;

struct Node* createNode(int key){

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

newNode->key = key;

newNode->left = newNode->right = NULL;

return newNode;

}

//Insert Recursive

struct Node * insert(struct Node * curr, int key){

if(!curr){

return createNode(key);

}

else if(curr->key > key){ // Ke kiri

curr->left = insert(curr->left, key);

return curr;

}

else if(curr->key < key){ // Ke kanan

curr->right = insert(curr->right, key);

return curr;

}

else{ //Kalo datanya sama

printf("Data Exist in the tree\n");

return curr;

}

}

Here's how to remove them:

struct Node * remove(struct Node *curr, int target){

if(!curr){// If there is no data yet

printf("Data %d not exist in tree\n",target);

return NULL;

}

else if(curr->key < target){ //Right

curr->right = remove(curr->right, target);

return curr;

}

else if(curr->key > target){ //Left

curr->left = remove(curr->left, target);

return curr;

}

else{ // The same/Data found

//Case 1 (If dont have any child node left)

if(curr->left == NULL && curr->right == NULL){

free(curr);

return NULL;

}

//Case 2 (If contains one child[left/right])

if(curr->left == NULL || curr->right == NULL){

struct Node *subtitue;

if(curr->left != NULL){

subtitue = curr->left;

}

else{

subtitue = curr->right;

}

free(curr);

return subtitue;

}

//Case 3 (If contains both left and right child nodes)

if(curr->left != NULL && curr->right != NULL){

// Find its substitution

struct Node *substitute;

//Predecessor

substitute = curr->left;

while(subtitue->right){

subtitue = substitue->right;

}

//Successor

substitute = curr->right;

while(substitute->left){

substitute = substitue->left;

}

curr->key = substitute->key;

// Discard the substitute below;

curr->right = remove(curr->right, substitute->key);

return curr;

}

}

}

Hope you find this summary useful!

Program Dreamers Market

//Dreamers market
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

struct item{
char value[50];
int qty;
int price;
struct item *next, *prev;
} *head, *tail, *curr;

void pushH(char a[],int b, int c){
curr=(struct item*) malloc(sizeof(struct item)); 
strcpy(curr->value,a);
curr->qty=b;
curr->price=c;
if (head==NULL){
head=tail=curr;
}
else{
curr->next=head;
head->prev=curr;
head=curr;
}
tail->next=NULL;
head->prev=NULL;
}

void pushT(char a[],int b, int c){
curr=(struct item*) malloc(sizeof(struct item));
strcpy(curr->value,a);
curr->qty=b;
curr->price=c;
if (head==NULL){
head=tail=curr;
}
else{
tail->next=curr;
curr->prev=tail;
tail=curr;
}
tail->next=NULL;
head->prev=NULL;
}

void pushM(char a[], int b, int c){
curr=(struct item*) malloc (sizeof(struct item));
strcpy(curr->value,a);
curr->qty=b;
curr->price=c;
struct item*temp;
temp=head;
while (strcmp(temp->next->value,curr->value)<0)
temp=temp->next;

curr->next=temp->next;
temp->next->prev=curr;
curr->prev=temp;
temp->next=curr;
}

void cetak(){
curr=head;
int total=0;
int i=1;
printf("\nNo - Nama (Qty) - Harga\n");
printf("=====================\n");
while (curr!=NULL){
printf("%d - %s (%d) - %-7d\n",i,curr->value,curr->qty,curr->price*curr->qty);
i++; total+=(curr->price*curr->qty);
curr=curr->next;
}
printf("\nTotal price: %d\n",total);
}

void cetak2(){
printf("It's on us, Kindness is Free :)\n");
}

void popH(){
curr=head;
if (head!=tail){
head=head->next;
free(curr);
head->prev=NULL;
}
else{
head=tail=NULL;
free(curr);
}
}

void popT(){
curr=tail;
tail=tail->prev;
free(curr);
tail->next=NULL;
}

void popM(char a[]){
curr=head;
while (curr!=NULL){
if(strcmp(curr->value,a) == 0) 
break;
else
curr=curr->next;
}
if (curr==NULL){
}
else{
curr->prev->next=curr->next;
curr->next->prev=curr->prev;
free(curr);
}
}

void pop(char a[]){
curr=(struct item*) malloc (sizeof(struct item));
strcpy(curr->value,a);

if (strcmp(head->value,curr->value)==0)
popH();
else if (strcmp(tail->value,curr->value)==0)
popT();
else
popM(a);
}


void push(char a[], int b, int c){
curr=(struct item*) malloc(sizeof(struct item));
strcpy(curr->value,a);
curr->qty=b;
curr->price=c;
if (head==NULL){
head=tail=curr;
tail->next=NULL;
head->prev=NULL;
}
else if (strcmp(curr->value,head->value)<0){
pushH(a,b,c);
}
else if (strcmp(curr->value,tail->value)>0)
pushT(a,b,c);
else
pushM(a,b,c);
}

bool search(char a[]){
curr=head; int i=0;
while (curr!=NULL){
if (strcmp(curr->value,a)==0)
break;
else
curr=curr->next;
}
if (curr==NULL){
return false;
}
return true;
}
int main(){
int pilihan=0,jml;
char nama[50],nama2[50],nama3[50];
do{
printf("     Dreamers Market\n");
printf("==========================\n");
printf("1. Add an item\n");
printf("2. Edit item\n");
printf("3. Delete item\n");
printf("4. View item\n");
printf("5. Checkout\n");
printf("Your choice : ");scanf("%d",&pilihan); 

switch(pilihan){
case 1: printf("\n   Add Item\n");
printf("==============\n");
printf("Item name : ");getchar(); scanf("%[^\n]",nama);
printf("Item qty : ");scanf("%d",&jml);
push(nama,jml,(rand() % (499000))+ 1000);
printf("Item successfully added!\n\n");
break;
case 2: printf("\n   Edit Item\n");
printf("===============\n");
printf("Item name : ");getchar(); scanf("%[^\n]",nama2);
if (search(nama2)){
printf("Current qty : %d\n",curr->qty);
printf("New qty : "); scanf("%d",&jml); getchar();
curr->qty=jml;
printf("Item updated!\n\n");
}
else
printf("Item not found!\n\n");
break;
case 3: printf("\n   Delete Item\n");
printf("=================\n");
printf("Item name : ");getchar(); scanf("%[^\n]",nama3);
if (search(nama3)){
pop(nama3);
printf("Item deleted!\n\n");
}
else
printf("Item not found!\n\n");
break;
case 4: cetak();
break;
case 5: cetak2();
break;
}
} 
while (pilihan!=5);

return 0;
}