CSLL (Circular Single/Singly Linked List) dan DCLL (Double/Doubly Circular Linked List)


Circular Single Linked List
Merupakan perkembangan dari single linked list
Tidak memiliki tail, tidak seperti single linked list, karena Head akan kembali lagi ke posisi awal ketika sudah di ujung list tersebut

Keuntungan
Tidak memerlukan Tail setelah data pertama dimasukkan karena node bisa kembali ke node semula
Dapat digunakan dalam implementasi Queue, karena node selanjutnya bisa dianggap sebagai node sebelum yang paling akhir
Digunakan dalam beberapa aplikasi yang menggunakan turn/giliran

#include<stdio.h>
#include<conio.h>

void insertAtBeginning(int);
void insertAtEnd(int);
void insertAtAfter(int,int);
void deleteBeginning();
void deleteEnd();
void deleteSpecific(int);
void display();

struct Node
{
   int data;
   struct Node *next;
}*head = NULL;

void main()
{
   int choice1, choice2, value, location;
   clrscr();
   while(1)
   {
      printf("\n*********** MENU *************\n");
      printf("1. Insert\n2. Delete\n3. Display\n4. Exit\nEnter your choice: ");
      scanf("%d",&choice1);
      switch()
      {
         case 1: printf("Enter the value to be inserted: ");
                           scanf("%d",&value);
                 while(1)
                 {
                         printf("\nSelect from the following Inserting options\n");
                         printf("1. At Beginning\n2. At End\n3. After a Node\n4. Cancel\nEnter your choice: ");
                    scanf("%d",&choice2);
                    switch(choice2)
                    {
                   case 1:   insertAtBeginning(value);
                                  break;
                   case 2:   insertAtEnd(value);
                                  break;
                case 3:   printf("Enter the location after which you want to insert: ");
                                  scanf("%d",&location);
                                  insertAfter(value,location);
                                  break;
                       case 4:   goto EndSwitch;
                       default: printf("\nPlease select correct Inserting option!!!\n");
                    }
                 }
         case 2: while(1)
                 {
                   printf("\nSelect from the following Deleting options\n");
  printf("1. At Beginning\n2. At End\n3. Specific Node\n4. Cancel\nEnter your choice: ");
                    scanf("%d",&choice2);
                    switch(choice2)
                    {
                       case 1:   deleteBeginning();
                                  break;
                       case 2:   deleteEnd();
                                  break;
                       case 3:   printf("Enter the Node value to be deleted: ");
                                  scanf("%d",&location);
                                  deleteSpecic(location);
                                  break;
                       case 4:   goto EndSwitch;
                       default: printf("\nPlease select correct Deleting option!!!\n");
                    }
                 }
                 EndSwitch: break;
         case 3: display();
                  break;
         case 4: exit(0);
         default: printf("\nPlease select correct option!!!");
      }
   }
}

void insertAtBeginning(int value)
{
    struct Node *newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = value;
    if(head == NULL)
    {
       head = newNode;
       newNode -> next = head;
    }
    else
    {
       struct Node *temp = head;
       while(temp -> next != head)
          temp = temp -> next;
       newNode -> next = head;
       head = newNode;
       temp -> next = head;
    }
    printf("\nInsertion success!!!");
}
void insertAtEnd(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {
      head = newNode;
      newNode -> next = head;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> next != head)
         temp = temp -> next;
      temp -> next = newNode;
      newNode -> next = head;
   }
   printf("\nInsertion success!!!");  
}
void insertAfter(int value, int location)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {     
      head = newNode;
      newNode -> next = head;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> data != location)
      {
         if(temp -> next == head)
         {
            printf("Given node is not found in the list!!!");
            goto EndFunction;
         }
         else
         {
            temp = temp -> next;
         }
      }
      newNode -> next = temp -> next;
      temp -> next = newNode;
      printf("\nInsertion success!!!");
   }
   EndFunction:
}
void deleteBeginning()
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp = head;
      if(temp -> next == head)
      {
         head = NULL;
         free(temp);
      }
      else{
         head = head -> next;
         free(temp);
      }
      printf("\nDeletion success!!!");
   }
}
void deleteEnd()
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp1 = head, temp2;
      if(temp1 -> next == head)
      {
         head = NULL;
         free(temp1);
      }
      else{
         while(temp1 -> next != head){
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
         temp2 -> next = head;
         free(temp1);
      }
      printf("\nDeletion success!!!");
   }
}
void deleteSpecific(int delValue)
{
   if(head == NULL)
      printf("List is Empty!!! Deletion not possible!!!");
   else
   {
      struct Node *temp1 = head, temp2;
      while(temp1 -> data != delValue)
      {
         if(temp1 -> next == head)
         {
            printf("\nGiven node is not found in the list!!!");
            goto FuctionEnd;
         }
         else
         {
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
      }
      if(temp1 -> next == head){
         head = NULL;
         free(temp1);
      }
      else{
         if(temp1 == head)
         {
            temp2 = head;
            while(temp2 -> next != head)
               temp2 = temp2 -> next;
            head = head -> next;
            temp2 -> next = head;
            free(temp1);
         }
         else
         {
            if(temp1 -> next == head)
            {
               temp2 -> next = head;
            }
            else
            {
               temp2 -> next = temp1 -> next;
            }  
            free(temp1);
         }
      }
      printf("\nDeletion success!!!");
   }
   FuctionEnd:
}
void display()
{
   if(head == NULL)
      printf("\nList is Empty!!!");
   else
   {
      struct Node *temp = head;
      printf("\nList elements are: \n");
      while(temp -> next != head)
      {
         printf("%d ---> ",temp -> data);
      }
      printf("%d ---> %d", temp -> data, head -> data);
   }
}

Insertion
Insertion untuk code tersebut dapat dilakukan dengan 3 cara:
1.       Insert depan
2.       Insert Akhir
3.       Insert di lokasi yang spesifik
Insert depan
1.       newNode dibuat dengan value yang diinput
2.       cek apakah daftar tersebut kosong/Head ==NULL
3.       Jika NULL, maka Head=newNode, dan newNode -> next=head
4.       Jika tidak kosong, maka membentuk pointer temp dan dimulai dengan head
5.       temp akan bergeser terus sampai node ‘akhir’/setelah temp adalah head
6.       set newNode->next=head dan newNode->next=head
Insert Akhir
1.       newNode dibuat dengan value yang diinput
2.       cek apakah daftar tersebut kosong/Head ==NULL
3.       Jika NULL, maka Head=newNode, dan newNode -> next=head
4.       Jika tidak kosong, maka membentuk pointer temp dan dimulai dengan head
5.       temp akan bergeser terus sampai node ‘akhir’/setelah temp adalah head
6.       set temp->next = newNode dan newNode->next = head
Insert di lokasi yang spesifik(setelah ada Node)
1.       newNode dibuat dengan value yang diinput
2.       cek apakah daftar tersebut kosong/Head ==NULL
3.       Jika NULL, maka Head=newNode, dan newNode -> next=head
4.       Jika tidak kosong, maka mebentuk temp dan dimulai dengan head
5.       temp akan bergeser terus sampai node setelah node yang ingin diisi
6.       setiap kali temp akan memeriksa apakah temp sudah sampai node paling ujung/temp setelahnya adalah Head. Jika berada di situ, maka muncul 'Given node is not found in the list!!! Insertion not possible!!!' dan function berhenti. Jika tidak, maka temp akan terus bergeser
7.       jika temp telah sampai node setelah node yang ingin diisi dengan newNode, maka akan diperiksa jika node tersebut adalah node terakhir/temp->next = head
8.       jika temp adalah node terakhir, maka set temp->next = newNode dan newNode->next = head
7.       jika temp bukan node terakhir, maka set newNode->next=head dan newNode->next=head

Deletion
                Deletion dalam code tersebut dapat dilakukan dengann 3 cara:
1.       Delete dari depan
2.       Delete dari terakhir
3.       Delete di lokasi yang spesifik

Delete depan
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka membentuk pointer temp1 dan temp2 dan inisialisasi temp1 dan temp2 dengan Head
4.       Cek apakah daftar tersebut hanya memiliki satu node/ temp1->next == head
5.       Jika True, maka Head== NULL dan hapus temp1, Kemudian function selesai (daftar akan memenuhi syarat kosong)
6.       Jika False, maka geser temp1 sampai node terakhir/temp1-> next == head
7.       set head = temp2 → next, temp1 → next = head dan hapus temp2

Delete terakhir
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka membentuk pointer temp1 dan temp2 dan inisialisasi temp1 dan temp2 dengan Head
4.       Cek apakah daftar tersebut hanya memiliki satu node/ temp1->next == head
5.       Jika True, maka Head== NULL dan hapus temp1, Kemudian function selesai (daftar akan memenuhi syarat kosong)
6.       Jika False, makaset temp2=temp1 dan geser temp1 sampai node terakhir/temp1-> next == head
7.       set temp2->next=head, dan hapus temp1

Delete di lokasi yang spesifik
1.       Cek apakah daftar tersebut kosong/Head == NULL
2.       Jika kosong, maka munculkan 'List is Empty!!! Deletion is not possible' dan function selesai
3.       Jika tidak kosong, maka membentuk pointer temp1 dan temp2 dan inisialisasi temp1 dan temp2 dengan Head
4.       Temp1 akan bergeser sampai node sampai mencapai node yang ingin dihapus atau node terakhir. Set temp2=temp1 sebelum temp1 bergeser ke node selnjutnya
5.       Jika sudah mencapai node terakhir, maka cetak  'Given node not found in the list! Deletion not possible!!!' dan function selesai
6.       Jika sudah mencapai node yang ingin dihapus, maka cek apakah daftar hanya memiliki satu node/temp1->next ==head
7.       Jika hanya ada satu node dan node itu yang akan dihapus, maka set Head==NULL dan hapus temp1(free(temp1))
8.       Jika ada node lebih dari satu, maka cek apakah temp1 adalah node epan temp1==Head
9.       Jika temp1 adalah Head maka set temp2==Head dan geser temp2 sampai ke node terakhir, kemudian set Head=Head->next, temp2->next=head dan hapus temp1
1        Jika temp1 bukan node pertama kemudian cek apakah temp1 adalah node terakhir
1      Jika temp1 adalah node terakhir, maka set temp2->next=head dan hapus temp1 (free(temp1))
1    Jika temp1 bukan node depan dan akhir, maka set temp2->next = temp1->next dan hapus temp1(free(temp1))


Display
                Cara menampilkan elemen yang ada dalam daftar tersebut adalah:
1.       Cek apakah daftar kosong/Head==NULL
2.       Jika kosong, maka munculkan 'List is Empty!!!' dan function selesai
3.       Jika tidak kosong, maka membentuk pointer temp dan dimulai dengan Head
4.       Munculkan temp->data dengan tanda panah sampai temp mencapai node terakhir
5.       Munculkan temp->data dengan panah menunjuk head->data


Double Circular Linked List

Double Circular Linked List adalah kombinasi dari Double linked lit dan circular linked list. Selaindapat bergeser dua arah, Double Circular Linked List tidak hanya dapat langsung bergeser dari Tail ke Head, tetapi juga dapat dari Head langsung ke Tail

Keuntungan
Dapat langsung bergeser dari Head ke Tail/vice versa dengan satu pergeseran
Dapat bergeser dua arah

Implementasi
Playlist Lagu
System Shopping Cart

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
    struct node *prev; 
    struct node *next; 
    int data; 
}; 
struct node *head; 
void insertion_beginning(); 
void insertion_last(); 
void deletion_beginning(); 
void deletion_last(); 
void display(); 
void search(); 
void main () 
{ 
int choice =0; 
    while(choice != 9) 
    { 
        printf("\n*********Main Menu*********\n"); 
        printf("\nChoose one option from the following list ...\n"); 
        printf("\n===============================================\n"); 
        printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search\n6.Show\n7.Exit\n"); 
        printf("\nEnter your choice?\n"); 
        scanf("\n%d",&choice); 
        switch(choice) 
        { 
            case 1: 
            insertion_beginning(); 
            break; 
            case 2: 
                    insertion_last(); 
            break; 
            case 3: 
            deletion_beginning(); 
            break; 
            case 4: 
            deletion_last(); 
            break; 
            case 5: 
            search(); 
            break; 
            case 6: 
            display(); 
            break; 
            case 7: 
            exit(0); 
            break; 
            default: 
            printf("Please enter valid choice.."); 
        } 
    } 
} 
void insertion_beginning() 
{ 
   struct node *ptr,*temp;  
   int item; 
   ptr = (struct node *)malloc(sizeof(struct node)); 
   if(ptr == NULL) 
   { 
       printf("\nOVERFLOW"); 
   } 
   else 
   { 
    printf("\nEnter Item value"); 
    scanf("%d",&item); 
    ptr->data=item; 
   if(head==NULL) 
   { 
      head = ptr; 
      ptr -> next = head;  
      ptr -> prev = head;  
   } 
   else  
   { 
       temp = head;  
    while(temp -> next != head) 
    { 
        temp = temp -> next;  
    } 
    temp -> next = ptr; 
    ptr -> prev = temp; 
    head -> prev = ptr; 
    ptr -> next = head; 
    head = ptr; 
   } 
   printf("\nNode inserted\n"); 
} 
    
} 
void insertion_last() 
{ 
   struct node *ptr,*temp; 
   int item; 
   ptr = (struct node *) malloc(sizeof(struct node)); 
   if(ptr == NULL) 
   { 
       printf("\nOVERFLOW"); 
   } 
   else 
   { 
       printf("\nEnter value"); 
       scanf("%d",&item); 
        ptr->data=item; 
       if(head == NULL) 
       { 
           head = ptr; 
           ptr -> next = head;  
           ptr -> prev = head;  
       } 
       else 
       { 
          temp = head; 
          while(temp->next !=head) 
          { 
              temp = temp->next; 
          } 
          temp->next = ptr; 
          ptr ->prev=temp; 
          head -> prev = ptr; 
      ptr -> next = head; 
        } 
   } 
     printf("\nnode inserted\n"); 
} 
 
void deletion_beginning() 
{ 
    struct node *temp; 
    if(head == NULL) 
    { 
        printf("\n UNDERFLOW"); 
    } 
    else if(head->next == head) 
    { 
        head = NULL;  
        free(head); 
        printf("\nnode deleted\n"); 
    } 
    else 
    { 
        temp = head;  
        while(temp -> next != head) 
        { 
            temp = temp -> next; 
        } 
        temp -> next = head -> next; 
        head -> next -> prev = temp; 
        free(head); 
        head = temp -> next; 
    } 
 
} 
void deletion_last() 
{ 
    struct node *ptr; 
    if(head == NULL) 
    { 
        printf("\n UNDERFLOW"); 
    } 
    else if(head->next == head) 
    { 
        head = NULL;  
        free(head);  
        printf("\nnode deleted\n"); 
    } 
    else  
    { 
        ptr = head;  
        if(ptr->next != head) 
        { 
            ptr = ptr -> next;  
        } 
        ptr -> prev -> next = head; 
        head -> prev = ptr -> prev;   
        free(ptr); 
        printf("\nnode deleted\n"); 
    } 
} 
 
void display() 
{ 
    struct node *ptr; 
    ptr=head; 
    if(head == NULL) 
    { 
        printf("\nnothing to print"); 
    }    
    else 
    { 
        printf("\n printing values ... \n"); 
         
        while(ptr -> next != head) 
        { 
         
            printf("%d\n", ptr -> data); 
            ptr = ptr -> next; 
        } 
        printf("%d\n", ptr -> data); 
    } 
             
} 
 
void search() 
{ 
    struct node *ptr; 
    int item,i=0,flag=1; 
    ptr = head;  
    if(ptr == NULL) 
    { 
        printf("\nEmpty List\n"); 
    } 
    else 
    {  
        printf("\nEnter item which you want to search?\n");  
        scanf("%d",&item); 
        if(head ->data == item) 
        { 
        printf("item found at location %d",i+1); 
        flag=0; 
        } 
        else  
        { 
        while (ptr->next != head) 
        { 
            if(ptr->data == item) 
            { 
                printf("item found at location %d ",i+1); 
                flag=0; 
                break; 
            }  
            else 
            { 
                flag=1; 
            } 
            i++; 
            ptr = ptr -> next; 
        } 
        } 
        if(flag != 0)  
        { 
            printf("Item not found\n"); 
        } 
    }    
         

}  





Komentar

Posting Komentar

Postingan populer dari blog ini

CA01-011 Heap & Tries

Gambar
Max Heap : pohon yang parentnya selalu lebih besar dari anaknya Min Heap : pohon yang parentnya selalu lebih kecil dari anaknya Min-Max Heap : Pohon yang selang-seling parentnya Heap biasanya menggunakan array, tapi bisa menggunakan linked list juga. Dimulai dari 1 untuk memudahkan mencari node. Insert dalam heap dilakukan dengan seperti berikut: 1.        Insert node seperti dalam Binary Tree 2.        cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk min heap, lebih kecil dari parentnya untuk max heap) 3.        Jika salah, maka angka tersebut ditukar dengan parentnya 4.        lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root aksi yang dilakukan tersebut disebut Heapify Up untuk delete dilakukan sebagai berikut: 1.        hap...
Baca selengkapnya