Skip to main content

Review

Single Linked List 

merupakan suatu sistem penyimpanan dimana memori yang digunakan untuk penyimpanan digunakan secara dinamis (memori yang digunakan sesuai dengan ukuran dari data yang ditampung)
Difference between a Static Queue and a Singly Linked List ...
Struktur Single Linked List (node) : 
- Data yang ditmapung, dapat berupa : char,int, bool dan sebagainya
- Pointer next  yang merefernce ke alamat node setelahnya


Pendeklarasian:
struct Mahasiswa{
char nama[20];
char nim[20];

struct Mahasiswa * next;
};

Dalam Single Linked List dapat dilakukan juga :
Insert, Delete maupun Update

Ada beberapa cara dalam menginsert node baru :
- Insert di awal (head)
- Insert di akhir (tail)
- Insert di next dari node yang ditunjuk

Double Linked List 

merupakana salah satu perkembangan dari single linked list yaitu penyimpanan data secara dinamis (menggunakan memori secukupnya)
Doubly Linked List | Set 1 (Introduction and Insertion ...
Struktur Double Linked List : 
- Data yang ditampung, dapat berupa int , char , bool dan sebaginaya
- Pointer next  yang mereference ke node selanjutnya
- Pointer prev yang mereference ke node sebelumnya

Perbedaan antara Double Linked List & Single Linked List :
- Double Linked List lebih boros memori tetapi memilki kceepatan pencarian lebih cepat jika dibandingkan dengan Single Linked List karena memilki tambahan pointer yaitu pointer prev
- Double Linked List mempermudah jika ingin melakukan pencaraian data secara descending


Pendeklarasian:
struct Mahasiswa{
char nama[20];
char nim[20];

struct Mahasiswa * next;
struct Mahasiswa * prev;
};

Dalam Doubly Linked List dapat dilakukan juga :
Insert, Delete maupun Update

Ada beberapa cara dalam menginsert node baru :
- Insert di awal (head)
- Insert di akhir (tail)
- Insert di next dari node yang ditunjuk
- Insert di prev dari node yang ditunjuk

Circular Single Linked List

Perbedaan antara ciruclar single linked list dan single linked list biasa terdapat di bagian tail.
Di bagian tail dari circular single linked list pointer "next" nya tidak akan menunjuk ke null melainkan akan menunjuk ke awal node (head) sehingga tidak terdapat node yang isinya null

Circular Singly Linked List | Insertion - GeeksforGeeks

Circular Double Linked List



Perbedaan hampir sama seperti Circular Single Linked List dimana tidak akan ada nilai null di linked list tersebut. 

Di Circular Double Linked List, head akan memilki "prev"yang akan menunjuk pada tail dan tail akan memilki "next" yang akan menunjuk ke head 

Doubly Circular Linked List | Set 1 (Introduction and Insertion ...

Keuntungan :

- Linked list menjadi reversible
- Untuk pindah dari head ke tail maupun tail ke head lebih cepat dengan konstan waktu O(1)

Kekurangan :
- Membutuhkan memori lebih banyak dalam melakukan "prev"
- Banyak pointer yang dikaitkan sehingga dalam penggunaan pointer harus lebih teliti dan hati - hati

Contoh pengimplementasian :
- Menghandle pembuatan playlist lagu
- Menghandle shopping cart di online shop

Stack & Queue



Stack adalah konsep dimana dalam suatu linked list akan dilakukan penghapusan pada node terakhir baru node sebelumnya atau biasa orang menyebutnya dengan konsep "LIFO" (Last In First Out)

Konsep Stack :
- Pop : untuk menghapus data 
- Push : untuk menambah data baru
- Insert dan delete dari awal data 'top'
Queue adalah konsep dimana node pertama yang masuk akan meninggalkan node tersebut duluan atau bisa dibilang sesuai dengan artinya yaitu 'antri'. Jadi Queue menggunakan konsep 'FIFO' (First In First Out)


Konsep Queue:
- Enqueue : menambah data
- Dequeue : menghapus data
- Insert dimulai dari data terakhir
- Delete dimulai dari data pertama 

Queue



Hash Map

adalah suatu array yang mempunyai sekumpulan data yang ditampung sesuai dengan index arraynya, karena menggunakan index sebagai acuan / patokan sehingga pencarian data menjadi lebih cepat

Collision
Karena hashmap hanya tergantung pada index sehingga dalam pemasukan data dapat mengalami istilah "collision" sehingga ada beberapa cara agar collision dapat dicegah yaitu : 

1. Chaining :
Jika data memilki hasil hashing yang sama maka index hashing tersebut akan dibuat menjadi sebuah linked list sehingga collision tidak dapat terjadi



2. Linear probling 
adalah salah satu cara ketika memasukkan data ke hash mapnya tidak terjadi collision. Linear probling akan terjadi ketika pemasukkan data ke index tersebut tetapi index tersebut telah terisi dan akan terus mencari index yang kosong baru mengisi data tersebut



Hasil gambar untuk linear probing hash map


Binary Search Tree

BST merupakan suatu metode menganalisa node yang menggunkan konsep seperti pohon yaitu memiliki ranting. Ranting tersebut dibagi menjadi 2 macam, yaitu ranting sebelah kiri dan kanan, dimana ranting sebelah kiri merupakan kumpulan node yang lebih kecil dari induknya yaitu yang bagian tengah dan terdapat juga ranting yang sebelah kanan dimana akan berisi kumpulan node yang valuenya lebih besar dari node induknya.

Ciri - ciri BST:
- Menggunkan konsep relationship antara parent dan child
- Setiap parent node dapat mempunyai nol anak sampai dengan 2 anak(satu di sebelah kiri dan satu di sebelah kanan)
- Setiap subtree mempunyai subbranches di sebelah kanan maupun di sebelah kirinya
- Setiap node memilki nilai valuenya sendiri
- Node yang terletak di sebelah kiri dari si induk memilki value lebih kecil dari si induk dan lebih besar di sebelah kanan si induk.

Tipe - tipe BST :
- Full Binary Tree : BST yang dimana setiap node memilki anak (kecuali yang paling akhir -> leaves)
?
- Complete Binary Tree : BST yang setiap level nya memilki anak kecuali yang terakhir 

?
- Balanced / Perfect Binary Tree : setiap node memilki level yang sama dan terdapat anak dalam setipa node


Hasil gambar untuk perfect binary tree

Metode Insert :
- Misalkan kira ingin memsukkan node yang nialinya 10, kita compare dulu dengan si induk, apabila si induk nialinya lebih besar dari nilai yang kita cari maka kita mulai mencari dari anak yang sebelah kiri dan kemudian kita compare lagi, nilai 7 memilki nilai yang lebih keci dari pada 10 maka kita compare lagi dengan anak yang sebelah kanannya yaitu 9 dan memilki nilai yang lebih kecil lagi maka kita cek dulu apakah si 9 memilki anak atau tidak , jika tidak ada maka kita masukkan 10 menjadi anak dari si 9

Metode Seraching : 

Misalkan kita ingin mencari si nilai 10, maka kita comparedulu apakah nilai si induk lebih besar aau lebih besar dari si induk, apabila nilainya lebih besar maka kita compare lagi dengan si anaknya yang sebelah kiri apabila nilai anak yang sebelah kiri lebih kecil atau tidak sama dengan si 10 maka kita compare dengan anaknya yang sebelah kanannya dan di compare terus sampai nilainya ketemu. Apabila nilai yang dicari tidak ketemu maka akan direturn -1.


Metode Delete : 
Case 1 : Node yang ingin dihapus tidak memilki anak sama sekali maka langsung dihapus saja si value tesebut.
Case 2 : Node yang ingin dihapus memilki hanya satu anak maka anaknya langsung disambungkan dengan si parent dari node yang dihapus.



Case 3 : Node yang ingin dihapus memilki dua anak (child)
Ada 2 cara  : 
- In Order Predecessor : menghpus node tersebut dan digantikan dengan nilai terbesar dari node sebelah kiri dari node yang dihapus
- In Order Successor : menghapus node tersebut dan digantikan dengan nilai tersbesar dari node sebelah kanan dari node yang dihapus




Hasil Codingan saya untuk program yang bapak request :
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <stdlib.h>
#include <time.h>

struct Cart{
char productName[30];
int quantity;
int price;
struct Cart* next;
struct Cart* prev;
}*head = NULL, *tail = NULL;

struct Cart* createNewCart(char productName[], int quantity, int price){
struct Cart* newCart = (struct Cart*)malloc(sizeof(Cart));
strcpy(newCart->productName,productName);
newCart->quantity = quantity;
newCart->price = price;
newCart->next = NULL;
newCart->prev = NULL;
return newCart; 
}

void pushHead(char productName[], int quantity, int price){
struct Cart* newCart = createNewCart(productName, quantity, price);
if (!head){
head = tail = newCart;
}
else{
newCart->next = head;
head->prev = newCart;
head = newCart;
}
}


void pushTail(char productName[], int quantity, int price){
struct Cart* newCart = createNewCart(productName, quantity, price);
if (!head){
head = tail = newCart;
}
else{
newCart->prev = tail;
tail->next = newCart;
tail = newCart;
}
}

void pushMid(char productName[], int quantity, int price){
bool valid = true;
if (!head){
struct Cart* newCart = createNewCart(productName, quantity, price);
head = tail = newCart;
}
else{
if (head->price > price){
pushHead(productName, quantity, price);
}
else if (tail->price < price){
pushTail(productName, quantity, price);
}
else{
struct Cart* curr = head;
while(curr){
if(curr->productName == productName){
curr->quantity = quantity;
curr->price = price;
valid = false;
break;
}
if (curr->quantity > quantity){
break;
}
curr = curr->next;
}
if (valid){
struct Cart* newCart = createNewCart(productName, quantity, price);
newCart->prev = curr->prev;
newCart->next = curr;
curr->prev->next = newCart;
curr->prev = newCart;
}
}
}
}

void popHead(){
if (!head){
return;
}
else if (head == tail){
struct Cart* temp = head;
head = tail = NULL;
free(temp);
}
else{
struct Cart* temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}

void popTail(){
if (!head){
return;
}
else if (head == tail){
struct Cart* temp = head;
head = tail = NULL;
free(temp);
}
else{
struct Cart* temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
}
}

void popMid(char nama[]){
if (!head){
return;
}
else{
if (strcmp(head->productName,nama)==0){
popHead();
}
else if (strcmp(tail->productName,nama)==0){
popTail();
}
else{
struct Cart* curr = head;
while(curr){
if (strcmp(curr->productName,nama)==0){
break;
}
curr = curr->next;
}
curr->next->prev = curr->prev;
curr->prev->next = curr->next; 
free(curr);
}
}
}

int view(int index){
struct Cart* curr = head;
int i = 1;
int total;
if (!head){
printf("Currently there is nothing in cart...\n\n");
printf("Press any key to continue...\n");getchar();
return 0;
}
else{
printf("====================================================\n");
printf("| No | Product's Name        | Quantity | Price    |\n");
printf("====================================================\n");
while(curr){
printf("| %2d | %20s | %9d | %8d |\n",i,curr->productName,curr->quantity,curr->price);
total += (curr->price*curr->quantity);
i++;
curr = curr->next;
}
printf("====================================================\n\n");
printf("Press any key to continue...\n");getchar();
if (index == 0){
return i-1;
}
else if (index == 1){
return total;
}
}
}

void buy(){
char productName[20];
do{
printf("Input product's name [2 - 20 characters] :  ");scanf("%s",productName);
}while(strlen(productName) < 2 || strlen(productName) > 20);

int quantity = 0;
do{
printf("Input quantity [1 - 50] :  ");scanf("%d",&quantity);getchar();
}while(quantity < 1 || quantity > 50);
srand(time(NULL));   
int price = (rand() % 900000) + 10000;  
printf("Price : Rp. %d\n",price);
pushMid(productName,quantity,price);
printf("Item successfuly added to cart !\n\n");
printf("Press any key to continue...\n");getchar();
}

void remove(){
int i = 0;
int index = 0;
if (i = view(0)){
do{
printf("Input the index : [1 - %d] : ",i);
scanf("%d",&index);getchar();
}while(index < 1 || index > i);
struct Cart* curr = head;
int count = 1;
while(curr){
if (count == index){
printf("\nThe product '%s' is deleted from cart !\n\n",curr->productName);
psopMid(curr->productName);
break;
}
count++;
curr = curr->next;
}
printf("Press any key to continue. . .\n");getchar();
}
}

void printEnter(){
for (int i = 0; i < 20;i++){
printf("\n");
}
}

void checkOut(){
int total = view(1);
printf("Total price : %d\n\n",total);
printEnter();
for(int i = 0; i < 3;i++){
printf(". ");
Sleep(1000);
}
printEnter();
printf("\n\nJust kidding ! \nTotal price : GRATIS !!! \n\nKindness if free\n");
getchar();
}



int main(){
int input = 0;
do{
do{
printEnter();
printf("My Market\n");
printf("===================\n");
printf("1. Add to Cart\n");
printf("2. View Cart\n");
printf("3. Remove Cart\n");
printf("4. Check Out\n");
printf(">> ");
scanf("%d",&input);getchar();
}while(input < 1 || input > 4);
switch(input){
case 1:{
printEnter();
buy();
break;
}
case 2:{
printEnter();
view(0);
break;
}
case 3:{
printEnter();
remove();
break;
}
case 4:{
printEnter();
checkOut();
break;
}
}
}while(input != 4);

return 0;
}

Comments

Post a Comment

Popular posts from this blog

Heap dan Trie

HEAP heap merupakan algoritma yang konsepnya hampir sama dengan Tree yaitu memilki satu buah root yang akan becabang menampung node node lain yang memliki datanya masing - masing. Heap memilki dua struktur, yaitu :  - Max Heap  merupakan heap yang rootnya mempunyai value terbesar dan menampung node node yang memilki nilai value yang lebih kecil. - Min Heap merupakan heap yang rootnya mempunyai value terkecil dan menampung node node yang lebih besar dari value si root. Pengimplementasian heap digunakan pada Heap Sort (Heapify) :  - Descending membentuk max heap dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terbesar di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted - Ascending membentuk  min heap  dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terkecil di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted Tries merupakan
Post a Comment
Read more

Hash Map dan BST

Hash Map adalah suatu array yang mempunyai sekumpulan data yang ditampung sesuai dengan index arraynya, karena menggunakan index sebagai acuan / patokan sehingga pencarian data menjadi lebih cepat Collision Karena hashmap hanya tergantung pada index sehingga dalam pemasukan data dapat mengalami istilah "collision" sehingga ada beberapa cara agar collision dapat dicegah yaitu :  1. Chaining : Jika data memilki hasil hashing yang sama maka index hashing tersebut akan dibuat menjadi sebuah linked list sehingga collision tidak dapat terjadi 2. Linear probling  adalah salah satu cara ketika memasukkan data ke hash mapnya tidak terjadi collision. Linear probling akan terjadi ketika pemasukkan data ke index tersebut tetapi index tersebut telah terisi dan akan terus mencari index yang kosong baru mengisi data tersebut Binary Search Tree adalah cara menampung data yang memanfaatkan konsep akar dan menggunakan suatu node sebagai patokan atau a
Post a Comment
Read more