Final Summary

by : Philips

Linked List

Hello, fellow programmers!

I'm sure most of you must've heard about Array before, don't you?

Well today we'll be talking about something similar but slightly different, it's called Linked List.

What is 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).

There are two kinds of Linked List, they are called Single Linked List and Double Linked List. As the name suggests, Single Linked List is linked list that contains only the 'address/key' of the box after it, while Double Linked List contains both before and after.

Meaning, if you accidentally missed the box you're looking for in Single Linked List, you can't go back and you must start over again. 

Example of Double Linked List:

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

  };

  struct tnode *head = 0;

  struct tnode *tail = 0;

There's also a variation of linked-list called Circular Linked List, but all there's to it is that the tail
here will point to the head, while in normal linked list it will result in NULL.

How to use Linked List?

In linked list, you cannot access the data directly with index as in array. You must make use of a method called malloc() [Memory Allocation] and some asterisks(*) [pointer].

Why Linked List?

There is two major advantages that Linked List possess compared to Array.
First one being Linked-list is dynamic and flexible in size, unlike Array whose size are to be defined and fixed, therefore Linked-list can utilize memory more efficiently than array.
Finally, it all comes down to how efficient it is when it comes to modify records in Linked list. Unlike array where you have to loop an array of [n] for n times, all you have to do is a few row of codes. 

Here's the example of insertion and deletion of record in double linked-list

1. Supposedly you were to add a data at the first index(head)

struct tnode *node =(struct tnode*) malloc(sizeof(struct tnode));

  node->value = x;

  node->next  = head;

  node->prev  = NULL;

  head->prev  = node;

  head = node;

2. Supposedly you were to delete a data at neither head nor tail

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);     ---------Free is a method used to 'delete'/free up the memory used

 Imagine performing those two operations on array, how long would it be?

That's it for the introduction to Linked List, hope you learned something !

Linked List 2 : Single Linked List

Hello Guys, back with me again. After the opening of last week, I would like to tell you guys about the commonly used "module?" used in Linked List. Alright, lets get to it XD

--First of all there is to main method we will use in the code which is
Malloc -> sort of like reserve a certain memory space to be used
Free -> release the memory space that you reserved
Sizeof -> see the size of an object/variable

--In linked list, we normally use module such as Print, Pop-deletion & Push-insertion. Look at following code. Note that we always initiate current with Malloc at the beginning of the module. That serves as a container for the new value to be inserted to the record.

 To be noted here in Pop function also, we should always free up the memory space if we no longer uses the memory to prevent the record from bulking in size.

That's it for today, stay tuned for more!

Hashing Table & Binary Tree

Halo, halo.. Hari ini saya akan menjelaskan sesuatu yang lebih advanced nih ke kalian, namanya adalah Hashing Table dan Binary Tree. Jadi, mereka tuh adalah suatu metode pengelompokkan data untuk mempercepat proses searching. Bayangin, nih. . Udahlah kita semakin percepat proses searching data dari segi algoritma, kita nambahin lagi dari segi penyimpanannya, proses pengolahan data pasti makin cepat dong. Jadi, bedanya mereka apa :?

Hash Table

Apa sih yang dimaksud dengan Hash Table? Jadi Hash Table, itu suatu metode pengolompokan data dimana data data yang relevan dikelompokkan dalam sesuatu yang namanya Hash. Untuk apa? Hashing Table itu bakal mengelompokkan data-data yang relevan itu ke dalam suatu kelompok jadi gampang pas searching. Mereka tuh mirip kaya kamus, dimana kata dengan awalan yg sama dikelompokin ke section yg sama. Nah, gmana cara kelompokannya? 

Nah, tahukah teman-teman kalau Hashing sendiri, kerap diterapkan didalam dunia blockchain loh. Berikut contoh implementasinya:

-alamat pada blockchain diturunkan dari hashing, contoh alamat BitCoin SHA-256 dan RIPEMD 160.

-penggunaan hash membantu menyimpan data dalam jumlah besar. Datanya dilabelin dengan waktu dan dapat di-hash lebih lanjut pada masa depan, sehingga membuat storage data permanen lebih ekonomis.

-hash pada transaksi mempermudah untuk men-track transaksi pada blockchain.

Binary Tree

Berbeda dengan Hashing, pengelompokaan data pada binary tree adalah dengan permainan nilai batas atas dan atas bawah. Jadi, sebuah node dipecah dengan dua anaknya dan yg lebih kecil disimpan di sbelah kiri, dan yg gede sebelah kanan

Searching in BST

Halo semuanya, pada postingan sebelumnya saya suda menjelaskan sekilas mengenai konsep Binary Tree. Pada postingan kali ini saya ingin menjelaskan soal searching pada Binary Tree.

Searching disini menggunakan teknik rekursif ya man teman. Algoritmanya cukup sederhana, jadi apabila root (ibaratnya current) ketemu sama key (kata kunci) yang ingin kita cari, maka return root, or else geser. Itu saja sih man teman, makasi yaa.

struct node* search(struct node* root, int key)

{

    // Base Cases: if the root is null or key is present at root

    if (root == NULL || root->key == key)

       return root;

     

    // If key is greater than root's key

    if (root->key < key)

       return search(root->right, key);

  

    // If key is smaller than root's key

    return search(root->left, key);

}

AVL

Introduction

Hello there, in the previous post I've talked about Binary Search Tree before. Some of you might've encountered a situation where when you input the first data with extreme value (too big or too small), the following leaves/nodes just get overweight at one side, probably looking like this.

100

/ 

50   

/  \   

45  60     

/             

30                

Actually, there's nothing wrong with it. But since one invented an innovation towards this, here we are, a self-balancing binary tree : AVL tree. Technically speaking, AVL tree is an self-balancing binary tree in which the difference of depth between left and right subtree cannot be more than one.

How does it work

So basically, everytime when we input a data, we check on the balance between the right and left sub trees, and perform rotation accordingly to realign [rebalance] them.

There are four kinds of unbalanced tree that happens in a binary tree :
- Left left tree = [rotate right]

- Left right tree = [rotate right]

- Right right tree = [rotate left]

- Right left tree = [rotate left]

All situation on above will then get resolved in AVL by a few left/right rotation.

Like this :

What to code

To keep this short, I'll just mention a few core function that make up the balancing feature of AVL.

First, of all : imagine we have a data packed in struct named node , you should know that it is compulsory for every node to have an attribute that represents their height in the tree. Le'ts pretend the Node holds an numeric value named value

 node=leftRotate(node);

Struct * leftRotate(Struct *node){

  Struct *rightNode = node->right;

  Struct *rightLeftNode = rightNode->left;

  rightNode->left = node;  

  node->right = rightLeftNode;  

//Note : since we reshuffled the node, we should rewrite the height attribute that implies their       sequence

    node -> height = (node->left->height - node->right->height) +1;

//Note : apply above function to either leftNode or  rightNode too [for this case (LeftRotate), leftNode (which was rightLeftNode before) doesn't have to be re-written because it's height value is the same as before]. 

//Note : if they don't have child node anymore, should just return 0 for child's height.

  

  return rightNode;

}

I do think that the implementation for rotateRight and the code for the condition to use rotation isnt quite hard. So i'll leave it for y'all to think. See you soon ;D

Heap

Hello everyone, so today we're going to talk about something called Heap. So according to wikipedia, heap is a specialized-data structure that satisfies the heap property. It is also said that it implements the concept of priority queue in data structure.

Pretty confusing, eh.

To make things easier to comprehend, I came up with my own definition of heap if you dont mind. To me, heap is like a compilation of sorted array that is unifies in the end as root node. Here is an illustration of heap:

(max-heap)

Based on my explanation, I see that heap as 5 array of data :

1. array of [100,19,17,2]

2. array of [100,19,17,7]

3. array of [100,19,3]

4. array of [100,36,25]

5. array of [100,36,1]

See how it all starts with 100? That's what I meant by "they unifies in the end [it is indeed an end if you look from bottom to top]". But, there's more to it though, if you look closely, all of those arrays are sorted in descending order from the top to bottom. This is what it meant by implementation of priority queue : 

   "Each array is sorted in a certain way based on their value that we call as priority". 

In this case, every array is sorted in top-down descending order as it is max-heap

This might led you thinking: if there's max, there must be min heap. 

You're right about it. There are three kinds of heap, which is: Max-Heap, Min-Heap, and Min-Max Heap.

As you seen above, for Max-heap, the topmost node of the tree has the maximum value, and decreases gradually as it reaches the bottom. 

As for Min-heap, it is the opposite of Max-heap. The topmost node has the minimum value, and increases gradually as it reaches the bottom.

As for Min-max heap, it gets a little tricky as its an combination of both min and max heap. (Assuming that root node equals the height 1, its first gen of descendant is 2, second gen is 3, and so-on) In min-max tree: 

1.For every Odd height, it has the min-heap property [meaning it contains the minimum value and gets bigger as it progresses downward]

2. For every Even height, it has the max-heap property [meaning it contains the maximum value and gets smaller as it progress downward]

min-max heap

Insertion

Insertion in heap is the same as any binary tree, where it creates new node whenever is necessary. What differs it from normal BST, is however, after every insertion, it is followed by a Bubble-Up Operation. Bubble-Up Operation is a repositioning action that makes sure the tree still follows the 'Heap-property' after a new data is inserted.

How it works: It's an recursive method. In every iteration, the child node compares its value to its parent's value. If it's larger, or smaller [it depends on the type of heap], then perform a swap operation, and keeps on moving upward until the condition no longer meets.  

Deletion

In heap, normally it's the root node that gets deleted as it applies the concept of queue. But matters not, the following algorithm will still work. So, after a node is deleted [we call it node A], we replace node A value, with the last child node we perform insertion on. Then we perform another repositioning-operation like what we did in Insertion. However, deletion uses the exact opposite operation from Insertion, it's called Sink-Down Operation. 

How it works:  It's an recursive method. In every iteration, we (node A) compare our value, with our child node. The child that has the maximum or minimum value [again, it depends on the type of heap] get swapped with the value of the current node (node A). After that, proceed downward towards the child node that we performs the swap on and repeat until the last node.

Data Reference

https://www.google.com/url?sa=i&url=httpSource :

https://en.wikipedia.org/wiki/Heap_(data_structure)

https://stackoverflow.com/questions/14332279/delete-max-operation-in-a-min-max-heap

https://www.cs.usfca.edu/~galles/visualization/Heap.htmls%3A%2F%2Fdev.to%2Fswarup260%2Fdata-structures-algorithms-in-javascript-single-linked-list-part-1-3ghg&psig=AOvVaw2ZE3m5di1jvI95IYS7V07T&ust=1582731947459000&source=images&cd=vfe&ved=0CAMQjB1qFwoTCKCAr5KG7ecCFQAAAAAdAAAAABAY

BinusMaya powerpoint slides i and ii

https://www.geeksforgeeks.org/linked-list-vs-array/

https://www.youtube.com/watch?v=pBrz9HmjFOs