Data Structures and Applications (CS204) Module 3

3.4 Circular Singly Linked List

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We
can have circular singly linked list as well as circular doubly linked list.

We traverse a circular singly linked list until we reach the same node where we started. The circular
singly linked list has no beginning and no ending. There is no null value present in the next part of any of
the nodes.

The following image shows a circular singly linked list.

Circular linked list are mostly used in task maintenance in operating systems. There are many examples
where circular linked list are being used in computer science including browser surfing where a record of
pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed
again on clicking the previous button.

Memory Representation of circular linked list:

In the following image, memory representation of a circular linked list containing marks of a student in 4
subjects. However, the image shows a glimpse of how the circular list is being stored in the memory. The
start or head of the list is pointing to the element with the index 1 and containing 13 marks in the data
part and 4 in the next part. Which means that it is linked with the node that is being stored at 4th index of
the list.

However, due to the fact that we are considering circular linked list in the memory therefore the last node
of the list contains the address of the first node of the list.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 17

Data Structures and Applications (CS204) Module 3

We must be able to identify the last node of any linked list so that we can find out the number of
iterations which need to be performed while traversing the list.
Operations on Circular Singly linked list:
SN Operation Description

Insertion at
beginning It involves inserting any element at the front of the list. We just need to a few
1
link adjustments to make the new node as the head of the list.

Insertion at
2 It involves insertion at the last of the linked list.
end of the list

Insertion after It involves insertion after the specified node of the linked list. We need to skip
3 specified the desired number of nodes in order to reach the node after which the new node
node will be inserted.

Deletion at It involves deletion of a node from the beginning of the list. It just need a few
4 beginning adjustments in the node pointers.

Deletion at the
5 end of the list
It involves deleting the last node of the list.

6 Deletion after It involves deleting the node after the specified node in the list. We need to skip

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 18

 Data Structures and Applications (CS204) Module 3

specified node
the desired number of nodes to reach the node after which the node will be
deleted. This requires traversing through the list.

Traversing In traversing, we simply visit each node of the list at least once in order to
7 perform some specific operation on it, for example, printing data part of each
node present in the list.

Searching
In searching, we match each element of the list with the given element. If the
8 element is found on any of the location then location of that element is returned
otherwise null is returned.

Menu-driven program in C implementing all operations on circular singly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;

void begin_insert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 19

 Data Structures and Applications (CS204) Module 3

{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search f
or an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
begin_insert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 20

 Data Structures and Applications (CS204) Module 3

}
}
}
void begin_insert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}

}
void lastinsert()
{
struct node *ptr,*temp;

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 21

 Data Structures and Applications (CS204) Module 3

int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
printf("\nnode inserted\n");

}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
printf("\nnode inserted\n");
}

}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 22

 Data Structures and Applications (CS204) Module 3

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=1;i<loc;i++)
{
temp = temp->next;
if(temp == head)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
ptr=head;

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 23

 Data Structures and Applications (CS204) Module 3

free(ptr);
head=NULL;
printf("\nnode deleted\n");
}

else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");

}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
ptr = head;
free(ptr);
head=NULL;
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 24

 Data Structures and Applications (CS204) Module 3

preptr->next = ptr -> next;

free(ptr);
printf("\nnode deleted\n");

}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=1;i<=loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == head)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}

void search()
{
struct node *ptr;
int item,i=1,flag=0;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 25

 Data Structures and Applications (CS204) Module 3

{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i);
flag=1;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i);
flag=1;
break;
}
i++;
ptr = ptr -> next;
}
}
if(flag == 0)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr=head;
int count=0;
if(head == NULL)
{
printf("\nnothing to print");

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 26

 Data Structures and Applications (CS204) Module 3

else
{
printf("\n printing values ... \n");
count=1;
while(ptr -> next != head)
{

count=count+1;
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
printf("\n The number of nodes %d",count);
}

}
3.5 Doubly linked list
Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as
well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts:
node data, pointer to the next node in sequence (next pointer), pointer to the previous node (previous
pointer). A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the
following image.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 27

Data Structures and Applications (CS204) Module 3

In C, structure of a node in doubly linked list can be given as :

struct node
{
struct node *prev;
int data;
struct node *next;
};

The prev part of the first node and the next part of the last node will always contain null indicating end in
each direction.

In a singly linked list, we could traverse only in one direction, because each node contains address of the
next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this
limitation of singly linked list. Due to the fact that, each node of the list contains the address of its
previous node, we can find all the details about the previous node as well by using the previous address
stored inside the previous part of each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image. Generally, doubly
linked list consumes more space for every node and therefore, causes more expensive basic operations
such as insertion and deletion. However, we can easily manipulate the elements of the list since the list
maintains pointers in both the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer
points to the starting address 1. Since this is the first element being added to the list therefore the prev of
the list contains null. The next node of the list resides at address 4 therefore the first node contains 4 in
its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next part.

Node Creation

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 28

 Data Structures and Applications (CS204) Module 3

struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head=NULL;
Operations on doubly linked list
SN Operation Description

1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after specified node Adding the node into the linked list after the specified node.

4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.

Removing the node which is present just after the given

6 Deletion of the specified node
location.

Comparing each node data with the item to be searched and

7 Searching return the location of the item in the list if the item found else
return null.

8 Traversing Visiting each node of the list at least once in order to perform

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 29

 Data Structures and Applications (CS204) Module 3

some specific operation like searching, sorting, display, etc.

Menu Driven Program in C to implement all the operations of doubly linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head=NULL;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n 4.
Delete from Beginning\n 5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\
n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 30

 Data Structures and Applications (CS204) Module 3

break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 31

 Data Structures and Applications (CS204) Module 3

printf("\nEnter Item value");

scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
head=ptr;
printf("\nnode inserted\n");
}
else
{
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
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)
{
ptr->next = NULL;

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 32

 Data Structures and Applications (CS204) Module 3

ptr->prev = NULL;
head = ptr;
printf("\nnode inserted\n");
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
printf("\nnode inserted\n");
}
}
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
printf("Enter the location");
scanf("%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 33

 Data Structures and Applications (CS204) Module 3

if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
ptr->next->prev=ptr;
printf("\nnode inserted\n");
}
}

void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n List is empty");
}
else if(head->next == NULL)
{
ptr=head;
free(ptr);
head = NULL;
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 34

 Data Structures and Applications (CS204) Module 3

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n List is empty ");
}
else if(head->next == NULL)
{
ptr=head;
head = NULL;
free(ptr);
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=1;i<=loc;i++)
{
ptr = ptr->next;
if(ptr == NULL)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 35

 Data Structures and Applications (CS204) Module 3

{
printf("\nCan't delete");
return;
}
}
ptr->prev->next=ptr->next;
ptr->next->prev=ptr->prev;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void display() //Same as Singly Linked List display() function
{
int count=0;
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
count++;
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
printf("\n The number of nodes %d",count);
}
}
void search() //Same as Singly List List search() function
{
struct node *ptr;
int item,i=1,flag=0;
ptr = head;
if(ptr == NULL)
{

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 36

 Data Structures and Applications (CS204) Module 3

printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i);
flag=1;
break;
}
i++;
ptr = ptr -> next;
}
if(flag==0)
{
printf("\nItem not found\n");
}
}
}

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 37