UNIT-4

Linked list

Linked list is a linear data structure that includes a series of connected nodes. Linked list
can be defined as the nodes that are randomly stored in the memory. A node in the linked
list contains two parts, i.e., first is the data part and second is the address part. The last node
of the list contains a pointer to the null. After array, linked list is the second most used data
structure. In a linked list, every link contains a connection to another link.

Representation of a Linked list

Linked list can be represented as the connection of nodes in which each node points to the
next node of the list. The representation of the linked list is shown below -

Till now, we have been using array data structure to organize the group of elements that
are to be stored individually in the memory. However, Array has several advantages and
disadvantages that must be known to decide the data structure that will be used throughout
the program.

Why use linked list over array?

Linked list is a data structure that overcomes the limitations of arrays. Let's first see some
of the limitations of arrays -
o The size of the array must be known in advance before using it in the program.
o Increasing the size of the array is a time taking process. It is almost impossible to
expand the size of the array at run time.
o All the elements in the array need to be contiguously stored in the memory. Inserting
an element in the array needs shifting of all its predecessors.
Linked list is useful because -
o It allocates the memory dynamically. All the nodes of the linked list are non-
contiguously stored in the memory and linked together with the help of pointers.
o In linked list, size is no longer a problem since we do not need to define its size at
the time of declaration. List grows as per the program's demand and limited to the
available memory space.
How to declare a linked list?
It is simple to declare an array, as it is of single type, while the declaration of linked list is
a bit more typical than array. Linked list contains two parts, and both are of different types,
i.e., one is the simple variable, while another is the pointer variable. We can declare the
linked list by using the user-defined data type structure.
The declaration of linked list is given as follows -
1. struct node
2. {
3. int data;
4. struct node *next;
5. }
In the above declaration, we have defined a structure named as node that contains two
variables, one is data that is of integer type, and another one is next that is a pointer which
contains the address of next node.

Types of Linked list

Linked list is classified into the following types –

o Singly-linked list - Singly linked list can be defined as the collection of an ordered
set of elements. A node in the singly linked list consists of two parts: data part and
link part. Data part of the node stores actual information that is to be represented by
the node, while the link part of the node stores the address of its immediate successor.
o 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), and pointer to the previous node
(previous pointer).
o 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.
o Circular doubly linked list - Circular doubly linked list is a more complex type of
data structure in which a node contains pointers to its previous node as well as the
next node. Circular doubly linked list doesn't contain NULL in any of the nodes. The
last node of the list contains the address of the first node of the list. The first node of
the list also contains the address of the last node in its previous pointer.

Advantages of Linked list

The advantages of using the Linked list are given as follows -
o Dynamic data structure - The size of the linked list may vary according to the
requirements. Linked list does not have a fixed size.
 o Insertion and deletion - Unlike arrays, insertion, and deletion in linked list is easier.
Array elements are stored in the consecutive location, whereas the elements in the
linked list are stored at a random location. To insert or delete an element in an array,
we have to shift the elements for creating the space. Whereas, in linked list, instead
of shifting, we just have to update the address of the pointer of the node.
o Memory efficient - The size of a linked list can grow or shrink according to the
requirements, so memory consumption in linked list is efficient.
o Implementation - We can implement both stacks and queues using linked list.

Disadvantages of Linked list

The limitations of using the Linked list are given as follows -
o Memory usage - In linked list, node occupies more memory than array. Each node
of the linked list occupies two types of variables, i.e., one is a simple variable, and
another one is the pointer variable.
o Traversal - Traversal is not easy in the linked list. If we have to access an element
in the linked list, we cannot access it randomly, while in case of array we can
randomly access it by index. For example, if we want to access the 3rd node, then
we need to traverse all the nodes before it. So, the time required to access a particular
node is large.
o Reverse traversing - Backtracking or reverse traversing is difficult in a linked list.
In a doubly-linked list, it is easier but requires more memory to store the back
pointer.

Applications of Linked list

The applications of the Linked list are given as follows -
o With the help of a linked list, the polynomials can be represented as well as we can
perform the operations on the polynomial.
o A linked list can be used to represent the sparse matrix.
o The various operations like student's details, employee's details, or product details
can be implemented using the linked list as the linked list uses the structure data type
that can hold different data types.
o Using linked list, we can implement stack, queue, tree, and other various data
structures.
o The graph is a collection of edges and vertices, and the graph can be represented as
an adjacency matrix and adjacency list. If we want to represent the graph as an
adjacency matrix, then it can be implemented as an array. If we want to represent
the graph as an adjacency list, then it can be implemented as a linked list.
o A linked list can be used to implement dynamic memory allocation. The dynamic
memory allocation is the memory allocation done at the run-time.
Operations performed on Linked list
The basic operations that are supported by a list are mentioned as follows -
o Insertion - This operation is performed to add an element into the list.
o Deletion - It is performed to delete an operation from the list.
o Display - It is performed to display the elements of the list.
o Search - It is performed to search an element from the list using the given key.

Types of Linked list

The following are the types of linked list:
o Singly Linked list
o Doubly Linked list
o Circular Linked list
o Doubly Circular Linked list

Singly Linked list

It is the commonly used linked list in programs. If we are talking about the linked list, it
means it is a singly linked list. The singly linked list is a data structure that contains two
parts, i.e., one is the data part, and the other one is the address part, which contains the
address of the next or the successor node. The address part in a node is also known as
a pointer.
Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:

We can observe in the above figure that there are three different nodes having address 100,
200 and 300 respectively. The first node contains the address of the next node, i.e., 200,
the second node contains the address of the last node, i.e., 300, and the third node contains
the NULL value in its address part as it does not point to any node. The pointer that holds
the address of the initial node is known as a head pointer.
The linked list, which is shown in the above diagram, is known as a singly linked list as it
contains only a single link. In this list, only forward traversal is possible; we cannot traverse
in the backward direction as it has only one link in the list.
Representation of the node in a singly linked list
struct node
{
int data;
struct node *next;
}
In the above representation, we have defined a user-defined structure named
a node containing two members, the first one is data of integer type, and the other one is
the pointer (next) of the node type.

Doubly linked list

As the name suggests, the doubly linked list contains two pointers. We can define the
doubly linked list as a linear data structure with three parts: the data part and the other two
address part. In other words, a doubly linked list is a list that has three parts in a single
node, includes one data part, a pointer to its previous node, and a pointer to the next node.
Suppose we have three nodes, and the address of these nodes are 100, 200 and 300,
respectively. The representation of these nodes in a doubly-linked list is shown below:

As we can observe in the above figure, the node in a doubly-linked list has two address
parts; one part stores the address of the next while the other part of the node stores
the previous node's address. The initial node in the doubly linked list has the NULL value
in the address part, which provides the address of the previous node.

Representation of the node in a doubly linked list

struct node
{
int data;
struct node *next;
struct node *prev;
}
In the above representation, we have defined a user-defined structure named a node with
three members, one is data of integer type, and the other two are the pointers, i.e., next
and prev of the node type. The next pointer variable holds the address of the next node,
and the prev pointer holds the address of the previous node. The type of both the pointers,
i.e., next and prev is struct node as both the pointers are storing the address of the node
of the struct node type.

Circular linked list

A circular linked list is a variation of a singly linked list. The only difference between
the singly linked list and a circular linked list is that the last node does not point to any
node in a singly linked list, so its link part contains a NULL value. On the other hand, the
circular linked list is a list in which the last node connects to the first node, so the link part
of the last node holds the first node's address. The circular linked list has no starting and
ending node. We can traverse in any direction, i.e., either backward or forward. The
diagrammatic representation of the circular linked list is shown below:
struct node
{
int data;
struct node *next;
}
A circular linked list is a sequence of elements in which each node has a link to the next
node, and the last node is having a link to the first node. The representation of the circular
linked list will be similar to the singly linked list, as shown below:

Doubly Circular linked list

The doubly circular linked list has the features of both the circular linked list and doubly
linked list.
The above figure shows the representation of the doubly circular linked list in which the
last node is attached to the first node and thus creates a circle. It is a doubly linked list also
because each node holds the address of the previous node also. The main difference
between the doubly linked list and doubly circular linked list is that the doubly circular
linked list does not contain the NULL value in the previous field of the node. As the doubly
circular linked contains three parts, i.e., two address parts and one data part so its
representation is similar to the doubly linked list.
struct node
{
int data;
struct node *next;
struct node *prev;
}

Singly linked list or One way chain

Singly linked list can be defined as the collection of ordered set of elements. The number
of elements may vary according to need of the program. A node in the singly linked list
consist of two parts: data part and link part. Data part of the node stores actual information
that is to be represented by the node while the link part of the node stores the address of its
immediate
One way chain or singly linked list can be traversed only in one direction. In other words,
we can say that each node contains only next pointer, therefore we can not traverse the list
in the reverse direction.
Consider an example where the marks obtained by the student in three subjects are stored
in a linked list as shown in the figure.
In the above figure, the arrow represents the links. The data part of every node contains the
marks obtained by the student in the different subject. The last node in the list is identified
by the null pointer which is present in the address part of the last node. We can have as
many elements we require, in the data part of the list.

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such
operations is given below.

Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));

Insertion
The insertion into a singly linked list can be performed at different positions. Based on the
position of the new node being inserted, the insertion is categorized into the following
categories.
SN Operation Description

1 Insertion at It involves inserting any element at the front of the list. We

beginning just need to a few link adjustments to make the new node as
the head of the list.

2 Insertion at end It involves insertion at the last of the linked list. The new node
of the list can be inserted as the only node in the list or it can be inserted
as the last one. Different logics are implemented in each
scenario.
 3 Insertion after It involves insertion after the specified node of the linked list.
specified node We need to skip the desired number of nodes in order to reach
the node after which the new node will be inserted. .

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions.
Based on the position of the node being deleted, the operation is categorized into the
following categories.
SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list.

beginning This is the simplest operation among all. It just need a few
adjustments in the node pointers.

2 Deletion at the It involves deleting the last node of the list. The list can either
end of the list be empty or full. Different logic is implemented for the
different scenarios.

3 Deletion after It involves deleting the node after the specified node in the
specified node list. we need to skip the desired number of nodes to reach the
node after which the node will be deleted. This requires
traversing through the list.

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

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

Linked List in C: Menu Driven Program

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

void beginsert ();

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)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4
.Delete from Beginning\n
5.Delete from last\n6.Delete node after specified location\n7.Search for an eleme
nt\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
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..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}
}
void lastinsert()
{
 struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
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=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
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("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
 struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\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=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
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=0,flag;
ptr = head;
if(ptr == NULL)
{
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("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
 }

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}

Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

1

Enter value
1

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

2

Enter value?
2

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

3
Enter element value1

Enter the location after which you want to insert 1

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

8

printing values . . . . .

1
2
1

*********Main Menu*********

Choose one option from the following list ...

===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

2

Enter value?
123

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

1

Enter value
1234

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

4

Node deleted from the begining ...

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

5

Deleted Node from the last ...

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
6

Enter the location of the node after which you want to perform deletion
1

Deleted node 2

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

8

printing values . . . . .

1
1

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

7

Enter item which you want to search?

1
item found at location 1
item found at location 2

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice?

9

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.

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

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. }
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
expansive 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.
Operations on doubly linked list
Node Creation
1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. };
7. struct node *head;
All the remaining operations regarding doubly linked list are described in the following
table.
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 Adding the node into the linked list after the specified
specified node 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.

6 Deletion of the node Removing the node which is present just after the node
having given data containing the given data.

7 Searching Comparing each node data with the item to be searched

and 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 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;
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("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4
.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();
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
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
 head=ptr;
}
else
{
ptr->data=item;
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;
ptr->prev = NULL;
head = ptr;
}
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
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
 }
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
 ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
 ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
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+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}
 }

Output
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value12

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value123

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value1234

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
1234
123
12

*********Main Menu*********
Choos one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

2

Enter value89
node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

3
Enter the location1
Enter value12345

node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
1234
123
12345
12
89

*********Main Menu*********

Choose one option from the following list ...

===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

4

node deleted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

5
node deleted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
123
12345

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

6

Enter the data after which the node is to be deleted : 123

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
123

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert n begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

7

Enter item which you want to search?

123

item found at location 1

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

6
Enter the data after which the node is to be deleted : 123
Can't delete

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

9

Exited..

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 liked 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.
We can also have more than one number of linked list in the memory with the different
start pointers pointing to the different start nodes in the list. The last node is identified by
its next part which contains the address of the start node of the list. 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:
Insertion
SN Operation Description

1 Insertion at beginning Adding a node into circular singly linked list at the
beginning.

2 Insertion at the end Adding a node into circular singly linked list at the end.
Deletion & Traversing
SN Operation Description

1 Deletion at Removing the node from circular singly linked list at the
beginning beginning.

2 Deletion at the Removing the node from circular singly linked list at the end.
end

3 Searching Compare each element of the node with the given item and
return the location at which the item is present in the list
otherwise return null.

4 Traversing Visiting each element of the list at least once in order to

perform some specific operation.

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;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();

void main ()
{
int choice =0;
 while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delet
e from last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}

void beginsert()
{
 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;
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;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}
printf("\nnode inserted\n");
}
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
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)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");
}
}

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

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

Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

1

Enter the node data?10

node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

2

Enter Data?20
node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

2

Enter Data?30
node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

3

node deleted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

4

node deleted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

5

Enter item which you want to search?

20
item found at location 1

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

6

printing values ...

20

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

7

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in which a node
contain pointers to its previous node as well as the next node. Circular doubly linked list
doesn't contain NULL in any of the node. The last node of the list contains the address of
the first node of the list. The first node of the list also contain address of the last node in its
previous pointer.
A circular doubly linked list is shown in the following figure.
Due to the fact that a circular doubly linked list contains three parts in its structure
therefore, it demands more space per node and more expensive basic operations. However,
a circular doubly linked list provides easy manipulation of the pointers and the searching
becomes twice as efficient.
Memory Management of Circular Doubly linked list
The following figure shows the way in which the memory is allocated for a circular doubly
linked list. The variable head contains the address of the first element of the list i.e. 1 hence
the starting node of the list contains data A is stored at address 1. Since, each node of the
list is supposed to have three parts therefore, the starting node of the list contains address
of the last node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at
address 8 and containing data as 6, contains address of the first node of the list as shown in
the image i.e. 1. In circular doubly linked list, the last node is identified by the address of
the first node which is stored in the next part of the last node therefore the node which
contains the address of the first node, is actually the last node of the list.
Operations on circular doubly linked list :
There are various operations which can be performed on circular doubly linked list. The
node structure of a circular doubly linked list is similar to doubly linked list. However, the
operations on circular doubly linked list is described in the following table.
SN Operation Description

1 Insertion at beginning Adding a node in circular doubly linked list at the

beginning.

2 Insertion at end Adding a node in circular doubly linked list at the end.

3 Deletion at beginning Removing a node in circular doubly linked list from

beginning.
 4 Deletion at end Removing a node in circular doubly linked list at the
end.
Traversing and searching in circular doubly linked list is similar to that in the circular singly
linked list.

C program to implement all the operations on circular doubly linked list

#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.Del
ete 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");
}
}
}

Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

1

Enter Item value123

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

2

Enter value234
node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

1

Enter Item value90

Node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

2
Enter value80
node inserted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

3

*********Main Menu*********
Choose one option from the following list ...
==============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

4
node deleted

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

6

printing values ...

123

*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

5

Enter item which you want to search?

123
item found at location 1

*********Main Menu*********
Choose one option from the following list ...
============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?

7