Summary + Coding

LINKED LIST

     Linked List atau Senarai Berantai adalah data berbentuk urutan di mana setiap record data memiliki referensi ke data berikutnya. Elemen data yang dihubungkan dengan link pada linked list disebut Node. Dalam Linked List, terdapat istilah head dan tail. Head merupakan elemen yang berada pada posisi pertama. Tail merupakan elemen yang berada pada posisi terakhir.

A. SINGLE LINKED LIST

     Single Linked List hanya memiliki satu pointer saja. Pointer tersebut menunjuk ke node selanjutnya, dan field pada tail menunjuk ke NULL.

Contoh :

Contoh Coding :
struct Siswa{
  char Nama[30];
  int Umur;
  struct Siswa *next;
}*head, *tail;



B. DOUBLE LINKED LIST

     Double Linked List memiliki dua pointer, yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Pada Double Linked List, setiap head dan tailnya menunjuk ke NULL.

Contoh :

Contoh Coding :
struct Siswa{
  char Nama[30];
  int Umur;
  struct Siswa *next, *prev;
}*head, *tail;



C. CIRCULAR LINKED LIST

     Pada Circular Linked List, tail menunjuk ke head, sehingga tidak ada pointer yang menunjuk ke NULL. Ada dua jenis Circular Linked List, yaitu :

1. Circular Single Linked List




2. Circular Double Linked List

STACK AND QUEUE

A. Stack

     Stack atau tumpukan adalah sebuah data struktur penting di mana setiap elemennya memiliki urutan tertentu. Dapat juga diartikan sebagai kumpulan data yang seolah terlihat membentuk suatu tumpukan atau seperti ada data yang diletakkan di atas data lainnya.

     Stack dapat dianalogikan seperti ketika kita memiliki setumpuk piring di mana setiap piring diletakkan di atas piring lainnya atau ditumpuk ke atas. Ketika ingin mengeluarkan sebuah piring dari tumpukan tersebut, yang pertama kali diambil adalah piring yang paling atas. Oleh karena itu, kita hanya bisa menambahkan dan mengurangi piring pada satu posisi, yaitu posisi yang paling atas.

     Stack merupakan sebuah data struktur linear yang dapat diimplementasikan menggunakan array atau linked list. Elemen-elemen yang ditumpuk hanya bisa ditambah atau dikurangi dari ujungnya, yaitu yang paling atas (top). Maka, kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out. Artinya, data yang terakhir kali dimasukkan atau disimpan adalah data yang pertama kali akan diakses atau dikeluarkan.

                                       

     Operasi-operasi dalam stack :

1. Push : memasukkan atau menyimpan sebuah data ke dalam stack.

2. Pop : mengeluarkan atau menghapus data terakhir (yang berada pada posisi paling atas) dari stack.

B. Infix, Postfix, and Prefix Notation

     Ada tiga notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu Infix, Postfix, dan Prefix. Notasi-notasi tersebut terbentuk dari operand dan operator. Operand adalah data atau nilai, sedangkan operator adalah fungsi yang digunakan dalam proses.

     Pada notasi Infix, operator terletak di antara operand. Contoh :

     4 + 6 * (5 - 2) / 3 

     Pada notasi Prefix, operator berada di depan operand. Contoh :

     + 4 / * 6 - 5 2 3 

     Pada notasi Postfix, operator berada di belakang operand. Contoh :

     4 6 5 2 - * 3 / + 

     Mengapa kita membutuhkan notasi Prefix atau Postfix? Karena notasi tersebut tidak membutuhkan tanda kurung () untuk memprioritaskan operator-operator (operator precedence). Notasi Prefix dan Postfix lebih mudah untuk diproses oleh komputer.

     Latihan Soal :

     Infix : ( (1 + 3) / (100 * 5) ^ 30 )

     Prefix : / + 1 3 ^ * 100 5 30

     Postfix : 1 3 + 100 5 * 30 ^ /

C. Queue

     Queue atau antrian merupakan struktur data linear di mana penambahan dilakukan di satu ujung, dan pengurangan dilakukan di ujung lainnya. Dapat dianalogikan seperti orang-orang yang bergerak di eskalator. Orang yang pertama menaiki eskalator akan lebih dulu keluar dari eskalator.

     Kaidah utama dalam konsep queue adalah First In First Out (FIFO). Artinya, data yang pertama kali dimasukkan atau disimpan adalah data yang pertama kali akan diakses atau dikeluarkan.

                             

     Operasi-operasi dalam queue :

1. Enqueue : memasukkan sebuah data ke dalam queue.

2. Dequeue : menghapuskan sebuah data yang paling awal masuk ke dalam queue.

D. Perbedaan Stack dan Queue

1. Stack merupakan tumpukan, sedangkan queue merupakan antrian.

2. Stack bersifat LIFO, sedangkan queue bersifat FIFO.

3. Penambahan dan penghapusan elemen pada stack dilakukan di satu ujung, sedangkan pada queue dilakukan pada ujung yang berbeda.

HASHING AND HASH TABLES, TREES BINARY TREE

A. HASHING

     Hashing merupakan metode yang digunakan untuk menyimpan data dalam sebuah array agar dapat menyimpan data, mencari data, menambah data, dan menghapus data dengan cepat. Pengertian hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Dalam hashing, yang dilakukan adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array.

     Hash Function atau Fungsi Hash merupakan fungsi yang mengembalikan nilai atau kunci. Hash Table atau Tabel Hash merupakan array yang digunakan.

B. HASH TABLE

     Hash Table merupakan sebuah struktur data, terdiri atas sebuah tabel dan fungsi. Fungsi pada Hash Table bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

     Kelebihan dari Hash Table adalah waktu mengaksesnya yang cepat, apabila record yang dicari berada pada angka hash lokasi penyimpanannya. Namun, sering kali ditemukan Hash Table yang record-recordnya memiliki angka hash yang sama, sehingga bertabrakan.

C. HASH FUNCTION

     Hash Function yang dilambangkan dengan h(k) bertugas untuk mengubah k (key) menjadi suatu nilai dalam interval [0....X], di mana "X" adalah jumlah maksimum dari record-record yang dapat ditampung dalam tabel. Hash Function dikatakan ideal apabila mudah dihitung dan bersifat random agar dapat menyebarkan semua key. Dengan tersebarnya key, data dapat terdistribusi secara seragam dan bentrokan dapat dicegah. 

     Beberapa macam Hash Function yang dapat digunakan dalam penyimpanan database :

1. Division

      Pada metode ini, jumlah lokasi memori yang tersedia akan dihitung, kemudian digunakan untuk membagi nilai yang asli dan menghasilkan sisa yang merupakan nilai hashnya.

       Rumusnya adalah h(k)=k mod M.

       M adalah jumlah lokasi memori yang tersedia pada array.

    Hash Function tersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k).

     Dalam metode ini, sering dihasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau bisa juga disebut terjadi bentrokan. Maka, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut sebagai kebijakan resolusi bentrokan.

2. Folding

     Pada metode ini, nilai asli dibagi ke dalam beberapa bagian kemudian nilai-nilai tersebut dijumlahkan, lalu beberapa angka terakhir diambil sebagai nilai hashnya.

3. Digit

     Pada metode ini, urutan digit diubah dengan pola tertentu. Contoh, ambil digit ke-3 sampai ke-6 dari nilai aslinya kemudian balikkan urutannya dan gunakan digit yang urutannya terbalik itu sebagai nilai hash.

             

D. COLLISION

     Hash Function bukan merupakan fungsi satu ke satu, yang artinya beberapa record berbeda dapat menghasilkan nilai hash yang sama dan dapat menyebabkan terjadinya bentrokan (Collision). Apabila terjadi Collision, record-record tersebut tidak bisa menempati lokasi yang sama. 

     Ada dua cara umum untuk menangani Collision :

1. Linear Probing

     Dilakukan dengan cara mencari lokasi yang belum terisi, kemudian menambahkan string.

2. Chaining

     Dilakukan dengan cara menambahkan string pada lokasi tertentu sebagai Chained List (Linked List).

E. TREES

     Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut sebagai Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain, atau disebut Subtree.

     Istilah-istilah dalam Tree :

1. Predecessor : Node yang berada di atas node tertentu.

2. Successor    : Node yang berada di bawah node tertentu.

3. Ancestor : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

4. Descendant : Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

5. Parent : Predecessor satu level di atas suatu node.

6. Child : Successor satu level di bawah suatu node.

7. Sibling : Node-node yang memiliki parent yang sama dengan suatu node.

8. Subtree : Bagian dari Tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari Tree tersebut.

9. Size : Banyaknya node dalam suatu Tree.

10. Height : Banyaknya tingkatan/level dalam suatu Tree.

11. Root : Satu-satunya node khusus dalam Tree yang tak punya predecessor.

12. Leaf : Node-node dalam Tree yang tak memiliki successor.

13. Degree : Banyaknya child yang dimiliki suatu node.

F. BINARY TREE

     Binary Tree adalah Tree dengan syarat bahwa setiap node hanya boleh memiliki maksimal dua Subtree dan kedua Subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, setiap node dalam Binary Tree hanya boleh memiliki paling banyak dua Child.

     Kelebihan struktur Binary Tree :

1. Mudah dalam penyusunan algoritma sorting.

2. Searching data relatif cepat.

3. Fleksibel dalam penambahan dan penghapusan data.

     Jenis-jenis Binary Tree :

1. Perfect Binary Tree : sebuah Binary Tree yang setiap levelnya memiliki kedalaman yang sama.

2. Complete Binary Tree : setiap Subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki dua Child.

3. Skewed Binary Tree : sebuah Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu Child.

4. Balanced Binary Tree : tinggi maksimal suatu Tree adalah N-1, di mana N adalah jumlah node.

G. HASHING TABLE IMPLEMENTATION IN BLOCKCHAIN

     Dalam jaringan Blockchain, peran penting kriptografi terus berkembang tiada hentinya. Salah satunya yaitu proses perhitungan sebuah data secara konkret dan unik. Metode ini disebut juga dengan Hash. Ada banyak kode unik yang sering ditemukan di Blockchain, yang merupakan salah satu contoh dari Hash.

     Nilai berharga dari sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik untuk mengatasinya adalah dengan memberikan kode unik. Data tersebut akan aman. Hanya orang yang terkait yang berhak dan bisa mengakses data tersebut. Saat ini, ada beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem Blockchain menggunakan kode unik (Hash).

     Saat ini, ada sejumlah Hash yang digunakan. Fungsi dan keamanannya pun beragam dan dengan kemampuan transaksi data cepat.

BINARY SEARCH TREE

A. BINARY SEARCH TREE

     Binary Search Tree adalah tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.

     Ciri-ciri Binary Search Tree :

1. Setiap node mempunyai value dan tidak ada value yang double.

2. Value yang ada di kiri tree lebih kecil dari rootnya.

3. Value yang ada di kanan tree lebih besar dari rootnya.

4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunyai child.

5. Memiliki sifat rekursif.

     Binary Search Tree memiliki tiga operasi dasar :

1. Find(x) : menemukan value x di dalam Binary Search Tree (Search)

2. Insert(x) : memasukkan value baru x ke Binary Search Tree (Push)

3. Remove(x) : menghapus key x dari Binary Search Tree (Delete)

B. OPERASI SEARCH

1. Memulai pencarian dari root.

2. Jika root adalah value yang kita cari, maka berhenti.

3. Jika x lebih kecil dari root maka cari ke dalam rekursif tree sebelah kiri.

4. Jika x lebih besar dari root maka cari ke dalam rekursif tree sebelah kanan.

C. OPERASI INSERTION

1. Dimulai dari root

2. Jika x lebih kecil dari node value(key), kemudian cek dengan sub-tree sebelah kiri. Lakukan pengecekan secara berulang (rekursif).

3. Jika x lebih besar dari node value(key), kemudian cek dengan sub-tree sebelah kanan. Lakukan pengecekan secara berulang (rekursif).

4. Ulangi sampai menemukan node yang kosong untuk memasukkan value x. Dan x akan selalu berada di paling bawah, biasa disebut leaf atau daun.

D. OPERASI DELETION

1. Jika value yang ingin dihapus adalah leaf (daun) atau paling bawah, langsung delete.

2. Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus.

3. Jika value yang akan dihapus adalah node yang memiliki dua anak, maka ada dua cara. Kita bisa mencari dari left sub-tree anak kanan paling terakhir (leaf) (kiri, kanan). Atau dengan cara mencari dari right sub-tree anak kiri paling terakhir (leaf) (kanan, kiri).

CODING DOUBLE LINKED LIST APRILMARKET

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

// Nama : Lyvia Cornelia Michael
// NIM  : 2301906395

struct node{
char name[100];
int qty;
struct node *next;
struct node *prev;
} *head=NULL, *tail=NULL;

node* createnode(char nama[], int quantity){
struct node *curr=(struct node*) malloc(sizeof(struct node));
strcpy(curr->name, nama);
curr->qty=quantity;
curr->next=curr->prev=NULL;
return curr;
}

void pushHead(char nama[], int quantity){
node*curr=createnode(nama, quantity);
if(head==NULL){
head=tail=curr;
}else{
curr->next=head;
curr->prev=NULL;
head->prev=curr;
head=curr;
}
}

void pushTail(char nama[], int quantity){
node*curr=createnode(nama, quantity);
if(head==NULL){
head=tail=curr;
}else{
curr->prev=tail;
curr->next=NULL;
tail->next=curr;
tail=curr;
}
}

void pushMid(char nama[], int quantity){
node*curr=createnode(nama, quantity);
if(head==NULL){
head=tail=curr;
}else if(strcmpi(head->name, nama)>0){
pushHead(nama, quantity);
}else if(strcmpi(nama, tail->name)>0){
pushTail(nama, quantity);
}else{
node*temp=head;
while(temp->next!=NULL){
if(strcmpi(temp->next->name, nama)<0){
temp=temp->next;
}else{
break;
}
}
curr->next=temp->next;
temp->next->prev=curr;
temp->next=curr;
curr->prev=temp;
}
}

void view(){
node*curr=head;
printf("\n");
while(curr!=NULL){
printf("Nama : %s\n", curr->name);
printf("Qty  : %d\n\n", curr->qty);
curr=curr->next;
}
}

void edit(){
char editname[100];
int editqty;


if(head==NULL){
printf("No product to edit!\n\n");
system("pause");
return;
}

printf("\nInput Product's Name : ");
scanf(" %[^\n]", &editname);

node* temp=head;

while(temp!=NULL){
if(strcmp(temp->name, editname)!=0){
temp=temp->next;
}else{
break;
}
}

if(temp==NULL){
printf("\nThe product is not available!\n\n");
system("pause");
return;
}

printf("Input New Product Quantity : ");
scanf("%d", &editqty);

temp->qty=editqty;
printf("\nQuantity successfully edited!\n\n");
system("pause");
return;
}

void remove(){
char rmvname[100];
int rmvqty;


if(head==NULL){
printf("No product to remove!\n\n");
system("pause");
return;
}

printf("\nInput Product's Name : ");
scanf(" %[^\n]", &rmvname);

node* temp=head;

while(temp!=NULL){
if(strcmp(temp->name, rmvname)!=0){
temp=temp->next;
}else{
break;
}
}

if(temp==NULL){
printf("\nThe product is not available!\n\n");
system("pause");
return;
}

if(temp==head && head==tail){
head=tail=NULL;
free(temp);
}else if(temp==head){
head=head->next;
head->prev=NULL;
free(temp);
}else if(temp==tail){
tail=tail->prev;
tail->next=NULL;
free(temp);
}else{
temp->next->prev=temp->prev;
temp->prev->next=temp->next;
temp->prev=temp->next=NULL;
free(temp);
}
printf("\nProduct successfully removed!\n\n");
system("pause");
return;
}

int main(){
int choose=0;
char nama[100];
int quantity;

do{
printf("WELCOME TO APRILMARKET\n\n");
printf("1. Input Product\n");
printf("2. Edit Product Quantity\n");
printf("3. Remove Product\n");
printf("4. Checkout\n");
printf("Choose : ");
scanf("%d", &choose);

switch(choose){
case 1:
printf("\nInput Product's Name : ");
scanf(" %[^\n]", &nama);
printf("Input Product Quantity : ");
scanf("%d", &quantity);
pushMid(nama, quantity);
printf("\nProduct successfully added!\n\n\n");
break;

case 2:
view();
edit();
printf("\n\n");
break;

case 3:
view();
remove();
printf("\n\n");
break;
}

}while(choose!=4);

system("cls");
node* curr=head;
long long int totalprice=0;

printf("=========================================================\n");
printf("|                      APRILMARKET                      |\n");
printf("=========================================================\n");
printf("|            Product|        Price|    Qty|        Total|\n");
printf("---------------------------------------------------------\n");
while(curr!=NULL){
int price=(rand() % (100000 - 1000 + 1)) + 1000;
long long int total=price*curr->qty;
totalprice=totalprice+total;
printf("|%19s|%13d|%7d|%13lld|\n", curr->name, price, curr->qty, total);
curr=curr->next;
}
printf("---------------------------------------------------------\n");
printf("|                                                       |\n");
printf("|                                            Total Price|\n");
printf("---------------------------------------------------------\n");
printf("|%55lld|\n", totalprice);
printf("=========================================================\n");
printf("|                   KINDNESS IS FREE!                   |\n");
printf("=========================================================\n");

return 0;
}