November 30, 2019
Amitraj
Circular linked list data structure
-> In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
-> Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.
Applications of Circular Linked List
1. Example of Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
2. Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.
-> In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
-> Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.
Applications of Circular Linked List
1. Example of Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
2. Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.
/* C Program to Demonstrate Circular Linked List */
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *head = NULL, *x, *y, *z;
void create();
void ins_at_beg();
void ins_at_pos();
void del_at_beg();
void del_at_pos();
void traverse();
void search();
void update();
void rev_traverse(struct node *p);
void main()
{
int ch;
printf("\n 1.Creation \n 2.Insertion at beginning \n 3.Insertion at remaining");
printf("\n4.Deletion at beginning \n5.Deletion at remaining \n6.traverse");
printf("\n7.Search\n8.update\n9.reverse traverse\n10.Exit");
while (1)
{
printf("\n Enter your choice:");
scanf("%d", &ch);
switch(ch)
{
case 1: create(); break;
case 2: ins_at_beg(); break;
case 3: ins_at_pos(); break;
case 4: del_at_beg(); break;
case 5: del_at_pos(); break;
case 6: traverse(); break;
case 7: search(); break;
case 8: update(); break;
case 9: rev_traverse(head); break;
default: exit(0);
}
}
}
/*Function to create a new circular linked list*/
void create()
{
int c;
x = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &x->data);
x->link = x;
head = x;
printf("\n If you wish to continue press 1 otherwise 0:");
scanf("%d", &c);
while (c != 0)
{
y = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &y->data);
x->link = y;
y->link = head;
x = y;
printf("\n If you wish to continue press 1 otherwise 0:");
scanf("%d", &c);
}
}
/*Function to insert an element at the begining of the list*/
void ins_at_beg()
{
x = head;
y = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &y->data);
while (x->link != head)
{
x = x->link;
}
x->link = y;
y->link = head;
head = y;
}
/*Function to insert an element at any position the list*/
void ins_at_pos()
{
struct node *ptr;
int c = 1, pos, count = 1;
y = (struct node*)malloc(sizeof(struct node));
if (head == NULL)
{
printf("cannot enter an element at this place");
}
printf("\n Enter the data:");
scanf("%d", &y->data);
printf("\n Enter the position to be inserted:");
scanf("%d", &pos);
x = head;
ptr = head;
while (ptr->link != head)
{
count++;
ptr = ptr->link;
}
count++;
if (pos > count)
{
printf("OUT OF BOUND");
return;
}
while (c < pos)
{
z = x;
x = x->link;
c++;
}
y->link = x;
z->link = y;
}
/*Function to delete an element at any begining of the list*/
void del_at_beg()
{
if (head == NULL)
printf("\n List is empty");
else
{
x = head;
y = head;
while (x->link != head)
{
x = x->link;
}
head = y->link;
x->link = head;
free(y);
}
}
/*Function to delete an element at any position the list*/
void del_at_pos()
{
if (head == NULL)
printf("\n List is empty");
else
{
int c = 1, pos;
printf("\n Enter the position to be deleted:");
scanf("%d", &pos);
x = head;
while (c < pos)
{
y = x;
x = x->link;
c++;
}
y->link = x->link;
free(x);
}
}
/*Function to display the elements in the list*/
void traverse()
{
if (head == NULL)
printf("\n List is empty");
else
{
x = head;
while (x->link != head)
{
printf("%d->", x->data);
x = x->link;
}
printf("%d", x->data);
}
}
/*Function to search an element in the list*/
void search()
{
int search_val, count = 0, flag = 0;
printf("\nenter the element to search\n");
scanf("%d", &search_val);
if (head == NULL)
printf("\nList is empty nothing to search");
else
{
x = head;
while (x->link != head)
{
if (x->data == search_val)
{
printf("\nthe element is found at %d", count);
flag = 1;
break;
}
count++;
x = x->link;
}
if (x->data == search_val)
{
printf("element found at postion %d", count);
}
if (flag == 0)
{
printf("\nelement not found");
}
}
}
/*Function to update an element at any position the list*/
void update()
{
struct node *ptr;
int search_val;
int replace_val;
int flag = 0;
if (head == NULL)
{
printf("\n empty list");
}
else
{
printf("enter the value to be edited\n");
scanf("%d", &search_val);
fflush(stdin);
printf("enter the value to be replace\n");
scanf("%d", &replace_val);
ptr = head;
while (ptr->link != head)
{
if (ptr->data == search_val)
{
ptr->data = replace_val;
flag = 1;
break;
}
ptr = ptr->link;
}
if (ptr->data == search_val)
{
ptr->data = replace_val;
flag = 1;
}
if (flag == 1)
{
printf("\nUPdate sucessful");
}
else
{
printf("\n update not successful");
}
}
}
/*Function to display the elements of the list in reverse order*/
void rev_traverse(struct node *p)
{
int i = 0;
if (head == NULL)
{
printf("empty linked list");
}
else
{
if (p->link != head)
{
i = p->data;
rev_traverse(p->link);
printf(" %d", i);
}
if (p->link == head)
{
printf(" %d", p->data);
}
}
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *head = NULL, *x, *y, *z;
void create();
void ins_at_beg();
void ins_at_pos();
void del_at_beg();
void del_at_pos();
void traverse();
void search();
void update();
void rev_traverse(struct node *p);
void main()
{
int ch;
printf("\n 1.Creation \n 2.Insertion at beginning \n 3.Insertion at remaining");
printf("\n4.Deletion at beginning \n5.Deletion at remaining \n6.traverse");
printf("\n7.Search\n8.update\n9.reverse traverse\n10.Exit");
while (1)
{
printf("\n Enter your choice:");
scanf("%d", &ch);
switch(ch)
{
case 1: create(); break;
case 2: ins_at_beg(); break;
case 3: ins_at_pos(); break;
case 4: del_at_beg(); break;
case 5: del_at_pos(); break;
case 6: traverse(); break;
case 7: search(); break;
case 8: update(); break;
case 9: rev_traverse(head); break;
default: exit(0);
}
}
}
/*Function to create a new circular linked list*/
void create()
{
int c;
x = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &x->data);
x->link = x;
head = x;
printf("\n If you wish to continue press 1 otherwise 0:");
scanf("%d", &c);
while (c != 0)
{
y = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &y->data);
x->link = y;
y->link = head;
x = y;
printf("\n If you wish to continue press 1 otherwise 0:");
scanf("%d", &c);
}
}
/*Function to insert an element at the begining of the list*/
void ins_at_beg()
{
x = head;
y = (struct node*)malloc(sizeof(struct node));
printf("\n Enter the data:");
scanf("%d", &y->data);
while (x->link != head)
{
x = x->link;
}
x->link = y;
y->link = head;
head = y;
}
/*Function to insert an element at any position the list*/
void ins_at_pos()
{
struct node *ptr;
int c = 1, pos, count = 1;
y = (struct node*)malloc(sizeof(struct node));
if (head == NULL)
{
printf("cannot enter an element at this place");
}
printf("\n Enter the data:");
scanf("%d", &y->data);
printf("\n Enter the position to be inserted:");
scanf("%d", &pos);
x = head;
ptr = head;
while (ptr->link != head)
{
count++;
ptr = ptr->link;
}
count++;
if (pos > count)
{
printf("OUT OF BOUND");
return;
}
while (c < pos)
{
z = x;
x = x->link;
c++;
}
y->link = x;
z->link = y;
}
/*Function to delete an element at any begining of the list*/
void del_at_beg()
{
if (head == NULL)
printf("\n List is empty");
else
{
x = head;
y = head;
while (x->link != head)
{
x = x->link;
}
head = y->link;
x->link = head;
free(y);
}
}
/*Function to delete an element at any position the list*/
void del_at_pos()
{
if (head == NULL)
printf("\n List is empty");
else
{
int c = 1, pos;
printf("\n Enter the position to be deleted:");
scanf("%d", &pos);
x = head;
while (c < pos)
{
y = x;
x = x->link;
c++;
}
y->link = x->link;
free(x);
}
}
/*Function to display the elements in the list*/
void traverse()
{
if (head == NULL)
printf("\n List is empty");
else
{
x = head;
while (x->link != head)
{
printf("%d->", x->data);
x = x->link;
}
printf("%d", x->data);
}
}
/*Function to search an element in the list*/
void search()
{
int search_val, count = 0, flag = 0;
printf("\nenter the element to search\n");
scanf("%d", &search_val);
if (head == NULL)
printf("\nList is empty nothing to search");
else
{
x = head;
while (x->link != head)
{
if (x->data == search_val)
{
printf("\nthe element is found at %d", count);
flag = 1;
break;
}
count++;
x = x->link;
}
if (x->data == search_val)
{
printf("element found at postion %d", count);
}
if (flag == 0)
{
printf("\nelement not found");
}
}
}
/*Function to update an element at any position the list*/
void update()
{
struct node *ptr;
int search_val;
int replace_val;
int flag = 0;
if (head == NULL)
{
printf("\n empty list");
}
else
{
printf("enter the value to be edited\n");
scanf("%d", &search_val);
fflush(stdin);
printf("enter the value to be replace\n");
scanf("%d", &replace_val);
ptr = head;
while (ptr->link != head)
{
if (ptr->data == search_val)
{
ptr->data = replace_val;
flag = 1;
break;
}
ptr = ptr->link;
}
if (ptr->data == search_val)
{
ptr->data = replace_val;
flag = 1;
}
if (flag == 1)
{
printf("\nUPdate sucessful");
}
else
{
printf("\n update not successful");
}
}
}
/*Function to display the elements of the list in reverse order*/
void rev_traverse(struct node *p)
{
int i = 0;
if (head == NULL)
{
printf("empty linked list");
}
else
{
if (p->link != head)
{
i = p->data;
rev_traverse(p->link);
printf(" %d", i);
}
if (p->link == head)
{
printf(" %d", p->data);
}
}
}
OUTPUT:-
1.Creation
2.Insertion at beginning
3.Insertion at remaining
4.Deletion at beginning
5.Deletion at remaining
6.traverse
7.Search
8.update
9.reverse traverse
10.Exit
Enter your choice:1
Enter the data:11
If you wish to continue press 1 otherwise 0:1
Enter the data:22
If you wish to continue press 1 otherwise 0:1
Enter the data:33
If you wish to continue press 1 otherwise 0:1
Enter the data:4
If you wish to continue press 1 otherwise 0:0
Enter your choice:6
11->22->33->4
Enter your choice:9
4 33 22 11
Enter your choice:7
enter the element to search
33
the element is found at 2element found at postion 2
Enter your choice:7
enter the element to search
85
element not found
Enter your choice:8
enter the value to be edited
4
enter the value to be replace
55
UPdate sucessful
Enter your choice:6
11->22->33->55
Enter your choice:9
55 33 22 11
Enter your choice:2
Enter the data:89
Enter your choice:6
89->11->22->33->55
Enter your choice:3
Enter the data:63
Enter the position to be inserted:3
Enter your choice:6
89->11->63->22->33->55
Enter your choice:4
Enter your choice:6
11->63->22->33->55
Enter your choice:5
Enter the position to be deleted:2
Enter your choice:6
11->22->33->55
Enter your choice:9
55 33 22 11
Enter your choice:10
...
