You cannot copy content of this page.

Tag Archive Linked List

Conversion of a Linked List into Array

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 *insertend(list *head,int x)
{list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
return head;
}

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

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

list *dispose(list *head)
{
list *temp;
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

list *convertlist_to_array(list *head,int arr[])
{int i=0;
list *temp=head;
while(temp!=NULL)
{arr[i++]=temp->info;
temp=temp->next;
}
head=dispose(head);
return head;
}

void main()
{
list *head=NULL;
int i,ch,num,size,arr[MAX]={0};
while(1)
{
clrscr();
printf(“nMenu”);
printf(“nn1. Create List”);
printf(“n2. Display List”);
printf(“n3. Convert List to Array”);
printf(“n4. Display Array”);
printf(“n5. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number?”);
scanf(“%d”,&num);
head=insertend(head,num);
break;
case 2:
display(head);
break;
case 3:
size=count(head);
printf(“nConverting List to Array…”);
head=convertlist_to_array(head,arr);
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();
}
}

 

Tags, ,

Josephus Algorithm

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[45];
struct clist *next;
}*head=NULL,*temp,*ptr;

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()
{
if(head==NULL)
{
head=ptr;
ptr->next=head;
}
else
{temp=head;
while(temp->next!=head)
temp=temp->next;
ptr->next=head;
temp->next=ptr;
}
}

void display()
{
if(head==NULL)
{
printf(“List is empty.”);
return;
}

if(head==head->next)
{
printf(“(%d,%s)->”,head->id,head->name);
return;
}
temp=head;
printf(“(%d,%s)->”,temp->id,temp->name);
temp=temp->next;
while(temp!=head)
{
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);
temp=head;
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[45];
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”);
printf(“ntEnter your choice?”);
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.”);
}
}
}

Tags,

Polynomial – Representation, Addition, Multiplication

Polynomial Manipulation

  • Representation
  • Addition
  • 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:





Addition of two Polynomials:

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

/*Polynomial- Representation, Addition, Multiplication*/

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

struct poly
{
int coeff;
int exp;
struct poly *next;
}*head1=NULL,*head2=NULL,*head3=NULL,*head4=NULL,*temp,*ptr;

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(“ntMenu”);
printf(“nt1. Create First Polynomial.”);
printf(“nt2. Display First Polynomial.”);
printf(“nt3. Create Second Polynomial.”);
printf(“nt4. Display Second Polynomial.”);
printf(“nt5. Add Two Polynomials.”);
printf(“nt6. Display Result of Addition.”);
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”);
printf(“nntEnter your choice?”);
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);
head1 = insertend(head1);
break;
case 2:
display(head1);
break;
case 3:
printf(“nGenerating second polynomial:”);
printf(“nEnter coefficient?”);
scanf(“%d”,&coefficient);
printf(“nEnter exponent?”);
scanf(“%d”,&exponent);
makenode(coefficient,exponent);
head2 = insertend(head2);
break;
case 4:
display(head2);
break;
case 5:
printf(“nDisposing result list.”);
head3=dispose(head3);
head3=addtwopoly(head1,head2,head3);
printf(“Addition successfully done!”);
break;
case 6:
display(head3);
break;
case 7:
head3=dispose(head3);
head3=subtwopoly(head1,head2,head3);
printf(“Subtraction successfully done!”);
getch();
break;
case 8:
display(head3);
break;
case 9:
head3=dispose(head3);
head4=dispose(head4);
head4=multwopoly(head1,head2,head3);
break;
case 10:
display(head4);
break;
case 11:
printf(“Enter list number to dispose(1 to 4)?”);
scanf(“%d”,&listno);
if(listno==1)
head1=dispose(head1);
else if(listno==2)
head2=dispose(head2);
else if(listno==3)
head3=dispose(head3);
else if(listno==4)
head4=dispose(head4);
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;
}

struct poly *insertend(struct poly *head)
{
if(head==NULL)
head = ptr;
else
{
temp=head;
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr;
}
return head;
}

void display(struct poly *head)
{
if(head==NULL)
printf(“List is empty!”);
else
{
temp=head;
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;
}
if(search(head4,temp1->exp)==1)
{
makenode(res+temp1->coeff,temp1->exp);
head4=insertend(head4);
}
temp1=temp1->next;
}
return head4;
}

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)
{
printf(“List is already empty.”);
return list;
}
else
{
temp=list;
while(list!=NULL)
{
free(temp);
list=list->next;
temp=list;
}
return list;
}
}

 

Tags, ,

Circular Linked List

Circular Linked 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

/*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 *insertend(clist *head,int x)
{
clist *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
ptr->next=head;
}
else
{temp=head;
while(temp->next!=head)
temp=temp->next;
ptr->next=head;
temp->next=ptr;
}
return head;
}

void display(clist *head)
{
clist *temp;
if(head==NULL)
{
printf(“nList is empty.”);
return;
}
if(head==head->next)
{
printf(“%d->”,head->info);
return;
}
temp=head;
printf(“%d->”,temp->info);
temp=temp->next;
while(temp!=head)
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int choice,x;
clist *head=NULL;
while(1)
{
clrscr();
printf(“ntCircular List – Menu”);
printf(“nnt1. Generate Circular list”);
printf(“nt2. Display List”);
printf(“nt3. Exit”);
printf(“ntEnter your choice?”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
head=insertend(head,x);
break;
case 2:
display(head);
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:

/*traversal of circular linked list*/
void display(clist *head)
{
clist *temp;
if(head==NULL)
{
printf(“nList is empty.”);
return;
}
if(head==head->next)
{
printf(“%d->”,head->info);
return;
}
temp=head;
printf(“%d->”,temp->info);
temp=temp->next;
while(temp!=head)
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

Searching a node in a given Circular List:

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

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
thus head node shifts continuously.*/

clist *deletenode(clist *head,int x)
{
clist *temp,*prev;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==head)
{printf(“nDeletion of first node.”);
temp=head;
head=NULL;
free(temp);
return head;
}
temp=head;
/*position temp at node to delete*/
while((temp->info!=x)&&(temp->next!=head))
temp=temp->next;
if((temp->next==head)&&(temp->info!=x))
{printf(“nGiven node does not exist.”);
return head;
}
/*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
removes head and shift head to next node.*/
}

Disposing a Circular Linked List:

/*dispose circular linked list*/
/*
Entire circular list may be disposed off
by counting the number of nodes,n, freeing
memory n times and returning NULL.
*/
clist *dispose(clist *head)
{
clist *temp;
int i,count=1;
for(temp=head;temp->next!=head;temp=temp->next)
count++;

for(i=1;i<=count;i++)
{temp=head;
head=head->next;
free(temp);
}
return NULL;
}

 

Tags,

Program for operations on a Doubly Linked List

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.*/

/*Doubly Linked List*/

#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()
{
dlist *head=NULL;
int x,ch,val;
while(1)
{clrscr();
printf(“ntMenu(Doubly Linked List)”);
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”);
printf(“ntEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“ntEnter number?”);
scanf(“%d”,&x);
head=insertend(head,x);
break;
case 2:
displaylr(head);
getch();
break;
case 3:
displayrl(head);
getch();
break;
case 4:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. after which to insert?”);
scanf(“%d”,&val);
head=insaftelement(head,val,x);
break;
case 5:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. before which to insert?”);
scanf(“%d”,&val);
head=insbefelement(head,val,x);
break;
case 6:
printf(“nEnter node to delete?”);
scanf(“%d”,&x);
head=delelement(head,x);
break;
case 7:
printf(“nEnter node after which to delete?”);
scanf(“%d”,&x);
head=delafternode(head,x);
break;
case 8:
printf(“nEnter node before which to delete?”);
scanf(“%d”,&x);
head=delbeforenode(head,x);
break;
case 9:
printf(“nDisposing list. “);
printf(“Press any key to continue…!”);
getch();
head=dispose(head);
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 *insertend(dlist *head,int x)
{
dlist *temp,*ptr=makenode(x);
if(head==NULL)
head=ptr;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next = ptr;
ptr->prev = temp;
}
return head;
}

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

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

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

if(head==NULL)
printf(“nList is empty.”);
else
{temp=head;
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);
}
return head;
}

/*delete node after a given node*/
dlist *delafternode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
getch();
return head;
}
temp=head;
/*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);
return head;
}

/*delete node before a given node*/
dlist *delbeforenode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
return head;
}
temp=head;
/*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;
head=temp;
}
free(ptr);
return head;
}

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

/*Insert a node before a given node*/
dlist *insbefelement(dlist *head,int val,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,val);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
ptr=makenode(x);
if(head->info==val)
{
ptr->next=head;
head->prev=ptr;
head=ptr;
return head;
}
temp=head;
/*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;
return head;
}

/*disposing list*/
dlist *dispose(dlist *head)
{
dlist *temp;
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

Tags,

Doubly Linked List

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-

void displaylr(dlist *head)
{
dlist *temp;
if(head==NULL)
{printf(“List is empty.”);
}
else
{
temp=head;
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:

void displayrl(dlist *head)
{
dlist *temp;
if(head==NULL)
{printf(“List is empty.”);
}
else
{
for(temp=head;temp->next!=NULL;temp=temp->next);
while(temp!=head)
{
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-

int search(dlist *head,int x)
{
dlist *temp;
temp=head;
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.

(iii) Then next address of temp must become new node address.

(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 *insaftelement(dlist *head,int val,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,val);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
ptr=makenode(x);
temp=head;
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;
return head;
}

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 *insbefelement(dlist *head,int val,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,val);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
ptr=makenode(x);
if(head->info==val)
{
ptr->next=head;
head->prev=ptr;
head=ptr;
return head;
}
temp=head;
/*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;
return head;
}

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 *delafternode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
getch();
return head;
}
temp=head;
/*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);
return head;
}

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 *delelement(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}

if(head==NULL)
printf(“nList is empty.”);
else
{temp=head;
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);
}
return head;
}

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 *delbeforenode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
return head;
}
temp=head;
/*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;
head=temp;
}
free(ptr);
return head;
}

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 *dispose(dlist *head)
{
dlist *temp;
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

Tags,

Program for operations on a Singly Linked List

Singly Linked List

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

/*Program for Singly Linked List*/

/*Operations on Linked List*/

#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*/
void sortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“List is empty.”);
return;
}
temp=head;

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

/*UnSorted search on an unsorted list*/
void unsortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
/*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;
}
printf(“nNumber not found.”);
}

/*Insertion at beginning*/
list *insertbegin(list *head,int x)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{ptr->next=head;
head=ptr;
}
return head;
}

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

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

/*function to delete first node*/
list *delfirstnode(list *head)
{list *temp;
if(head==NULL)
{printf(“nList is empty!”);
return head;
}
temp=head;
head=head->next;
free(temp);
return head;
}

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

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

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

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

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

/*Reversing list*/
list *reverselist(list *head)
{
list *temp,*head1=NULL,*ptr,*temp1;
int i,j,count=0;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
for(temp=head;temp!=NULL;temp=temp->next,count++);
for(i=1;i<=count;i++)
{temp=head;
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;
if(head1==NULL)
{head1=ptr;
}
else
{temp1=head1;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
printf(“bb “);
temp=head;
while(temp!=NULL)
{ptr=temp;
temp=temp->next;
free(ptr);
}
return head1;
}

/*Disposing linked list*/
list *dispose(list *head)
{
list *ptr,*temp;
printf(“nDisposing the linked list.”);
printf(“nPress any key to continue…”);
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

/*Concatenating list*/
list *concatenate(list *head1,list *head2)
{
list *temp=head1;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head2;
return head1;
}

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

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

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

/*Split before given node*/
void splitbeforenode(list *head,int node)
{list *temp,*head1=NULL;
temp=head;
/*if there is only one node*/
if(temp->n==node)
{head1=temp;
head=NULL;
}
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)
{head1=temp->next;
temp->next=NULL;
}
}
printf(“nSplit task before given node is over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}

list *merge(list *head1,list *head2)
{list *head=NULL,*temp1,*temp2,*ptr,*tmp;
temp1=head1;
temp2=head2;
while((temp1!=NULL)&&(temp2!=NULL))
{if(temp1->n<temp2->n)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
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;
if(head==NULL)
head=ptr;
else
{tmp=head;
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;
if(head==NULL)
head=ptr;
else
{tmp=head;
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;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
return head;
}

void main()
{
list *head=NULL;
list *head1=NULL,*head2=NULL;
int ch,num,node;
while(1)
{
clrscr();
printf(“nLinked List Menu”);
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”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
head=insertbegin(head,num);
break;
case 2: printf(“nEnter any number?”);
scanf(“%d”,&num);
head=insertend(head,num);
break;
case 3: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node after which to insert?”);
scanf(“%d”,&node);
head=insertafternode(head,num,node);
break;
case 4: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node before which to insert?”);
scanf(“%d”,&node);
head=insertbeforenode(head,num,node);
break;
case 5: printf(“nIn-order display:”);
displaylist(head);
break;
case 6: printf(“nReverse order display:”);
displaylistreverse(head);
break;
case 7: printf(“nEnter number to search?”);
scanf(“%d”,&num);
sortedsearch(head,num);
break;
case 8: printf(“nEnter number to search?”);
scanf(“%d”,&num);
unsortedsearch(head,num);
break;
case 9:
head=delfirstnode(head);
break;
case 10:
head=dellastnode(head);
break;
case 11:
printf(“nEnter the node after which to delete?”);
scanf(“%d”,&node);
head=delafternode(head,node);
break;
case 12:
printf(“nEnter the node before which to delete?”);
scanf(“%d”,&node);
head=delbeforenode(head,node);
break;
case 13:
head=reverselist(head);
break;
case 14:
head=dispose(head);
break;
case 15:
printf(“nEnter number?”);
scanf(“%d”,&num);
head1=insertend(head1,num);
break;
case 16:
printf(“nEnter number?”);
scanf(“%d”,&num);
head2=insertend(head2,num);
break;
case 17:
printf(“Concatenating lists.”);
printf(“Press any key to continue…!”);
head1=concatenate(head1,head2);
break;
case 18:
printf(“nConcatenated list:”);
displaylist(head1);
break;
case 19:
splitmiddle(head);
break;
case 20:
splitalternatenodes(head);
break;
case 21:
printf(“nEnter the node after which to split?”);
scanf(“%d”,&node);
splitafternode(head,node);
break;
case 22:
printf(“nEnter the node before which to split?”);
scanf(“%d”,&node);
splitbeforenode(head,node);
break;
case 23:
printf(“nMerging two sorted lists.”);
printf(“nPress any key to continue…”);
head=merge(head1,head2);
break;
case 24:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}

Tags,

Program to create a Sorted Linked List

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.*/
/*Creation of Sorted Linked List*/

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

struct list
{int n;
struct list *next;
}*head=NULL;

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);
if(head==NULL)
{head=ptr;
}
else
{
if(head->n>x)
{ptr->next=head;
head=ptr;
}
else
{
temp1=head;
while((temp1->n<x) && (temp1!=NULL))
{temp2=temp1;
temp1=temp1->next;
}
ptr->next=temp2->next;
temp2->next=ptr;
}
}
}
/* else
{if(head->next==NULL)
{
if(head->n<x)
head->next=ptr;
else
{ptr->next=head;
head=ptr;
}
}
else
{
temp=head;
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;
if(head==NULL)
{printf(“List is empty!”);
return;
}
temp=head;
head=head->next;
free(temp);
}

/*Displaying list*/

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

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nCreation of Sorted Linked List-Menu”);
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
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();
}
}

Tags,

Program to create a FIFO Linked List

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.*/
/*FIFO Linked List*/

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

struct list
{int n;
struct list *next;
}*head=NULL;

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);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
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;
if(head==NULL)
{printf(“List is empty!”);
return;
}
temp=head;
head=head->next;
free(temp);
}

/*Displaying list*/

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

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nLinked List (FIFO)-Menu”);
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
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();
}
}

Tags,

Program to create a LIFO Linked List

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.*/
/*LIFO Linked List*/

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

struct list
{int n;
struct list *next;
}*head=NULL;

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);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
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;
if(head==NULL)
{printf(“List is empty!”);
return;
}
if(head->next==NULL)
{temp=head;
head=NULL;
free(temp);
return;
}
temp=head;
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;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int ch,num;
while(1)
{
clrscr();
printf(“nLinked List (LIFO)-Menu”);
printf(“nn1. Insert”);
printf(“n2. Delete”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
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();
}
}

Tags,

x Close

Like Us On Facebook