SUMMARY

Linked List

Linked list adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat atau referensi dari record selanjutnya.

Ada beberapa operasi dasar yang terdapat pada linked list:

1. Insert: untuk memasukkan data ke dalam linked list pada posisi yang ditunjuk oleh pointer pertama.
2. Find: untuk mencari suatu data dalam linked list.
3. Remove: untuk menghilangkan sebuah simpul dari linked list.

• Circular Single Linked List

 Circular list adalah bentuk lain dari linked list yang memberikan fleksibilitas dalam elemen. Pada circular list, pointer next dari elemen terakhir menunjuk ke elemen pertama dan bukan menunjuk NULL.

• Double Linked List

Double linked list memiliki pointer penunjuk 2 arah, yaitu node sebelum dan node sesudah. Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail dari double linked list, maka pointer dari elemen terakhir menunjuk NULL. Biasanya double linked list bisa mengatasi kelemahan - kelemahan single linked list. Double linked list mempunyai fleksibilitas yang lebih tinggi daripada single linked list dalam perpindahan pada list.

• Circular Double Linked List

Circular double linked list hampir mirip dengan circular single linked list. Circular double linked list merupakan jenis linked list yang dimana rujukan pada node terakhir akan merujuk pada node pertama dan rujukan pada node pertama akan merujuk pada node terakhir.

Stack and Queue

1. Stack

Stack adalah suatu kumpulan data yang seolah - olah terlihat seperti data yang diletakkan di atas data yang lain. Stack menggunakan konsep LIFO (Last In First Out). Struktur data dari sebuah stack harus memiliki minimal 2 variabel, yaitu top dan max. Top untuk menyimpan alamat elemen paling atas dan max untuk menyimpan jumlah maksimum elemen yang dapat ditampung stack. Stack biasa digunakan untuk mengubah urutan dari data, mengubah notasi infix menjadi postfix, mengubah notasi postfix menjadi infix, mengubah angka desimal menjadi bilangan binary, dan algoritma backtracking.

Terdapat 2 operasi dasar pada stack, yaitu:

• Push: untuk memasukkan sebuah nilai atau data ke dalam stack dengan cara menaikkan posisi top satu level ke atas.
• Pop: untuk mengeluarkan atau menghapus nilai terakhir dari stack dengan cara menurunka nilai top satu level ke bawah.

2. Queue

Queue adalah salah satu implementasi dari linked list. Queue adalah kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu tail dan penghapusan data hanya melalui sisi head. Queue menggunakan konsep FIFO (First In First Out).

Terdapat 2 operasi dasar pada queue, yaitu:

• Enqueue: untuk menambahkan elemen ke dalam queue.
• Dequeue: untuk mengambil elemen dari queue dengan cara memindahkan semua elemen satu langkah ke posisi depannya sehingga elemen yang paling depan tertimpa.

3. Prefix, Infix, dan Postfix

• Notasi prefix: notasi yang operatornya ditempatkan sebelum dua operand.
• Notasi infix: notasi yang operatornya ditempatkan diantara dua operand.
• Notasi postfix: notasi yang operatornya ditempatkan setelah dua operand.

Hashing, Hash Table, Trees & Binary Tree

Hashing & Hash Table

• Hashing: transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli.
• Hash Table: sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Ada beberapa fungsi hash yang digunakan, yaitu:

1. Metode pembagian-sisa: metode yang memperkirakan ukuran jumlah item dalam tabel, lalu menggunakannya sebagai pembagi dalam setiap nilai atau kunci asli untuk mengekstrak hasil bagi dan sisa. Sisa tersebut adalah nilai hash.
2. Metode lipat: membagi nilai asli menjadi beberapa bagian, menambahkan bagian - bagian bersama - sama, dan menggunakan 4 digit terakhir sebagai nilai hash.
3. Metode transformasi radix: jika kunci digital, basis angka dapat diubah menghasilkan urutan digit yang berbeda. Angka urutan tinggi dapat dibuang agar sesuai dengan nilai hash.
4. Metode penataan ulang digit: mengambil bagian dari nilai asli, membalikkan urutannya, dan menggunakan urutan digit itu sebagai nilai hash.

• Hash Collision

Jumlah kemungkinan kunci sangat banyak, bahkan tak terhingga. Sedangkan jumlah sel dalam hash table terbatas. Hal ini memungkinkan timbulnya collision, yaitu 2 atau lebih kunci  yang menghasilkan code yang sama. Maka dari itu collision tidak mungkin terhindarkan.

Ada 2 cara yang bisa digunakan jika terjadi collision, yaitu:

1. Linear Probing: mencari slot kosong dan meletakkan string disana.
2. Chaining: menggunakan struktur data linked list.

Trees

• Tree: salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis antara elemen - elemen.
• Tree adalah kumpulan dari satu atau lebih node.

Istilah-istilah dalam konsep tree:

1. Root: node yang paling atas
2. Edge: garis yang menghubungkan parent ke child
3. Leaf: node - node dalam tree yang tidak memiliki child
4. Sibling: node - node yang memiliki parent yang sama dengan suatu node
5. Degree: total sub tree dari suatu node
6. Height/Depth: maksimum degree dari node yang ada dalam tree
7. Ancestor: seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
8. Descendant: seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama

Binary Tree

• Binary Tree: tree dimana tidak ada node pada tree tersebut yang memiliki lebih dari 2 sub tree atau setiap simpul paling banyak mempunyai 2 child yang terdiri dari left subtree atau right subtree.

Jenis-jenis Binary Tree:

1. Perfect Binary Tree: binary tree yang setiap levelnya memiliki depth yang sama
2. Complete Binary Tree: tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
3. Skewed Binary Tree: semua nodenya (kecuali leaf) hanya memiliki 1 child.
4. Balanced Binary Tree: tidak ada leaf yang lebih jauh dari root dibanding leaf lainnya.

Representasi dari Binary Tree:

• Implementasi menggunakan array: Dalam susunan dari atas ke bawah ataupun dari kanan ke kiri. Penomoran dimulai dari simpul akar dan kemudian sisanya akan diberikan semakin meningkat jumlahnya di level.
• Implementasi menggunakan linked list

Binary Search Tree

• Binary Search Tree: struktur data yang mengadopsi konsep binary tree namun terdapat aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

3 jenis cara untuk melakukan penelusuran pada BST:

1. PreOrder: print data, telusur ke kiri, telusur ke kanan
2. InOrder: telusur ke kiri, print data, telusur ke kanan
3. PostOrder: telusur ke kiri, telusur ke kanan, print data

Operasi yang terdapat pada BST:

Operasi: Search

Karena ada syarat di dalam BST, searching di dalam BST menjadi mudah. 

Misalkan key yang dicari adalah value X.

• Memulai dari root
• Jika root adalah value yang dicari, maka berhenti
• Jika X lebih kecil dari root, maka cari secara rekursif ke tree sebelah kiri
• Jika X lebih besar dari root, maka cari secara rekursif ke tree sebelah kanan

Operasi: Insertion

Memasukkan value baru ke BST dilakukan dengan cara rekursif.

Misalkan kita memasukkan value X.

• Memulai dari root
• Jika X lebih kecil dari node key, masukkan X ke subtree kiri, jika lebih besarm masukkan X ke subtree kanan
• Ulang sampai ditemukan node kosong untuk meletakkan X

Operasi: Deletion

3 case yang harus dipertimbangkan:

• Jika value yang ingin dihapus ada di leaf, langsung hapus
• Jika value yang ingin dihapus memiliki satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• Jika value yang akan dihapus memiliki dua anak, cari anak paling kanan di subtree kiri (node P), ganti value dengan value P dan hilangkan P secara rekursif

Tugas Minimarket Application

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


struct Data{

char product[50];
int quan;
long long int price;
struct Data *next, *prev;


}*head = NULL, *tail = NULL, *curr;

char product[50];
int quan;
long long int price;
int index;

void Menu(){

printf("DREAMMERS MINIMARKET\n");
printf("====================\n");

printf("1. Insert Product\n");
printf("2. Edit Product's Quantity\n");
printf("3. Delete Product\n");
printf("4. View\n");
printf("5. Checkout\n");
printf(">>Choice: ");
}

void insert(){

do{
printf("Insert Product's Name: ");
    scanf("%[^\n]", &product); getchar();
 
}while(strlen(product) < 1 || strlen(product) > 50);
}

void Quantity(){
do{
   printf("Insert Product's Quantity (1-50 Only): ");
   scanf("%d", &quan); getchar();
 
}while(quan < 1 || quan > 50);
}

void push(char product[], int quan, int price){

curr = (struct Data*)malloc(sizeof(struct Data));
strcpy(curr->product, product);

curr->quan = quan;
curr->price = price;
curr->prev = curr->next = NULL;


if(head == NULL){
head = tail = curr;

}else if(strcmp(curr->product, head->product) < 0){

head->prev = curr;
curr->next = head;
head = curr;

}else if(strcmp(curr->product, tail->product) > 0){

tail->next = curr;
curr->prev = tail;
tail = curr;

  }else{
  struct Data *temp = head;
 
while(strcmp(curr->product, temp->next->product) > 0){
temp = temp->next;
  }
 
curr->next = temp->next;
temp->next = curr;
curr->prev = temp;
temp->next->prev = curr;
  }
}

void pop(char product[]){

if(strcmp(product, head->product) == 0 && head == tail){
printf("You have deleted %s\n", curr->product);
free(head);
head = tail = NULL;

}else if(strcmp(product, head->product) == 0){
curr = head;
head = head->next;
printf("You have deleted %s\n", curr->product);
free(curr);
head->prev = NULL;

}else if(strcmp(product, tail->product) == 0){
curr = tail;
tail = tail->prev;
printf("You have deleted %s\n", curr->product);
free(curr);
tail->next = NULL;
  }else{
  curr = head;
 
while(curr != NULL){
if(strcmp(product, curr->product) == 0){
break;
}
    curr = curr->next;
}

  if(curr == NULL){
printf("Product not found\n");

  }else{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
printf("You have deleted %s\n", curr->product);
free(curr);

  }
  }
}

void edit(char product[]){

  curr = head;
 
  while(curr != NULL){
  if(strcmp(product, curr->product) == 0){
  break;
}
  curr = curr->next;
  }

  if(curr == NULL){
  printf("Product not found\n");
}else{
 
  Quantity();
  curr->quan = quan;
  printf("You have changed product %s quantity\n", curr->product);
}
}

long long int random(){

long lower  = 100;
long upper = 999000;

return (rand() % (upper-lower+1) + lower);
}

void add(){

  insert();

  curr = head;
 
  while(curr != NULL){
  if(strcmp(product, curr->product) == 0){
  break;
}
  curr = curr->next;
  }

  if(curr == NULL){
  Quantity();
 
  price = random();
  push(product, quan, price);
  printf("You have inserted new product\n");
 
  }else{
  printf("Product already exist\n");
 
  edit(product);
  }
}

void del(){
  insert();
  pop(product);
}

void view(int choice){
  long long int total = 0;
  index = 0;
 
  if(choice == 4){
  printf("=============================== CART LIST =================================\n");
  printf("===========================================================================\n");
 
  }else if(choice == 5){
 
  printf("============================== CHECKOUT LIST ==============================\n");
  printf("===========================================================================\n");
  printf("| %3s. | %-20s | %5s | %15s | %15s |\n", "No", "Product", "Qty", "Price", "Total Price");
  curr = head;
}

  while(curr != NULL){
 
  printf("| %3d. | %-20s | %5d | %-8s %6ld | %-5s %9ld |\n", index + 1, curr->product, curr->quan, "Rp.", curr->price, "Rp.", curr->quan * curr->price);
  total  = total + curr->quan * curr->price;
  curr = curr->next;
  index++;
  }
 
  if(choice == 4){
  printf("\n");
  printf("Total\t: Rp. %lld\n", total);
  }else if(choice == 5){
  printf("===========================================================================\n\n");
printf("Total : Rp. %lld\n", total);
 
  }
}


int main(){

  int choice = 0;
 
  do{
  Menu();
 
  scanf("%d", &choice); getchar();
 
  switch(choice){
    case 1:
    add();
   
    break;
    case 2:
    if(head == NULL){
    printf("No Data!\n");
}else{
      insert();
      edit(product);
    }
   
    break;
  case 3:
    if(head == NULL){
    printf("No data\n");
}else{
del();
}

    break;
    case 4:
   
    if(head == NULL){
    printf("No Data!\n");
}else{
view(choice);
}

    break;
    case 5:
   
    if(head == NULL){
    printf("You haven't buy anything\n");
}else{
view(choice);
}

    printf("\nThankyou for buying\n");
    break;
  }
 
  if(choice < 5 && choice > 0){
    printf("\nPress enter to continue...\n"); getchar();
  }
 
  }while(choice != 5);

 return 0;
}