Circular Linked List

We have discussed singly and double linked list already. So it is recommended to go through it before this blog. Circular Linked List is a linked list where all nodes are connected to form a circle. There is no NULL at the end unlike latter. It can be of two forms circular and doubly circular linked lists. Implementation using C: #include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *link;
};

struct node *head = NULL, *x, *y, *z;

void create();
void insert_at_beg();
void insert_at_pos();
void delete_at_beg();
void delete_at_pos();
void traverse();
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("\n 4.Deletion at beginning \n 5.Deletion at remaining \n 6.traverse");
printf("\n 7.Exit\n");
while (1)
{
printf("\n Enter your choice:");
scanf("%d", &ch);
switch(ch)
{
case 1:
create();
break;
case 2:
insert_at_beg();
break;
case 3:
insert_at_pos();
break;
case 4:
delete_at_beg();
break;
case 5:
delete_at_pos();
break;
case 6:
traverse();
break;
case 7:
rev_traverse(head);
break;
default:
exit(0);
}
}
}

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

void insert_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;
}

void insert_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;
}

void delete_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);
}
}

void delete_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);
}
}

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

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);
}
}
} Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem Follow Programmers Door for more. #blog #interview #placement #circular #linked #list

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door