## Conversion of a Linked List into Array

The conversion process involves creation of a linked list.  Then the list is read from the first node till the last node such that each node value is stored in an array and the node is removed by freeing its memory.  The array is then displayed as an output.

/*Conversion of a linked list into array*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

typedef struct list
{int info;
list *next;
}list;

list *create()
{list *temp=(list *)malloc(sizeof(list));
if(temp==NULL)
{printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

list *makenode(int x)
{list *ptr=create();
ptr->info=x;
ptr->next=NULL;
return ptr;
}

{list *temp,*ptr=makenode(x);
}
else
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
}

{
list *temp;
{printf(“List is empty.”);
return;
}
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

{list *temp;
int ct=0;
while(temp!=NULL)
{ct++;
temp=temp->next;
}
return ct;
}

{
list *temp;
free(temp);
}
}

{int i=0;
while(temp!=NULL)
{arr[i++]=temp->info;
temp=temp->next;
}
}

void main()
{
int i,ch,num,size,arr[MAX]={0};
while(1)
{
clrscr();
printf(“nn1. Create List”);
printf(“n2. Display List”);
printf(“n3. Convert List to Array”);
printf(“n4. Display Array”);
printf(“n5. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number?”);
scanf(“%d”,&num);
break;
case 2:
break;
case 3:
printf(“nConverting List to Array…”);
break;
case 4:
printf(“nDisplaying array elements: “);
for(i=0;i<size;i++)
printf(“%dt”,arr[i]);
printf(“bb “);
break;
case 5:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

## Josephus Algorithm

The problem is described as, “If there are n persons standing in a circle.  Beginning from any person, the others are numbered in a particular direction (clockwise or anti-clockwise).  Then a random number, n is generated.  The counting begins from the person numbered as one upto n.  The nth person is removed from the game so that total number of persons in the circle gets reduced by one.  The same process is continued until one person remains in the circle, who is declared to be the winner.  Circular linked list may be used for representing this problem, which is codified below:

/*Josephus algorithm*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

struct clist
{
int id;
char name;
struct clist *next;

void create()
{
ptr=(struct clist *)malloc(sizeof(struct clist));
if(ptr==NULL)
{
printf(“Memory Allocation Error!”);
exit(1);
}
}

void makenode(int pid,char nm[])
{
create();
ptr->id=pid;
strcpy(ptr->name,nm);
ptr->next=NULL;
}

void insertend()
{
{
}
else
temp=temp->next;
temp->next=ptr;
}
}

void display()
{
{
printf(“List is empty.”);
return;
}

{
return;
}
printf(“(%d,%s)->”,temp->id,temp->name);
temp=temp->next;
{
printf(“(%d,%s)->”,temp->id,temp->name);
temp=temp->next;
}
printf(“bb “);
}

void playgame()
{
int m,i;
struct clist *tmp;
printf(“Enter the value of counter m?”);
scanf(“%d”,&m);
while(temp!=temp->next)
{
for(i=0;i<m-1;i++)
temp=temp->next;
tmp=temp->next;
temp->next=tmp->next;
free(tmp);
}
printf(“Winner of the Game is: (%d,%s)”,temp->id,temp->name);
getch();
}

void main()
{
int choice,id;
char name;
while(1)
{
clrscr();
printf(“ntWhat to do”);
printf(“nnt1. Generate Circular list of persons”);
printf(“nt2. Display List of persons”);
printf(“nt3. Play the Game”);
printf(“nt4. Exit”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“nEnter person id?”);
scanf(“%d”,&id);
printf(“nEnter person name?”);
scanf(“%s”,name);
makenode(id,name);
insertend();
break;
case 2:
display();
getch();
break;
case 3:
playgame();
break;
case 4:
exit(0);
default:
printf(“nInvalid choice.”);
}
}
}

## Polynomial – Representation, Addition, Multiplication

#### Polynomial Manipulation

• Representation
• Multiplication

Representation of a Polynomial:  A polynomial is an expression that contains more than two terms.  A term is made up of coefficient and exponent.  An example of polynomial is

P(x) = 4x3+6x2+7x+9

A polynomial thus may be represented using arrays or linked lists.  Array representation assumes that the exponents of the given expression are arranged from 0 to the highest value (degree), which is represented by the subscript of the array beginning with 0.  The coefficients of the respective exponent are placed at an appropriate index in the array.  The array representation for the above polynomial expression is given below: A polynomial may also be represented using a linked list.  A structure may be defined such that it contains two parts- one is the coefficient and second is the corresponding exponent.  The structure definition may be given as shown below:

struct polynomial
{
int coefficient;
int exponent;
struct polynomial *next;
};

Thus the above polynomial may be represented using linked list as shown below: For adding two polynomials using arrays is straightforward method, since both the arrays may be added up element wise beginning from 0 to n-1, resulting in addition of two polynomials.  Addition of two polynomials using linked list requires comparing the exponents, and wherever the exponents are found to be same, the coefficients are added up.  For terms with different exponents, the complete term is simply added to the result thereby making it a part of addition result.  The complete program to add two polynomials is given in subsequent section.

Multiplication of two Polynomials:

Multiplication of two polynomials however requires manipulation of each node such that the exponents are added up and the coefficients are multiplied.  After each term of first polynomial is operated upon with each term of the second polynomial, then the result has to be added up by comparing the exponents and adding the coefficients for similar exponents and including terms as such with dissimilar exponents in the result.  The ‘C’ program for polynomial manipulation is given below:

Program for Polynomial representation, addition and multiplication

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

struct poly
{
int coeff;
int exp;
struct poly *next;

void create();
void makenode(int,int);
struct poly *insertend(struct poly *);
void display(struct poly *);
struct poly *addtwopoly(struct poly *,struct poly *,struct poly *);
struct poly *subtwopoly(struct poly *,struct poly *,struct poly *);
struct poly *multwopoly(struct poly *,struct poly *,struct poly *);
struct poly *dispose(struct poly *);
int search(struct poly *,int);

void main()
{
int ch,coefficient,exponent;
int listno;
while(1)
{
clrscr();
printf(“nt1. Create First Polynomial.”);
printf(“nt2. Display First Polynomial.”);
printf(“nt3. Create Second Polynomial.”);
printf(“nt4. Display Second Polynomial.”);
printf(“nt7. Subtract Two Polynomials.”);
printf(“nt8. Display Result of Subtraction.”);
printf(“nt9. Multiply Two Polynomials.”);
printf(“nt10. Display Result of Product.”);
printf(“nt11. Dispose List.”);
printf(“nt12. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nGenerating first polynomial:”);
printf(“nEnter coefficient?”);
scanf(“%d”,&coefficient);
printf(“nEnter exponent?”);
scanf(“%d”,&exponent);
makenode(coefficient,exponent);
break;
case 2:
break;
case 3:
printf(“nGenerating second polynomial:”);
printf(“nEnter coefficient?”);
scanf(“%d”,&coefficient);
printf(“nEnter exponent?”);
scanf(“%d”,&exponent);
makenode(coefficient,exponent);
break;
case 4:
break;
case 5:
printf(“nDisposing result list.”);
break;
case 6:
break;
case 7:
printf(“Subtraction successfully done!”);
getch();
break;
case 8:
break;
case 9:
break;
case 10:
break;
case 11:
printf(“Enter list number to dispose(1 to 4)?”);
scanf(“%d”,&listno);
if(listno==1)
else if(listno==2)
else if(listno==3)
else if(listno==4)
else
printf(“Invalid number specified.”);
break;
case 12:
exit(0);
default:
printf(“Invalid Choice!”);
break;
}
}
}

void create()
{
ptr=(struct poly *)malloc(sizeof(struct poly));
if(ptr==NULL)
{
printf(“Memory Allocation Error!”);
exit(1);
}
}

void makenode(int c,int e)
{
create();
ptr->coeff = c;
ptr->exp = e;
ptr->next = NULL;
}

{
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr;
}
}

{
printf(“List is empty!”);
else
{
while(temp!=NULL)
{
printf(“(%d,%d)->”,temp->coeff,temp->exp);
temp=temp->next;
}
printf(“bb “);
}
getch();
}

struct poly *addtwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
(5,3)->(6,1) + (7,3)->(9,2) = (12,3)->(6,1)->(9,2)
*/
struct poly *temp1,*temp2,*temp3;
temp1=h1;
temp2=h2;
while(temp1!=NULL || temp2!=NULL)
{
if(temp1->exp==temp2->exp)
{
makenode(temp1->coeff+temp2->coeff,temp1->exp);
h3=insertend(h3);
}
else
{
makenode(temp1->coeff,temp1->exp);
h3=insertend(h3);
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
}
temp1=temp1->next;
temp2=temp2->next;
}
if(temp1==NULL && temp2!=NULL)
{
while(temp2!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
}
if(temp2==NULL && temp1!=NULL)
{
while(temp1!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp1=temp1->next;
}
}
return h3;
}

struct poly *subtwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
(5,3)->(6,1) – (7,3)->(9,2) = (-2,3)+(6,1)-(9,2)
*/
struct poly *temp1,*temp2,*temp3;
temp1=h1;
temp2=h2;
while(temp1!=NULL || temp2!=NULL)
{
if(temp1->exp==temp2->exp)
{
makenode(temp1->coeff-temp2->coeff,temp1->exp);
h3=insertend(h3);
}
else
{
makenode(temp1->coeff,temp1->exp);
h3=insertend(h3);
makenode(-temp2->coeff,temp2->exp);
h3=insertend(h3);
}
temp1=temp1->next;
temp2=temp2->next;
}
if(temp1==NULL && temp2!=NULL)
{
while(temp2!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
}
if(temp2==NULL && temp1!=NULL)
{
while(temp1!=NULL)
{
makenode(-temp2->coeff,temp2->exp);
h3=insertend(h3);
temp1=temp1->next;
}
}
return h3;
}

struct poly *multwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
h1=(5,3)->(6,1) * h2=(7,3)->(9,2)
(5,3)->(7,3),(9,2) = (35,6),(45,5)
(6,1)->(7,3),(9,2) = (42,4),(54,3)
h3->(35,6)->(45,5)->(42,4)->(54,3)
(35,6)+(45,5)+(42,4)+(54,3)=Result
*/
int res=0;
struct poly *temp1,*temp2,*temp3;
printf(“nDisplaying First Polynomial:ntt”);
display(h1);
printf(“nDisplaying Second Polynomial:ntt”);
display(h2);

temp1=h1;
while(temp1!=NULL)
{
temp2=h2;
while(temp2!=NULL)
{
makenode(temp1->coeff*temp2->coeff,temp1->exp+temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
temp1=temp1->next;
}

printf(“nDisplaying Initial Result of Product:ntt”);
display(h3);
getch();

temp1=h3;
while(temp1!=NULL)
{temp2=temp1->next;
res=0;
while(temp2!=NULL)
{
if(temp1->exp==temp2->exp)
res += temp2->coeff;
temp2=temp2->next;
}
{
makenode(res+temp1->coeff,temp1->exp);
}
temp1=temp1->next;
}
}

int search(struct poly *h,int val)
{
struct poly *tmp;
tmp=h;
while(tmp!=NULL)
{if(tmp->exp==val)
return 0;
tmp=tmp->next;
}
return 1;
}

struct poly *dispose(struct poly *list)
{
if(list==NULL)
{
return list;
}
else
{
temp=list;
while(list!=NULL)
{
free(temp);
list=list->next;
temp=list;
}
return list;
}
}

Creation of a Circular Linked List:

A circular linked list is similar to that of a singly linked list with the only difference that the last node points the first node of the list, such that a circular path is obtained.  Thus last node of this list instead of pointing to NULL points to the head node as described in the following figure:- Program to implement a Circular Linked List

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

typedef struct clist
{
int info;
clist *next;
}clist;

clist *create()
{
clist *temp;
temp=(clist *)malloc(sizeof(clist));
if(temp==NULL)
{
printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

clist *makenode(int x)
{
clist *ptr=create();
ptr->info=x;
ptr->next=NULL;
return ptr;
}

{
clist *temp,*ptr=makenode(x);
}
else
temp=temp->next;
temp->next=ptr;
}
}

{
clist *temp;
{
printf(“nList is empty.”);
return;
}
{
return;
}
printf(“%d->”,temp->info);
temp=temp->next;
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int choice,x;
while(1)
{
clrscr();
printf(“nnt1. Generate Circular list”);
printf(“nt2. Display List”);
printf(“nt3. Exit”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
break;
case 2:
break;
case 3:
exit(0);
default:
printf(“nInvalid choice.”);
}
getch();
}
}

Traversal in a Circular Linked List:  Traversal involves keeping a temp pointer on the first node of the list and printing its value.  This pointer is then moved while printing the node’s value until this node becomes equal to head node.  The ‘C’ function is given below:

{
clist *temp;
{
printf(“nList is empty.”);
return;
}
{
return;
}
printf(“%d->”,temp->info);
temp=temp->next;
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

Searching a node in a given Circular List:

/*search node in a circular linked list*/
{
clist *temp;
int flag=0;
{printf(“nList is empty.”);
return;
}
{if(temp->info==val)
{flag=1;
break;
}
temp=temp->next;
}
if(temp->info==val)
flag=1;
if(flag==1)
printf(“nNumber found.”);
else
}

Deleting a node from a Circular List:

/*delete a given node*/

/*this code does not assume fixed head*/
/*thus after deletion of a node, the linked
list is displayed from the next node in
circular fashion.
example: 11->12->13->14
deleting 12 displays 13->14->11

{
clist *temp,*prev;
{printf(“nList is empty.”);
}
{printf(“nDeletion of first node.”);
free(temp);
}
/*position temp at node to delete*/
temp=temp->next;
{printf(“nGiven node does not exist.”);
}
/*position prev before temp.
the following loop works fine with circular list*/
for(prev=temp;prev->next!=temp;prev=prev->next);

prev->next=temp->next;
free(temp);
return (prev->next);
/*return prev->next since deletion of first node
}

/*
Entire circular list may be disposed off
by counting the number of nodes,n, freeing
memory n times and returning NULL.
*/
{
clist *temp;
int i,count=1;
count++;

for(i=1;i<=count;i++)
free(temp);
}
return NULL;
}

## Program for operations on a Doubly Linked List

Program to create a doubly linked list with the possible operations that can be done is given below:

/*Program to create a doubly linked list along with various operations that can be performed on it.*/

#include
#include
#include

typedef struct dlist
{
int info;
struct dlist *prev;
struct dlist *next;
}dlist;

/*creation*/
dlist *create();
dlist *makenode(int);

/*Insert a node at the end*/
dlist *insertend(dlist *,int);

/*Insert a node after a given node*/
dlist *insaftelement(dlist *,int,int);

/*Insert a node before a given node*/
dlist *insbefelement(dlist *,int,int);

/*delete the given node*/
dlist *delelement(dlist *,int);

/*delete node after a given node*/
dlist *delafternode(dlist *,int);

/*delete node before a given node*/
dlist *delbeforenode(dlist *,int);

/*In-order traversal*/
void displaylr(dlist *);

/*Reversal traversal*/
void displayrl(dlist *);

/*searching a given node*/
int search(dlist *,int);

/*disposing list*/
dlist *dispose(dlist *);

void main()
{
int x,ch,val;
while(1)
{clrscr();
printf(“nt1. Create”);
printf(“nt2. Display L to R”);
printf(“nt3. Display R to L”);
printf(“nt4. Insert after element”);
printf(“nt5. Insert before element”);
printf(“nt6. Delete given node”);
printf(“nt7. Delete after given node”);
printf(“nt8. Delete before given node”);
printf(“nt9. Dispose list”);
printf(“nt10. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“ntEnter number?”);
scanf(“%d”,&x);
break;
case 2:
getch();
break;
case 3:
getch();
break;
case 4:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. after which to insert?”);
scanf(“%d”,&val);
break;
case 5:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. before which to insert?”);
scanf(“%d”,&val);
break;
case 6:
printf(“nEnter node to delete?”);
scanf(“%d”,&x);
break;
case 7:
printf(“nEnter node after which to delete?”);
scanf(“%d”,&x);
break;
case 8:
printf(“nEnter node before which to delete?”);
scanf(“%d”,&x);
break;
case 9:
printf(“nDisposing list. “);
printf(“Press any key to continue…!”);
getch();
break;
case 10:
exit(0);
default:
printf(“ntInvalid Choice.”);
}
getch();
}
}

dlist *create()
{
dlist *ptr=(dlist *)malloc(sizeof(dlist));
if(ptr==NULL)
{printf(“Memory allocation error!”);
exit(1);
}
return ptr;
}

dlist *makenode(int x)
{
dlist *ptr=create();
ptr->info = x;
ptr->prev=NULL;
ptr->next=NULL;
return ptr;
}

{
dlist *temp,*ptr=makenode(x);
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next = ptr;
ptr->prev = temp;
}
}

{
dlist *temp;
{printf(“List is empty.”);
}
else
{
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}
}

{
dlist *temp;
{printf(“List is empty.”);
}
else
{
{
printf(“%d->”,temp->info);
temp=temp->prev;
}
printf(“%d->”,temp->info);
}
printf(“bb “);
}

{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}

printf(“nList is empty.”);
else
while(temp->next->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
}
}

/*delete node after a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
{printf(“nList is empty.”);
}
{printf(“nCannot delete. Only one node exists.”);
getch();
}
/*position temp at node after which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
}

/*delete node before a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
{printf(“nList is empty.”);
}
{printf(“nCannot delete. Only one node exists.”);
}
/*position temp at node before which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->prev;
if(ptr->prev!=NULL)
{ptr->prev->next=temp;
temp->prev=ptr->prev;
}
else
{temp->prev=NULL;
}
free(ptr);
}

{
dlist *temp;
while(temp!=NULL)
{
if(temp->info==x)
return 1;
temp=temp->next;
}
return 0;
}
/*Insert a node after given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
ptr=makenode(x);
while(temp->info!=val)
temp=temp->next;
ptr->next=temp->next;
ptr->prev=temp;
temp->next=ptr;
if(ptr->next!=NULL)
ptr->next->prev=ptr;
}

/*Insert a node before a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
ptr=makenode(x);
{
}
/*position temp on the node
before which to insert*/
while(temp->info!=val)
temp=temp->next;
ptr->next=temp;
ptr->prev=temp->prev;
temp->prev=ptr;
if(ptr->prev!=NULL)
ptr->prev->next=ptr;
}

/*disposing list*/
{
dlist *temp;
free(temp);
}
}

Representation of a doubly linked list:

A doubly linked list contains backward as well as forward reference.  Each node contains two address along with the information field.  One address is the address of the next node and the other one is that of the previous node.  Thus doubly linked list is a bi-directional list, since we may traverse either from left to right or from right to left directly without any pointer manipulations as was the case with singly linked list. A doubly linked list may be represented using the following structure definition:

struct doublylist
{int info;
struct doublylist *next;
struct doublylist *prev;
};

Creation of a doubly linked list:  The program to create a doubly linked list is given below:

Program for operations on a Doubly Linked List

Operations covered in the following program:

• In-order traversal
• Reverse-order traversal
• Searching
• Insertion (inserting after, inserting before)
• Deletion (deleting after, deleting before)
• Disposing list

In-order traversal:  It refers to reading the elements of a doubly linked list from left to right.  The ‘C’ function for inorder traversal is as follows-

{
dlist *temp;
{printf(“List is empty.”);
}
else
{
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}
}

Reverse-order traversal:  Doubly linked list facilitates reverse order traversal, since reverse links are maintained via. keeping addresses of previous node as well as next node.  Thus a temp pointer may be positioned on the last element and then the traversal may begin from last to first using temp->prev navigation condition.  In the end, the first element may be printed.  The ‘C’ function is as follows:

{
dlist *temp;
{printf(“List is empty.”);
}
else
{
{
printf(“%d->”,temp->info);
temp=temp->prev;
}
printf(“%d->”,temp->info);
}
printf(“bb “);
}

Searching a node from a doubly linked list:  Searching a given value involves locating that value in the doubly list.  A temp pointer may be positioned at head node, and may be shifted until null is found or the given value is found.  The ‘C’ function to search a given node is as follows-

{
dlist *temp;
while(temp!=NULL)
{
if(temp->info==x)
return 1;
temp=temp->next;
}
return 0;
}

Insertion after a given node:  Inserting a new node after a given node requires four pointer adjustments.  First of all the node after which new node is to be inserted is to be located in the doubly list.  If it is found, then the following pointer assignments are required:

(i) The next address of new node must be set to the next of temp.

(ii) The prev address of new node must be set to temp.

(iv) Finally, the prev of next node of new node must be set to new node, if next node exists in the doubly list.

The ‘C’ function for the same is given below:

/*Insert a node after given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
ptr=makenode(x);
while(temp->info!=val)
temp=temp->next;
ptr->next=temp->next;
ptr->prev=temp;
temp->next=ptr;
if(ptr->next!=NULL)
ptr->next->prev=ptr;
}

Insertion before a given node:  Insertion before a given node  is quite similar to that of insertion of a new node after a given node, provided we place temp pointer on the node before the node instead on that node (node before which new node is to be added up).  The ‘C’ functions that handles this operation is as under:

/*Insert a node before a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
ptr=makenode(x);
{
}
/*position temp on the node
before which to insert*/
while(temp->info!=val)
temp=temp->next;
ptr->next=temp;
ptr->prev=temp->prev;
temp->prev=ptr;
if(ptr->prev!=NULL)
ptr->prev->next=ptr;
}

Deletion after a given element/node:  To delete a node after a given node, locate that node in the doubly list.  Place temp pointer on that node.  Make following pointer assignments:

(i) Assign the next node of temp to any other pointer say ptr.

(ii) Assign the address in the next of temp as the address of next of ptr.

(iii) If a node after ptr exists, then assign the prev of next of ptr as temp.

(iv) Free pointer ptr.

The ‘C’ function is given below:

/*Delete node after a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
{printf(“nList is empty.”);
}
{printf(“nCannot delete. Only one node exists.”);
getch();
}
/*position temp at node after which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
}

Deletion of a given element/node:  To delete the user defined node, locate that node such that the temp pointer is positioned on a node just before the node to be removed.  Then perform pointer adjustments as given in the previous case.  The ‘C’ function to delete a given node is as under:

{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}

printf(“nList is empty.”);
else
while(temp->next->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
}
}

Deletion before a given element/node:  The function to delete a node before a given node is as follows:

/*delete node before a given node*/
{
dlist *temp,*ptr;
int ans;
if(ans==0)
{printf(“nNumber does not exist.”);
}
{printf(“nList is empty.”);
}
{printf(“nCannot delete. Only one node exists.”);
}
/*position temp at node before which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->prev;
if(ptr->prev!=NULL)
{ptr->prev->next=temp;
temp->prev=ptr->prev;
}
else
{temp->prev=NULL;
}
free(ptr);
}

Disposing doubly linked list:  Disposing is the process of removing all the nodes of a doubly list and freeing the allocated memory, such that the list is finally deleted.  The ‘C’ function to dispose a doubly list is as follows:

/*disposing list*/
{
dlist *temp;
free(temp);
}
}

## Program for operations on a Singly Linked List

Program for various operations that can be done on a Singly Linked List is given below:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct list
{int n;
struct list *next;
}list;

list *createnode()
{list *temp;
temp=(list*)malloc(sizeof(list));
return temp;
}

list *makenode(int x)
{list *temp;
temp=createnode();
temp->n=x;
temp->next=NULL;
return temp;
}

/*11 13 15 17*/
/*Sorted search on a list sorted in ascending order*/
{
list *temp;
{printf(“List is empty.”);
return;
}

while((temp->n!=val) && (val>temp->n) && (temp!=NULL))
temp=temp->next;
if(temp->n==val)
printf(“nNumber found.”);
else
}

/*UnSorted search on an unsorted list*/
{
list *temp;
{printf(“nList is empty.”);
return;
}
/*searches for equality until number is found*/
/*best case is when first number is the required number*/
/*worst case is number does not exist*/
/*or number is present at last position in list*/
while(temp!=NULL)
{if(temp->n==val)
{printf(“nNumber found.”);
return;
}
temp=temp->next;
}
}

/*Insertion at beginning*/
{
list *temp,*ptr=makenode(x);
}
else
}
}

/*Insertion at end*/
{
list *temp,*ptr=makenode(x);
}
else
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
}

/*Insertion after given element/node*/
{
list *temp,*ptr=makenode(x);
{printf(“nGiven node does not exist. List empty”);
}
else
while(temp->n!=node)
temp=temp->next;
if(temp==NULL)
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}
/*Insertion before given element/node*/
{
list *temp,*ptr=makenode(x);
{printf(“nGiven node does not exist. List empty”);
}
else
}
else
while(temp->next->n!=node)
temp=temp->next;
if(temp==NULL)
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}
}

/*function to delete first node*/
{list *temp;
{printf(“nList is empty!”);
}
free(temp);
}

/*function to delete last node*/
{list *ptr,*temp;
{printf(“nList is empty!”);
}
free(temp);
}
if(temp->next->next==NULL)
{ptr=temp->next;
temp->next=NULL;
free(ptr);
}
while(temp->next->next!=NULL)
temp=temp->next;
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
}

/*function to delete node after a given node*/
{
list *temp,*ptr;
{printf(“nList is empty.”);
}
/*locate given node in the list*/
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
}
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
}

/*function to delete node before a given node*/
{
list *temp,*temp1,*ptr;
{printf(“nList is empty.”);
}
{printf(“nCannot delete before first node.”);
}
/*locate given node in the list*/
while((temp->next->n!=node) && (temp!=NULL))
{temp1=temp;
temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
}
ptr=temp1->next;
temp1->next=ptr->next;
free(ptr);
}

/*In-order traversal*/
{
list *temp;
{printf(“nList is empty.”);
return;
}
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}

/*Reverse order traversal*/
{
list *temp;
int i,j,count=0;
{printf(“nList is empty.”);
return;
}
for(i=1;i<=count;i++)
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
}
printf(“bb “);
}

/*Reversing list*/
{
int i,j,count=0;
{printf(“nList is empty.”);
}
for(i=1;i<=count;i++)
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
}
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
printf(“bb “);
while(temp!=NULL)
{ptr=temp;
temp=temp->next;
free(ptr);
}
}

{
list *ptr,*temp;
printf(“nPress any key to continue…”);
free(temp);
}
}

/*Concatenating list*/
{
while(temp->next!=NULL)
temp=temp->next;
}

/*Splitting from middle*/
{
int i,count=0;
count++;
/*i is 1 since temp is already at first node*/
for(i=1;i<count/2;i++)
temp=temp->next;
temp->next=NULL;
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
printf(“%d->”,temp->n);
printf(“bb “);
}

/*Splitting alternate nodes*/
{
int i;
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
/*creating odd list*/
if(i%2!=0)
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
else /*creating even list*/
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
}
printf(“nAlternate node Splitting list task over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
printf(“%d->”,temp->n);
printf(“bb “);
}

/*Splitting after a given node*/
while((temp!=NULL)&&(temp->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->n==node)
temp->next=NULL;
}
printf(“nSplit task after given node is over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
printf(“%d->”,temp->n);
printf(“bb “);
}

/*Split before given node*/
/*if there is only one node*/
if(temp->n==node)
}
else
{
while((temp!=NULL)&&(temp->next->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->next->n==node)
temp->next=NULL;
}
}
printf(“nSplit task before given node is over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
printf(“%d->”,temp->n);
printf(“bb “);
}

while((temp1!=NULL)&&(temp2!=NULL))
{if(temp1->n<temp2->n)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
else
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
else
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
else
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
}
while(temp1!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
else
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
while(temp2!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
else
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
}

void main()
{
int ch,num,node;
while(1)
{
clrscr();
printf(“nn1. Insert at beginning”);
printf(“n2. Insert at end”);
printf(“n3. Insert after given node”);
printf(“n4. Insert before given node”);
printf(“n5. In-order display”);
printf(“n6. Reversal display”);
printf(“n7. Sorted Search”);
printf(“n8. Unsorted Search”);
printf(“n9. Delete first node”);
printf(“n10. Delete last node”);
printf(“n11. Delete after node”);
printf(“n12. Delete before node”);
printf(“n13. Reverse list”);
printf(“n14. Dispose list”);
printf(“n15. Create first list”);
printf(“n16. Create second list”);
printf(“n17. Concatenate list”);
printf(“n18. Display concatenated list.”);
printf(“n19. Split list from middle.”);
printf(“n20. Split alternate nodes.”);
printf(“n21. Split after given node.”);
printf(“n22. Split before given node.”);
printf(“n23. Merge two lists.”);
printf(“n24. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
break;
case 2: printf(“nEnter any number?”);
scanf(“%d”,&num);
break;
case 3: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node after which to insert?”);
scanf(“%d”,&node);
break;
case 4: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node before which to insert?”);
scanf(“%d”,&node);
break;
case 5: printf(“nIn-order display:”);
break;
case 6: printf(“nReverse order display:”);
break;
case 7: printf(“nEnter number to search?”);
scanf(“%d”,&num);
break;
case 8: printf(“nEnter number to search?”);
scanf(“%d”,&num);
break;
case 9:
break;
case 10:
break;
case 11:
printf(“nEnter the node after which to delete?”);
scanf(“%d”,&node);
break;
case 12:
printf(“nEnter the node before which to delete?”);
scanf(“%d”,&node);
break;
case 13:
break;
case 14:
break;
case 15:
printf(“nEnter number?”);
scanf(“%d”,&num);
break;
case 16:
printf(“nEnter number?”);
scanf(“%d”,&num);
break;
case 17:
printf(“Concatenating lists.”);
printf(“Press any key to continue…!”);
break;
case 18:
printf(“nConcatenated list:”);
break;
case 19:
break;
case 20:
break;
case 21:
printf(“nEnter the node after which to split?”);
scanf(“%d”,&node);
break;
case 22:
printf(“nEnter the node before which to split?”);
scanf(“%d”,&node);
break;
case 23:
printf(“nMerging two sorted lists.”);
printf(“nPress any key to continue…”);
break;
case 24:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}

## Singly Linked List – Creation Sorted

Program to create a Sorted Linked List

Creating a Sorted Linked List involves insertion of a new node in the linked list such that the order of the list is preserved.  The order to be retained in the list may be chosen as either ascending or descending order.

/*Program for linked list creation,insertion and deletion.*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct list
{int n;
struct list *next;

struct list *createnode()
{struct list *temp;
temp=(struct list*)malloc(sizeof(struct list));
return temp;
}

struct list *makenode(int x)
{struct list *temp;
temp=createnode();
temp->n=x;
temp->next=NULL;
return temp;
}

/*Insertion condition-At the end*/
/*New element is inserted at the end*/

void insertend(int x)
{
struct list *temp1,*temp2,*ptr=makenode(x);
}
else
{
}
else
{
while((temp1->n<x) && (temp1!=NULL))
{temp2=temp1;
temp1=temp1->next;
}
ptr->next=temp2->next;
temp2->next=ptr;
}
}
}
/* else
{
else
}
}
else
{
while((temp->next->n<x) && (temp->next!=NULL))
temp=temp->next;

if(temp->next==NULL)
temp->next=ptr;
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}

}

Deletion condition-At the beginning*/

void delnode()
{struct list *temp;
{printf(“List is empty!”);
return;
}
free(temp);
}

/*Displaying list*/

void displaylist()
{
struct list *temp;
{printf(“nList is empty.”);
return;
}
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
insertend(num);
break;
case 2:
delnode();
break;
case 3:
displaylist();
break;
case 4:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

## Singly Linked List – Creation FIFO

Program to create a FIFO linked list

If a linked list is created considering FIFO order, then insertions are done at one end, whereas deletions are performed at the other end.  Thus, the first node to be deleted is only that node which is inserted first in the linked list.
/*Program for linked list creation,insertion and deletion.*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct list
{int n;
struct list *next;

struct list *createnode()
{struct list *temp;
temp=(struct list*)malloc(sizeof(struct list));
return temp;
}

struct list *makenode(int x)
{struct list *temp;
temp=createnode();
temp->n=x;
temp->next=NULL;
return temp;
}

/*Insertion condition-At the end*/
/*New element is inserted at the end*/

void insertend(int x)
{
struct list *temp,*ptr=makenode(x);
}
else
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
}

/*Deletion condition-At the beginning*/
/*Since first node inserted is to be removed first*/

void delnode()
{struct list *temp;
{printf(“List is empty!”);
return;
}
free(temp);
}

/*Displaying list*/

void displaylist()
{
struct list *temp;
{printf(“nList is empty.”);
return;
}
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
insertend(num);
break;
case 2:
delnode();
break;
case 3:
displaylist();
break;
case 4:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

## Singly Linked List – Creation LIFO

Program to create a LIFO Linked List:

Creation of a linked list may be done in LIFO order.  If a linked list is created in LIFO order, then insertions as well as deletions are done at the same end i.e. the last node of the linked list is the first one to be deleted.

/*Program for linked list creation,insertion and deletion.*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct list
{int n;
struct list *next;

struct list *createnode()
{struct list *temp;
temp=(struct list*)malloc(sizeof(struct list));
return temp;
}

struct list *makenode(int x)
{struct list *temp;
temp=createnode();
temp->n=x;
temp->next=NULL;
return temp;
}

/*Insertion condition-At the end*/
/*New element is inserted at the end*/

void insertend(int x)
{
struct list *temp,*ptr=makenode(x);
}
else
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
}

/*Deletion condition-At the end*/
/*since last node is the first to be removed*/

void delnode()
{struct list *ptr,*temp;
{printf(“List is empty!”);
return;
}
free(temp);
return;
}
if(temp->next->next==NULL)
{ptr=temp->next;
temp->next=NULL;
free(ptr);
return;
}
while(temp->next->next!=NULL)
temp=temp->next;
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
}

/*Displaying list*/

void displaylist()
{
struct list *temp;
{printf(“nList is empty.”);
return;
}
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
insertend(num);
break;
case 2:
delnode();
break;
case 3:
displaylist();
break;
case 4:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

x Close
{"ft_lang_label":"__label__en","ft_lang_prob":0.53562796,"math_prob":0.9167119,"size":47558,"snap":"2021-04-2021-17","text_gpt3_token_len":14245,"char_repetition_ratio":0.22828785,"word_repetition_ratio":0.31726837,"special_character_ratio":0.312797,"punctuation_ratio":0.22646672,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98454475,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,10,null,10,null,8,null,8,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-22T08:39:41Z\",\"WARC-Record-ID\":\"<urn:uuid:c40b364a-34e2-42f2-8aef-5afd67ac7da5>\",\"Content-Length\":\"150021\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:72b4c0d4-170b-46db-be65-709f81c92f9d>\",\"WARC-Concurrent-To\":\"<urn:uuid:abbbca7d-25f3-4ce8-aa84-e0a157cc02c7>\",\"WARC-IP-Address\":\"160.153.137.99\",\"WARC-Target-URI\":\"http://www.manojagarwal.co.in/category/data-structures-using-c-language/linked-list/\",\"WARC-Payload-Digest\":\"sha1:54PXIAG2CZMMJRXU6JBS4PDE3ER4OS4Y\",\"WARC-Block-Digest\":\"sha1:XPZ67P4L6AJE7UXDY7KZCMDYBU5HX44I\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703529179.46_warc_CC-MAIN-20210122082356-20210122112356-00702.warc.gz\"}"}