Push Linked List

Final Review

Single Linked List

Apa itu Push?

Push adalah action memasukan suatu inputan ke dalam List, push diawali dengan membuat gerbong nya terlebih dahulu dimana gerbong ini akan diisi oleh inputan dan jumlah nya disesuai kan dengan memory alokasi yang kita butuhkan, nah setelah gerbong tersedia, baru lah kita dapat melakukan Push.

Ada berapa type Push?

Push memiliki 3 type : Depan, Belakang, dan Tengah.

Push depan adalah Push dimana inputan dimasukan tepat di depan head, setelah inputan diletakan di depan head, inputan tersebut disambungkan dengan inputan belakang nya dan menjadi head yang baru.

Push belakang adalah Push dimana inputan dimasukan tepat di belakang tail, setelah inputan diletakan di belakang tail, inputan tersebut disambungkan dengan inputan didepan nya dan menjadi tail yang baru.

Push tengah adalah Push dimana inputan dimasukan diantara posisi head dan tail, untuk mengetahui dengan pasti posisi inputan maka dilakukan proses sorting terlebih dahulu, dimana inputan dibandingkan dengan value yang berada di head terlebih dahulu, sampai ditemukan angka yang lebih besar dari inputan, baru lah inputan dimasukan tepat di depan angka yang lebih besar dari diri nya dan dibelakang angka yang lebih kecil dari nya.

Hash Table and Binary Search Tree

Hash table is a structure data which consist of table and function aiming to map unique key value from each record to hash, the record location is located within the table.

Hash Operation consist of :

Insert : Insert a value into the table
Find : Search a value in the table
Remove : Delete a value in the table
GetIterator : Return Iterator which check all value one by one.

The hash table uses an associative array data structure that associates a record with a unique key field in the form of a number (Hash) which is a representation of that record. For example, there is data in the form of a string to be stored in a hash table. The string is represented in a key field K.

The way to get this key field varies greatly, but the end result is a hash number that is used to determine the location of a record. This hash number is entered into the hash function and produces a record location index in the table.
             k (x) = key field generator function (1)
             h (x) = hash function (2)

Question : Does Blockchain technology employ hash table?

The answer is Yes as explained by the picture below, hash function connect the keys with the bucket.

Binary Search Tree

Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Binary Search Tree Example :

Double Linked List (DLL)

Double Linked List is simliar to Single Linked List, the different is that instead of one pointer, Double Linked List as the name suggested possess 2 pointer instead of one, where the other point can point backward too in addition to pointing forward to the next value.

Double Linked List code example :

/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};

Advantage over Single Linked List :

Advantages over singly linked list
1. A DLL can be traversed in both forward and backward direction.
2. The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3, We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

*Hash Table

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data. 

Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

*Hashing

Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

Single Linked List

Apa itu Push?

Push adalah action memasukan suatu inputan ke dalam List, push diawali dengan membuat gerbong nya terlebih dahulu dimana gerbong ini akan diisi oleh inputan dan jumlah nya disesuai kan dengan memory alokasi yang kita butuhkan, nah setelah gerbong tersedia, baru lah kita dapat melakukan Push.

Ada berapa type Push?

Push memiliki 3 type : Depan, Belakang, dan Tengah.

Push depan adalah Push dimana inputan dimasukan tepat di depan head, setelah inputan diletakan di depan head, inputan tersebut disambungkan dengan inputan belakang nya dan menjadi head yang baru.

Push belakang adalah Push dimana inputan dimasukan tepat di belakang tail, setelah inputan diletakan di belakang tail, inputan tersebut disambungkan dengan inputan didepan nya dan menjadi tail yang baru.

Push tengah adalah Push dimana inputan dimasukan diantara posisi head dan tail, untuk mengetahui dengan pasti posisi inputan maka dilakukan proses sorting terlebih dahulu, dimana inputan dibandingkan dengan value yang berada di head terlebih dahulu, sampai ditemukan angka yang lebih besar dari inputan, baru lah inputan dimasukan tepat di depan angka yang lebih besar dari diri nya dan dibelakang angka yang lebih kecil dari nya.

Double Linked List (DLL)

Double Linked List is simliar to Single Linked List, the different is that instead of one pointer, Double Linked List as the name suggested possess 2 pointer instead of one, where the other point can point backward too in addition to pointing forward to the next value.

Double Linked List code example :

/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};

Advantage over Single Linked List :

Advantages over singly linked list
1. A DLL can be traversed in both forward and backward direction.
2. The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3, We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Hash Table and Binary Search Tree

Hash table is a structure data which consist of table and function aiming to map unique key value from each record to hash, the record location is located within the table.

Hash Operation consist of :

Insert : Insert a value into the table
Find : Search a value in the table
Remove : Delete a value in the table
GetIterator : Return Iterator which check all value one by one.

The hash table uses an associative array data structure that associates a record with a unique key field in the form of a number (Hash) which is a representation of that record. For example, there is data in the form of a string to be stored in a hash table. The string is represented in a key field K.

The way to get this key field varies greatly, but the end result is a hash number that is used to determine the location of a record. This hash number is entered into the hash function and produces a record location index in the table.
             k (x) = key field generator function (1)
             h (x) = hash function (2)

Question : Does Blockchain technology employ hash table?

The answer is Yes as explained by the picture below, hash function connect the keys with the bucket.

Binary Search Tree

Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Binary Search Tree Example :

Tugas codingan:

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//create struct

struct item

{

char itemName[100];

int itemQ;

struct item *next;

struct item *prev;

}*head, *tail, *curr;

void input(char itemName[100], int itemQ)

{

//pesan memory

struct item *curr = (struct item*)malloc(sizeof(struct item));

//inisialisasi

strcpy(curr->itemName, itemName);

curr->itemQ = itemQ;

curr->next = NULL;

curr->prev = NULL;

//check if head is empty;

if(head==NULL)

{

head = tail = curr;

}

//insert head

else if(strcmp(head->itemName, itemName) >0)

{

curr->next = head;

head->prev = curr;

head = curr;

}

//insert tail

else if(strcmp(tail->itemName, itemName)<0)

{

tail->next = curr;

curr->prev = tail;

tail = curr;

}

//insert di tgh"

else

{

struct item *temp = head;

while(temp->next!=NULL && strcmp(curr->itemName, itemName)>0)

{

temp = temp->next;

}

curr->next = temp->next;

curr->prev = temp;

temp->next = curr;

curr->next->prev = curr;

}

}

void printAll()

{

curr = head;

printf("Nama Barang Jumlah");

printf("\n");

while(curr!=NULL)

{

printf("%s  %d\n",curr->itemName, curr->itemQ);

curr=curr->next;

}

}

void pop(char *hapus)

{

curr = head;

//tidak ada link list

if(head==NULL)

{

printf("Tidak ada Linked List!\n");

}

//pophead

else if(head!=NULL && strcmp(curr->itemName, hapus)==0)

{

head = head->next;

free(curr);

}

else

{

struct item *temp = curr;

while(curr!=NULL && strcmp(curr->itemName, hapus)!=0)

{

temp = curr;

curr = curr->next;

}

if(curr==tail)

{

tail = temp;

}

else

{

curr->next->prev = temp;

}

temp->next=curr->next;

free(curr);

}

}

void update(char *key, int Q)

{

curr = head;

if(head==NULL)

{

printf("Tidak ada linked list!\n");

}

while(curr!=NULL)

{

if(strcmp(curr->itemName, key)==0)

{

curr->itemQ = Q;

}

if(curr->next!=NULL)

{

curr = curr->next;

}

else

{

return;

}

}

printf("Data does not exist in the list\n");

}

int main(int argc, char** argv) {

int choice;

char itemName[100];

int itemQ;

do{

printAll();

printf("1.Input barang untuk dibeli\n");

printf("2.Update jumlah barang\n");

printf("3.Delete barang\n");

printf("4.Check Out\n");

do{

printf("Masukan Inputan[1..4] : ");

scanf("%d",&choice);getchar();

}while(choice<1 || choice>4);

if(choice==1)

{

printf("Masukan nama item : ");

scanf("%s",&itemName);getchar();

printf("\n");

printf("Masukan Quantity nya : ");

scanf("%d", &itemQ);getchar();

printf("\n");

input(itemName, itemQ);

}

else if(choice==2)

{

printf("Masukan nama item yang ingin diupdate: ");

scanf("%s", &itemName);getchar();

printf("\n");

printf("Masukan Quantity baru nya :");

scanf("%d", &itemQ);getchar();

printf("\n");

update(itemName, itemQ);

}

else if(choice==3)

{

printf("Masukan nama item yang ingin dihapus : ");

scanf("%s", &itemName);getchar();

printf("\n");

pop(itemName);

}

else

{

printf("\n");

printf("Terima kasih sudah datang mengunjungi toko kami!\n");

return 0;

}

}while(choice!=4);

return 0;

}

AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Contoh AVL tree :

Insertion : Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Single rotation : Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti gambar dibawah T1,T2, dan T3 adalah subtree yang urutan nya harus seperti demikian serta height nya harus sama (>0)

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3.

Pada kedua rotation ini dikenal juga istilah left left(LL), right right(RR), right left(RL), left right(LR)..

Deletion : Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus → root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.