C program to perform different operations on a singly linked list

Program Statement : 
Write a C program to perform the following operations on a singly linked list :-
● Insertion.
● Deletion.
● Display.
● Sort.
● Reverse
● Split

Theory :
In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
Linked list is called a dynamic data structure where the amount of memory required can be varied during its use. In the linked list, adjacency between the elements is maintained by means of links or pointers. A link or pointer is the address (memory location) of the subsequent element.
An element in a linked list is specially termed as node which consists of two fields :
1. Data-to store the actual information.
2. Link-to point to the next node.
Linked list can be classified in three major groups :

Algorithm:
● Insertion
/*getnode(), which is used in all insertion algorithms, is a function which allocates the required memory space for creating a node*/
/*In all insertion algorithms address of the head pointer and the data to be inserted are passed as parameters; Algo_insgen which inserts a node at any position takes one extra parameter - the position where a node is to be inserted.*/
/*Algorithm to insert a node in the starting position of the linked list*/
Algo_insbeg(head,data)
{
/*The address of the newly created node is assigned to a node type pointer t*/
Step1: t = getnode();
Step2: t->data = data;
Step3: t->next = head;
Step4: head = t;
}

/*Algorithm to insert a node in the ending position of the linked list*/
Algo_insend(head,data)
{
if(head=NULL) /*The list is empty*/
{
Algo_insbeg(head,data);
exit;
}
Step1: Traverse the list until last node is reached;
/*The address of the newly created node is assigned to a node type pointer t*/
Step 2: t = getnode();
Step 3: t->data = data;
Step 4: t->next = NULL;
}

/*Algorithm to insert a node at any position of the linked list*/
Algo_insgen(head,data,pos)
{
Step1: Traverse the list until the previous node of the required position is reached;
Step 2: tmp = getnode();
Step 3: tmp->data = data;
Step 4: tmp->next = t;
Step 5: t = tmp;
}
● Deletion
/*In all deletion algorithms address of the head pointer is passed as parameter; Algo_deleteany which inserts a node at any position takes one extra parameter - the position of the node is to be deleted.*/
/*Algorithm to delete a node from the starting position of the linked list*/
Algo_deletebegin(head)
{
if(head=NULL)
exit;
Step1: p = head; /*p is a node type pointer*/
Step2: data = p->data;
Step3: head = p->next;
Step4: Deallocate the allocated memory space held by p;
return data;
}
/*Algorithm to delete a node from the ending position of the linked list*/
Algo_deleteend(head)
{
if(head=NULL)
exit;
Step1: Traverse the list until previous node of the last node is reached; Step2: p = t; /*p is a node type pointer*/
Step3: data = p->data;
Step4: t = NULL;
Step5: Deallocate the allocated memory space held by p;
return data;
}
/*Algorithm to delete a node from any position of the linked list*/
Algo_deleteany(head,position)
{
Step1: Traverse the list until the previous node of the required position is reached;
Step2: p = t; /*p is a node type pointer*/
Step3: data = p->data;
Step4: t = p->next;
Step5: Deallocate the allocated memory space held by p;
return data;
}
● Display
/*Algorithm to display all the nodes of the linked list*/
disp(head) /*Address of the head pointer is passed as parameter*/
{
print(Start->);
for(t=head;t!=NULL;t=t->next)
print(t->data);
print(NULL);
}
● Sort
/*Algorithm to sort all the nodes of the linked list in ascending order*/
Algo_sort(head) /*Address of the head pointer is passed as parameter*/
{
while(head!=NULL)
{
Step1: Find a node m with maximum data;
Step2: p = m;
Step3: m = m->next;
/*new is a newly created list where deleted maximum node from the
original list is inserted at each iteration*/
Step4: p->next = new;
Step5: new = p;
}
head = new;
}
● Reverse
/*Algorithm to reverse all the nodes of the linked list*/
Algo_reverse(head)
{
/*p, q, r are all node type pointers*/
q = head;
r = NULL;
while(q!=NULL)
{
Step1: head = r;
Step2: r = q;
Step3: q = q->next;
Step4: r->next = s;
}
head = r;
}
● Split

/* THIS ALGORITHM SPLIT THE LINK LIST */

void split(head)
{
struct node *p=head,head1;
int i,non=0;
if(head==NULL)
{
printf("n**********LINK LIST IS EMPTY**********");
return;
}
while(p!=NULL)
{
non++;
p=p->next;
}
for(p=head,i=1;i<non/2;i++)
{
p=p->next;
}
head1=p->next;
p->next=NULL;
printf("n 1st LINK LIST :- n");
disp (head);
printf("n 2nd LINK LIST :-n ");
disp (head1);
}

Program listing :
/*C program to perform insert, delete, display, sort, split and reverse operations on a singly linked list*/
#include<stdio.h>
#include<stdlib.h>
/*A node of the linked list is defined as a structure*/
typedef struct node
{
int data;
struct node*next;
}
node;
void main()
{
node*s=NULL;/*Initially the linked list is empty*/
void disp(node*);
void insbeg(node**,int);
void insend(node**,int);
int insgen(node**,int,int);
int deleteany(node**,int);
int deletebegin(node**);
int deleteend(node**);
void reverse(node**);
void sort(node**);
void split(node*);
int i,n,data,pos,ch,ch_ins,ch_del,con_op,nc,tmp;
nc=0;/*This variable is used to keep track of number of nodes in the linked list*/
printf("..........Linked list operation..........n");
while(1)
{
printf("n..........Main menu..........n");
printf("1.Insertn2.Deleten3.Displayn4.Sortn5.Reversen6.Splitn7.Exit.n");
printf("nEnter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
con_op=1;
while(con_op!=0)
{
printf("Give data : ");
scanf("%d",&data);
printf("n..........List insertion submenu..........n");
printf("1.Insbeg.n2.Insend.n3.Any position.n");
printf("nEnter choice : ");
scanf("%d",&ch_ins);
switch(ch_ins)
{
case 1:
{
insbeg(&s,data);
nc++;
break;
}
case 2:
{
insend(&s,data);
nc++;
break;
}
case 3:
{
nc++;
printf("Enter position : ");
scanf("%d",&pos);
if(pos<0)
{
printf("nInvalid position.n");
nc--;
break;
}
if(insgen(&s,data,pos)==0)
{
printf("nInvalid position");
nc--;
}
break;
}
default:
{
printf("nInvalid choicen");
}
}
printf("nDo you want to continue insertion(if not insert 0) : ");
scanf("%d",&con_op);
}
break;
}
case 2:
{
con_op=1;
while(con_op!=0)
{
if(nc==0)
{
printf("nList is empty.n");
printf("Insert some elements first..!!n");
break;
}
printf("n..........List deletion submenu..........n");
printf("1.Delbeg.n2.Delend.n3.Any position.n");
printf("nEnter choice : ");
scanf("%d",&ch_del);
switch(ch_del)
{
case 1:
{
tmp=deletebegin(&s);
nc--;
break;
}
case 2:
{
tmp=deleteend(&s);
nc--;
break;
}
case 3:
{
nc--;
printf("Enter position to delete : ");
scanf("%d",&pos);
if(pos>=(nc+1)||pos<0)
{
printf("nInvalid position.n");
tmp=-1;
nc++;
break;
}
if((tmp=deleteany(&s,pos))==-1)
{
printf("Invalid position");
nc++;
}
break;
}
default:
{
printf("nInvalid choicen");
}
}
if(tmp!=-1)
printf("Deleted data is : %d",tmp);
printf("nDo you want to continue deletion(if not insert 0) : ");
scanf("%d",&con_op);
}
break;
}
case 3:
{ disp(s);
break;
}
case 4:
{
sort(&s);
printf("Sorted list is : n");
disp(s);
break;
}
case 5:
{
if(nc<2)
{
printf("Two elements must be inserted to visualize reverse operation : n");
break;
}
reverse(&s);
printf("Reversed list is : n");
disp(s);
break;
}
case 6:
{
split(s);
break;
}
case 7:
{
if(nc!=0)/*When list is not empty all the nodes will be deleted*/
{
printf("WARNING!!!!!!!!List is not empty....Nodes will be destroyed.");
while(s!=NULL)
deletebegin(&s);
}
disp(s);
return;
}
default:
printf("Invalid choice givenn");
}
}
}
/*Function to insert a node in the starting position of the linked list*/
void insbeg(node**s,int data)
{
node*t;
t=(node*)malloc(sizeof(node));
t->data=data;
t->next=*s;
*s=t;
}
/*Function to insert a node in the ending position of the linked list*/
void insend(node**s,int data)
{
node**t;
if(*s==NULL)/*The list is empty*/
{
insbeg(s,data);
return;
}
for(t=s;(*t)!=NULL;t=&((*t)->next));
*t=(node*)malloc(sizeof(node));
(*t)->data=data;
(*t)->next=NULL;
}
/*Function to display all the nodes of the linked list*/
void disp(node*s)
{
node*t;
printf("nStart->");
for(t=s;t!=NULL;t=t->next)
printf("%d->",t->data);
printf("NULLn");
}
/**Function to insert a node at any position of the linked list*/
int insgen(node**s,int data,int pos)
{
int i;
node**t;
node*tmp;
for(i=0,t=s;i<pos;i++,t=&((*t)->next))
{
if((*t)==NULL)
return 0;
}
tmp=(node*)malloc(sizeof(node));
tmp->data=data;
tmp->next=(*t);
(*t)=tmp;
}
/*Function to delete a node from the ending position of the linked list*/
int deleteend(node**s)
{
node*p;
node**t;
int dt;
if(*s==NULL)
return -1;
for(t=s;(*t)->next!=NULL;t=&((*t)->next));
p=(*t);
dt=p->data;
(*t)=NULL;
free(p);
return dt;
}
/*Function to delete a node from the starting position of the linked list*/
int deletebegin(node**s)
{
node*p;
int dt;
if(*s==NULL)
return -1;
p=*s;
dt=p->data;
*s=p->next;
free(p);
return dt;
}
/*Function to delete a node from any position of the linked list*/
int deleteany(node**s,int position)
{
node**t;
node*p;
int c=0;
int dt;
for(t=s,c=0;c<position;t=&((*t)->next),c++)
{
if((*t)==NULL)
return -1;
}
p=(*t);
dt=p->data;
(*t)=p->next;
free(p);
return dt;
}
/*Function to reverse all the nodes of the linked list*/
void reverse(node**x)
{
node*q;
node*r;
node*s;
q=*x;
r=NULL;
while(q!=NULL)
{
s=r;
r=q;
q=q->next;
r->next=s;
}
*x=r;
}
/*Function to sort all the nodes of the linked list in ascending order*/
void sort(node**s)
{
node**t;
node**m;
node*p;
node*new=NULL;
while(*s!=NULL)
{
for(t=s,m=s;(*t)!=NULL;t=&((*t)->next))
{
if((*m)->data<(*t)->data)
m=t;
}
p=(*m);
*m=(*m)->next;
p->next=new;
new=p;
}
*s=new;
}
/*Function to split the linked list*/
void split(node *s)
{

struct node *p=s,*s1;
int i,non=0;
if(s==NULL)
{
printf("n**********LINK LIST IS EMPTY**********");
return;
}
while(p!=NULL)
{
non++;
p=p->next;
}
for(p=s,i=1;i<non/2;i++)
{
p=p->next;
}
s1=p->next;
p->next=NULL;
printf("n 1st LINK LIST :- n");
disp(s);
printf("n 2nd LINK LIST :-n ");
disp(s1);
}

Output :
..........Linked list operation..........

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 1
Give data : 45

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 1

Do you want to continue insertion(if not insert 0) : 1
Give data : 22

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 2

Do you want to continue insertion(if not insert 0) : 1
Give data : 15

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 1

Do you want to continue insertion(if not insert 0) : 1
Give data : 89

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 2

Do you want to continue insertion(if not insert 0) : 1
Give data : 51

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 0

Do you want to continue insertion(if not insert 0) : 1
Give data : 77

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 6

Invalid position
Do you want to continue insertion(if not insert 0) : 1
Give data : 56

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 5

Do you want to continue insertion(if not insert 0) : 1
Give data : 78

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 4

Do you want to continue insertion(if not insert 0) : 1
Give data : 12

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 5

Do you want to continue insertion(if not insert 0) : 0

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 3

Start->51->45->15->89->78->12->22->56->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 2

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 1
Deleted data is : 51
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 2
Deleted data is : 56
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 3
Enter position to delete : 2
Deleted data is : 89
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 3
Enter position to delete : 6

Invalid position.

Do you want to continue deletion(if not insert 0) : 0

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 3

Start->45->15->78->12->22->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 4
Sorted list is :

Start->12->15->22->45->78->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 5
Reversed list is :

Start->78->45->22->15->12->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 6
Enter choice : 6

1st LINK LIST :-

Start->78->45->NULL

2nd LINK LIST :-

Start->22->15->12->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice :7
WARNING!!!!!!!!List is not empty....Nodes will be destroyed.
Start->NULL
Discussions :
● In the program, pointers should be manipulated carefully or pointer related errors (such as segmentation fault) may occur.
● The memory which is allocated during the program should be deallocated before exiting from the program.
● To obtain advantages of both doubly and circular linked lists the above program can be implemented using doubly-circular linked list.
● Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in a dynamic array may require moving half of the elements, or more.
● Linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations - such as obtaining the last node of the list, or finding a node that contains a given data, or locating the place where a new node should be inserted - may require scanning most of the list elements.
● Dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only sequential access to elements.
● Singly-linked lists, in fact, can only be traversed in one direction.
● Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items.

Back to main directory:  C Assignment    Software Practical