Circular Linked List

As we know, in the case of singly linked list, the next reference to tail is pointed to NULL to indicate that this is the end of the linked list. But in case of circular linked list, tail points back to head.
 
 
Implementation of Circular Linked List
 
Code:
 
#include <stdio.h>
#include "stdlib.h"
 
struct node{
                int num;
                struct node *next;
}*head, *tail;
 
int sizeoflist;
 
void Display(){
               
                if(head == NULL){
                                printf("\nLinked List is empty!!");
                                return;
                }
                struct node *ptr = head;
                printf("\n-----------Displaying linked list-----------\n");
                printf("\nHead->");
                while(ptr!=tail){
                                printf("%d -> ", ptr->num);
                                ptr = ptr->next;
                }
                printf("%d-> Tail ->%d (head)", tail->num, tail->next->num);
}
 
/*adding element at the end of the linked list*/
void Add_at_tail(){
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the end of the list: ");
                scanf("%d", &ptr->num);
                ptr->next = NULL;
               
                if(tail == NULL){
                                /*Linked list is not formed. Add first element to the linked list*/
                                head = ptr;
                                tail = ptr;
                }
                else{
                                /*add element at the end of the linked list*/
                                tail->next = ptr;
                                tail = ptr;
                               
                                /*feature of CLL*/
                                tail->next = head;
                }
               
                printf("\n%d is added at the tail..", ptr->num);
                sizeoflist++;
}
 
/*adding element at the beginning of the linked list*/
void Add_at_head(){
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the beginning of the list: ");
                scanf("%d", &ptr->num);
                ptr->next = NULL;
               
                if(head == NULL){
                                /*Linked list is not formed. Add first element to the linked list*/
                                head = ptr;
                                tail = ptr;
                }
                else{
                                /*add element at the beginning of the linked list*/
                                ptr->next = head;
                                head = ptr;
                                /*feature of CLL*/
                                tail->next = head;
                }
               
                printf("\n%d is added at the head..", ptr->num);
                sizeoflist++;
}
 
 
/*adding element at the nth position of the linked list*/
/*Linked list position starts from 1*/
void Add_at_nth_position(){
               
                int position = 0;
               
                printf("\nEnter the position where you want to add element in the list: ");
                scanf("%d", &position);
               
                if(position <= 1 || position >= sizeoflist){
                                printf("\nINVALID POSITION!! Position should be strictly in between 1 and %d", sizeoflist);
                                return;
                }
 
                /*position is in between 1 and sizeoflist*/          
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the %d-th position of the list: ", position);
                scanf("%d", &ptr->num);
                ptr->next = NULL;
               
                /*find position*/
                struct node *prev = NULL, *temp = head;
                int curloc = 1;
                while(temp != NULL && curloc != position){
                                prev = temp;
                                temp = temp->next;
                                curloc++;
                }
               
                /*we need to add ptr in between prev and temp*/
                prev->next = ptr;
                ptr->next = temp;
               
                printf("\n%d is added at %d-th position in the linked list..", ptr->num, position);
                sizeoflist++;
}
 
/*deleting tail of the linked list*/
void Delete_from_tail(){
                struct node *temp = head, *prev = NULL;
               
                if(head == NULL){
                                printf("\nLinked List is empty!!");
                                return;
                }
                else if(sizeoflist == 1){
                                /*only one element in the linked list*/
                                printf("\n%d is deleted from the linked list from tail position", tail->num);
                                free(tail);
                                head = NULL;
                                tail = NULL;
                }
                else{
                                /*multiple elements in linked list*/
                                while(temp != tail){
                                                prev = temp;
                                                temp = temp->next;
                                }
                                printf("\n%d is deleted from the linked list from tail position", tail->num);           
                                free(tail);
                                tail = prev;
                                /*feature of CLL*/
                                tail->next = head;
                }             
                sizeoflist--;
}
 
/*deleting head of the linked list*/
void Delete_from_head(){
                struct node *temp = NULL;
               
                if(head == NULL){
                                printf("Linked List is empty!!");
                                return;
                }
                else if(sizeoflist == 1){
                                /*only one element in the linked list*/
                                printf("\n%d is deleted from the linked list from head position", head->num);
                                free(head);
                                head = NULL;
                                tail = NULL;
                }
                else{
                                /*multiple elements in linked list*/
                                printf("\n%d is deleted from the linked list from head position", head->num);
                                temp = head->next;
                                free(head);
                                head = temp;
                                /*feature of CLL*/
                                tail->next = head;
                }
                sizeoflist--;
}
 
/*deleting element from the nth position of the linked list*/
/*Linked list position starts from 1*/
void Delete_from_nth_position(){
               
                int position = 0;
               
                printf("\nEnter the position from where you want to delete element in the list: ");
                scanf("%d", &position);
               
                if(head == NULL){
                                printf("Linked List is empty!!");
                                return;
                }
                else if(position <= 1 || position >= sizeoflist){
                                printf("\nINVALID POSITION!! Position should be strictly in between 1 and %d", sizeoflist);
                                return;
                }
 
                /*position is in between 1 and sizeoflist*/          
                /*find position*/
                struct node *prev = NULL, *temp = head, *tmp = NULL;
                int curloc = 1;
                while(temp!=NULL && curloc != position){
                                prev = temp;
                                temp = temp->next;
                                curloc++;
                }
               
                /*we need to delete temp and point prev to temp->next*/
                tmp = temp->next;
                prev->next = tmp;
                printf("\n%d is deleted from %d-th position from the linked list", temp->num, position);
                free(temp);
                temp = NULL;
               
                sizeoflist--;
 
}
 
void main(){
               
                int option;
                char con, c;
               
                do{
                                do{
                                                printf("\n\nWhat do you want to do?");
                                                printf("\n1. Add to head\n2. Add to tail\n3. Add at nth position\n4. Delete head");
                                                printf("\n5. Delete tail\n6. Delete at nth position\n7. Display\n8. Exit\nOption : ");
                                                scanf("%d", &option);
                                               
                                                switch(option){
                                                                case 1:
                                                                                Add_at_head();
                                                                                break;
                                                                case 2:
                                                                                Add_at_tail();
                                                                                break;
                                                                case 3:
                                                                                Add_at_nth_position();
                                                                                break;
                                                                case 4:
                                                                                Delete_from_head();
                                                                                break;
                                                                case 5:
                                                                                Delete_from_tail();
                                                                                break;
                                                                case 6:
                                                                                Delete_from_nth_position();
                                                                                break;
                                                                case 7:
                                                                                Display();
                                                                                break;
                                                                case 8:
                                                                                goto exit;
                                                                                break;
                                                                default:
                                                                                break;  
                                                }
                                               
                                }while(1);
                               
                                exit:
                                               
                                printf("\nDo you want to continue (y/n) ?:");
                                getchar();
                                con = getchar();
                }while(con == 'y' || con == 'Y');
}
 
Output:
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 12
 
12 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 2
 
Enter value to be added at the end of the list: 23
 
23 is added at the tail..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 34
 
34 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 2
 
Enter value to be added at the end of the list: 45
 
45 is added at the tail..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 56
 
56 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->56 -> 34 -> 12 -> 23 -> 45-> Tail ->56 (head)
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 3
 
Enter the position where you want to add element in the list: 3
 
Enter value to be added at the 3-th position of the list: 22
 
22 is added at 3-th position in the linked list..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->56 -> 34 -> 22 -> 12 -> 23 -> 45-> Tail ->56 (head)
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 4
 
56 is deleted from the linked list from head position
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->34 -> 22 -> 12 -> 23 -> 45-> Tail ->34 (head)
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 5
 
45 is deleted from the linked list from tail position
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->34 -> 22 -> 12 -> 23-> Tail ->34 (head)
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 6
 
Enter the position from where you want to delete element in the list: 3
 
12 is deleted from 3-th position from the linked list
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->34 -> 22 -> 23-> Tail ->34 (head)
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 8
 
Do you want to continue (y/n) ?:n

No comments :

Post a Comment