Rangkuman Semester

Circular Single Linked List

• Circular Single Linked List merupakan Single Linked List dimana tail node menunjuk (menggunakan pointer) pada head node.
• Ini juga berarti tidak ada node yang menunjuk pada NULL dikarenakan tail node-nya menunjuk pada head node membentuk lingkaran.
• Karena berbentuk circular maka linked list ini dapat dimulai dari mana saja karena bentuknya.

Doubly Linked List

• Bernama lain two-way linked list.
• Tidak seperti single linked list, doubly linked list setiap nodenya memiliki 2 pointer, yang satu menunjuk pada node sebelumnya (previous node) dan lainnya menunjuk pada node setelahnya (next node).
• Dikarenakan head node adalah node pertama maka pointer yang seharusnya menujuk pada node sebelumnya menunjuk pada NULL. Begitu pula dengan tail node-nya, di mana pointer yang seharusnya menunjuk pada node setelahnya menunjuk pada NULL.

 Insertion pada Doubly Linked List

• Sama seperti insertion pada Single Linked List, tetapi bedanya kali ini kita harus menghubungkan kembali bukan hanya dengan node setelahnya, tetapi juga dengan node sebelumnya karena ini adalah Doubly Linked List

Delete pada Doubly Linked List

• Jika yang di-delete adalah node satu-satunya :

      free(head);

        head = NULL;

        tail = NULL;

• Jika yang di-delete adalah head node :

        head = head ->next;
        free (head -> prev );

        head -> prev = NULL;

• Jika yang di-delete adalah tail node :

        tail = tail ->prev;
        free (tail -> next );

        tail -> next = NULL;

• Jika yang di-delete adalah bukan head node atau tail node :

        

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);

Circular Doubly Linked List

• Dapat dilihat dari namanya ini merupakan Doubly Linked list yang circular.
• Perbedaan dengan Doubly Linked List ialah tidak ada yang menunjuk pada NULL karena tail node menunjuk pada head node.
• Sama seperti Circular Single Linked List, Circular Doubly Linked List dapat dimulai dari mana saja karena bentuknya yang circular.

Sumber :

• Materi dari Binusmaya
• https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
• https://www.youtube.com/watch?v=BFYLS0uPnJk
• https://www.studytonight.com/data-structures/doubly-linked-list

I. Push

• Adalah metode memasukkan "gerbong" (data) baru pada linked list.
• Ada dua jenis push, yaitu :
• Push head
• Memasukkan data baru yang akan menjadi head (bagian depan) sehingga "gerbong" (data) yang di belakangnya terdorong.
• Contoh : {1,2,3} jika di-PushHead "7" menjadi {7,1,2,3} (Head berpindah dari 1 ke 7).
• Push Tail
• Memasukkan data baru yang akan menjadi tail (bagian belakang) sehingga "gerbong" (data) yang di depannya terdorong.
• Contoh : {1,2,3} jika di-PushHead(7) menjadi {1,2,3,7} (Head berpindah dari 1 ke 7).

II. Pop

• Adalah metode untuk menghapus data pada linked list
• Setelah dihapus datanya, kita harus menyambung kembali node yang terputus akibat hilangnya data yang dipop.

Hashing 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.

Binary Search Tree

Binary tree adalah sekumpulan data digambarkan berupa sebuah tree.

Berikut merupakan Binary Search Tree :

Binary tree selalu dimulai dari root. Setiap data memiliki maksimal 2 cabang (bisa 2, 1, atau tidak ada cabang sama sekali). Angka yang lebih kecil selalu berada di cabang yang kiri dan yang besar berada di cabang yang kanan.

Dalam Binary Search Tree ada function insertion, deletion, dan print sama seperti linked list.

Deklarasi Binary Search Tree :

#include<stdio.h>

#include<stdlib.h>

struct Data

{

         int nilai;

         Data *left , *right;

}*root = NULL;       //NULL karena belum ada data dimasukan

Insertion:

struct Data* insert(struct Data *curr,int nilai) //menggunakan struct karena akan mengreturn struct

{

          if(curr == NULL)

         {

                  struct Data *temp = (struct Data*)malloc(sizeof(struct Data));

                  temp->nilai = nilai;

                  temp->left = temp->right = NULL;

                  curr = temp;

          }

          else

         {

                if(curr->nilai > nilai)

                {

                        curr->left = insertNilai(curr->left,nilai);

                }

                else

                {

                        curr->right = insertNilai(curr->right,nilai);

                }

         }

         return curr;

}

APLIKASI

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

struct node{
  char name[21];
  int price;
  int qty;
//  int howMuchDel;
  node *next,*prev;
}*head,*tail,*curr;

void pushTail(char name[21],int qty,int price){
  curr = (struct node *) malloc(sizeof(node));
  strcpy(curr->name,name);
  curr->qty=qty;
  curr->price=price;
  curr->next = curr -> prev =NULL;

  if(head==NULL){
    head=tail=curr;
  }else{
    curr->prev=tail;
    tail->next=curr;
    tail=curr;
  }
}

void popHead(){
if(head==tail){
curr=head;
head=tail=NULL;
free(curr);
}else{
curr=head;
head=head->next;
        head->prev=NULL;
free(curr);
}
}

void pop(){

if(curr==head && curr==tail){

head=tail=NULL;

free(curr);

}else if(curr==head){

popHead();

}else if(curr==tail){

curr=tail->prev;

free(tail);

tail=curr;

tail->next=NULL;

}

else{

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

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

free(curr);

}

}

void buyItem(){
  char name [21];
  int qty;
  int price;
  int len;
  srand(time(0)); 
  do {
    printf("Masukkan input nama (max 20 huruf): ");
    scanf("%[^\n]s",name);getchar();
    len=strlen(name);
    printf("\n");
  }while (len>20);

  printf("Masukkan input quantity: ");
  scanf("%d",&qty);getchar();
  printf("\n");
  
  price=(rand() % (100000 - 10000 + 1)) + 10000;
  
  if(qty!=0){
  pushTail(name,qty,price);
  printf("Item has been added to cart.\n");
}else{
printf("No item has been added to cart (user quantity input = 0).\n");
}
}

void showItem(){
if(head==NULL) {
printf("No items in cart\n\n");
}else {
printf("=====================================================\n");
printf("|  List of items                                    |\n");

curr = head;
while(curr != NULL){
    printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
curr = curr->next;
    }
   
printf("=====================================================\n");
}
}

void editCart(){
char input [21];
int len,found=0;
do{
printf("Input item name to edit [max 20 char]: ");
scanf("%[^\n]",input);getchar();
printf("\n");
len=strlen(input);
}while(len>20);
curr=head;
while(curr!=NULL){
if(strcmp(input,curr->name)==0){
found=1;
break;
}
curr=curr->next;
}
if(found==1){
int x;
printf("\nEdit Menu: \n\n");
     printf("1. Delete from cart\n");
         printf("2. Change quantity\n");
      printf("3. Exit\n");
      printf("--> ");
scanf("%d",&x);getchar();
printf("\n");
switch(x){
case 1 :{
pop();break;
}
case 2 :{
printf("Input new quantity for item: ");
scanf("%d",&curr->qty);getchar();
printf("\n");
if(curr->qty==0){
pop();
printf("Item has been deleted\n");
}else{
printf("Item quantity has been changed.\n");
break;
}
}
                }
}else{
printf("Item not found. Please try again.\n");
editCart();
}
}

int checkOut(){
int total;
if(head==NULL) {
printf("No items left in cart\n\n");
return 0;
}else {
printf("=====================================================\n");
printf("|  List of items left in cart                       |\n");

curr =head;
while(curr != NULL){
    printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
    total+=(curr->price*curr->qty);
curr = curr->next;
    }
   
printf("=====================================================\n");
printf("=====================================================\n");
printf("|Total:                                    %d|\n",total);
printf("=====================================================\n");
}
printf("Pay?\n");
printf("Y=Pay  N=Back to Menu\n");
char yn;
printf("--> ");scanf("%c",&yn);getchar();printf("\n");
if(yn=='Y' || yn=='y'){
printf("Kindness is free.\n");
printf("No need to pay.\n");
printf("Have a good day !!!\n");
while(head!=NULL){
popHead();
}
return 1;
}else if (yn=='N' || yn=='n'){
return 0;
}

}

int main (){
  int input,flag=0;
  while (flag==0){
    printf("\nMenu: \n\n");
    printf("1. Buy Item\n");
    printf("2. View Cart\n");
    printf("3. Edit Cart\n");
    printf("4. Check Out\n");
    printf("5. Exit\n\n");
    printf("--> ");
    scanf("%d",&input);getchar();
    printf("\n");
    switch (input) {
      case 1 : buyItem();break;
      case 2 : showItem();break;
      case 3 : editCart();break;
      case 4 : flag=checkOut();break;
      case 5 : flag=1;break;
    }
  }
  return 0;
}

AVL

AVL tree adalah pengembangan dari binary tree yang nantinya tree akan dapat self balancing.

Penamaan AVL tree diambil dari penemunya yang adalah Georgy Adelson-Velsky dan Landis.

Tree dinyatakan balance jika ketinggian anak kiri dan kanan sama atau setidaknya berselisih 1.

Self balancing dari AVL tree sendiri pada dasarnya dilakukan dengan rotasi. Rotasi yang digunakan tergantung dari posisi node mana yang tidak balance dan lurus atau tidaknya node yang tidak balance dilihat dari root..

Ada 2 jenis rotasi untuk menyeimbangkan tree yaitu, Single Rotate dan Double Rotate.

Single Rotate digunakan jika untuk ke node yang tidak balance dari root adalah lurus.

Double Rotate digunakan jika untuk ke node yang tidak balance dari root adalah tidak lurus

First rotation

Second rotation

Source : PPT

Heap

Merupakan data structur yang berdasarkan tree (binary tree) yang memenuh ketentuan-ketentuan tertentu (ketentuan heap). Salah satu ketentuan heap yaitu selalu ada level terakhir yang diisi NULL.

Heap dibagi menjadi 3, yaitu min-Heap, max-Heap, dan MinMax-Heap.

Min-Heap

Min-heap adalah heap yang disusun dari kecil ke besar. Disusun kecil ke besar artinya setiap node meliki nilai yang lebih kecil dari pada childnya. Ini berarti nilai terkecil berada pada root dan nilai yang terbesar berada pada salah satu leaf di level yang terakhir.

Max-Heap

Min-heap adalah heap yang disusun dari besar ke kecil. Disusun besar ke kecil artinya setiap node meliki nilai yang lebih besar dari pada childnya. Ini berarti nilai terbesar berada pada root dan nilai yang terkecil berada pada salah satu leaf di level yang terakhir.

Tries

Tries adalah sebuah tree yang tiap leafnya menyimpan sebuah character. Biasanya root diberi char kosong ("") karena tidak digunakan nilainya. Implementasi tries antara lain untuk auto-complete dan search engine dan lainnya.

Contoh tries:

                                  ""
                                   |
                                   R
                                 /  |
                              U   E
                              /     |  \
                           N     A   S
                                    |      \
                                   L      T

kata: RUN, REAL, REST