Write a
C program that uses functions to perform the following:
a) Create
a doubly linked list of integers.
b) Delete
a given integer from the above doubly linked list.
c) Display
the contents of the above list after deletion.
AIM: Implement
the Single linked List
Algorithms:
Inserting
a node into DLL: Algorithm: Insert at front()
{
Allocate
a memory for new node(new1) if (new1== NULL)
then
display
memory is full (insertion is not possible)
end
if else
read element ele;
new1->data=ele;/*copy
the data into new1 node */ new1->next=header->next;
header->next->prev=new1;
header->next=new1;
new1->prev=header;
end
else
}
Algorithm:
Insert
at End()
{
Allocate
a memory for new node(new1) if(new1== NULL)
then
display
memory is full (insertion is not possible)
end
if else
ptr=header
while(ptr->next!=NULL
)/*ptr moves end of list */ then
ptr=ptr->next
end
new1->next=NULL new1->prev=ptr; new1->data=ele ptr->next=new1
end else
}
Algorithm: Insert at middle ()
{
Allocate
a memory for new node(new1)
if
(new1== NULL) then
display
memory is full (insertion is not possible)
exit
else
read ele,pos ptr=header count=0
while(ptr->next!=NULL)
{
ptr=ptr->next;
count ++;
}
if(count<pos-1)
then
display
position is not of range
end
ptr=header count=0
while(count<pos-1)
then
ptr=ptr->next
count++
end
new1->data=ele;
new1->next=ptr->next;
new1->prev=ptr; ptr->next->prev=new1; ptr->next=new1
end
else
}
Deleting
a node from the DLL: Algorithm: delete at front()
{
if
(header->next==NULL) then
display list is
empty
end
if else
temp=header->next;
header->next=header->next->next; temp->next->prev=header;
free(temp);
end if
}
Algorithm:
Delete
at end()
{
if(header->next==NULL)
then
display
list is empty
end
if else
ptr=header;
while(ptr->next->next!=NULL)
{
ptr->=Ptr->next;
}
temp=ptr->next;
ptr->next=NULL; free(temp);
end else
}
Algorithm:delete
at anyposition()
{
if
(header->next==NULL) then
display
list is empty /*deletion is not
possible*/
end
if ptr=header; count=0;
while(ptr->next!=NULL)
{
ptr=ptr->next;
count++;
}
if(count<pos-1)
{
Display position
is out of range
}
ptr=header;
count=0;
while(count<pos-1)
{
ptr=ptr->next;
count++;
}
temp=ptr->next;
ptr->next=temp->next; temp->next->prev=Ptr; free(temp)
}
Traversing
a List:
Algorithm:Traverse()
{
ptr=header;
if(ptr
->next==NULL)
then
display list is empty end if
else
while(ptr ->
next!=NULL)
{
display
ptr-> data
ptr=ptr
-> next /*
move to next node */
}
end
if
}
Program:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int
data;
struct
node *next; struct node *prev;
};
struct node *header=NULL; struct node
*ptr=NULL,*temp=NULL;
void create();
void
insert_at_front(); void insert_at_end(); void insert_at_ middle(); void
delete_at_front(); void delete_at_end(); void delete_at_middle(); void count();
void
display(); void search();
int
main()
{
int
ch;
header=(struct
node*)malloc(sizeof(struct node)); header->next=NULL;
header->prev=NULL; ptr=header;
//clrscr();
printf("\n\n1.create
\n2- insert at front\n3- insert at middle\n4- insert at
end\n5-display\n6.delete_at_front\n7.delete_at_middle\n8.delete_at_end\\n9-exit");
while(1)
{
printf("\nenter
ur choice : "); scanf("%d",&ch); switch(ch)
{
case 1: create(); break;
case 2: insert_at_front(); break;
case 3: insert_at_middle(); break;
case 4: insert_at_end(); break;
case 5: display(); break;
case 6: delete_at_front(); break;
case
7: delete_at_middle(); break;
case 8: delete_at_end(); break;
case 9: exit(0);
default:
printf("wrong choice");
}
}
}
void create()
{
char
ch; while(1)
{
insert_at_end();
printf("if
u want to continue press 'y' or 'n' :"); fflush(stdin);
scanf("%c",&ch);
if(ch=='y'||ch=='Y')
continue;
else
break;
}
}
void
insert_at_front()
{
int ele;
struct node *new1;
new1=(struct
node*)malloc(sizeof(struct node)); if(new1==NULL)
{
printf("out
of space"); return;
}
printf("enter
ele:"); scanf("%d",&ele); new1->next=header->next;
header->next->prev=new1; header->next=new1; new1->prev=header; new1->data=ele;
printf("inserted successfully");
}
void
insert_at_end()
{
struct
node *new1; int ele;
new1=(struct
node*)malloc(sizeof(struct node)); ptr=header;
if(new1==NULL)
{
printf("out
of space"); return;
}
printf("enter
Inserted ele:"); scanf("%d",&ele);
/*
Move the pointer to upto end of the node*/ while(ptr->next!=NULL)
{
ptr=ptr->next;
}
new1->next=NULL;
new1->prev=ptr; ptr->next=new1; new1->data=ele; printf("inserted
successfully");
}
void
insert_at_middle()
{
struct
node *new1; int ele;
int pos,count=0;
new1=(struct
node*)malloc(sizeof(struct node));
ptr=header;
if(new1==NULL)
{
printf("out
of space"); return;
}
printf("enter
Inserted ele:"); scanf("%d",&ele);
printf("enter
where it to be inserted at what position number:");
scanf("%d",&pos);
/*
Calculate the no of elements in the list */ while(ptr->next!=NULL)
{
count++;
ptr=ptr->next;
}
/*Compare the entered positions number is
valid or not using count the no.of elements in the list*/
if(count<pos)
{
printf("pos
is out of range"); return;
}
ptr=header;
count=0;
/*Move
the ptr upto particular entered position number*/ while(count<pos-1)
{
ptr=ptr->next;
count++;
}
new1->next=ptr->next;
new1->prev=ptr; ptr->next->prev=new1; ptr->next=new1;
new1->data=ele; printf("inserted successfully");
}
void display()
{
ptr=header;
/*
Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list
is empty"); return;
}
while(ptr->next!=NULL)
{
printf("%u,%d,%u
->
",ptr->next->prev,ptr->next->data,ptr->next->next);
ptr=ptr->next;
}
printf("NULL");
}
void
delete_at_front()
{
ptr=header;
/*
Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list
is empty deletion is not possible"); return;
}
temp=ptr->next;
ptr->next=ptr->next->next; ptr->next->prev=ptr; free(temp);
printf("deleted
succssfully");
}
void
delete_at_end()
{
ptr=header;
/*
Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list
is empty deletion is not possible"); return;
}
/*Move
the ptr upto last but one node*/ while(ptr->next->next!=NULL)
{
ptr=ptr->next;
}
temp=ptr->next;
ptr->next=NULL;
free(temp);
/* Clear the Memory*/ printf("deleted succssfully");
}
void
delete_at_middle()
{
int pos,count; ptr=header;
/*
Check the List is Empty or not*/ if(ptr->next==NULL)
{
printf("list
is empty deletion is not possible"); return;
}
count=0;
/*
Calculate the no.of elements in the list */ while(ptr->next!=NULL)
{
ptr=ptr->next;
count++;
}
printf("enter
deleted position number:"); scanf("%d",&pos);
/*Compare the
entered positions number is valid or not using count the no.of elements in the
list*/
if(count<pos)
{
printf("position
is out of range"); return;
}
ptr=header;
count=0;
/*Move the ptr upto particular entered
position number*/ while(ptr->next->next!=NULL&&count<pos-1)
{
ptr=ptr->next;
count++;
}
temp=ptr->next;
ptr->next=ptr->next->next; ptr->next->prev=ptr; free(temp);
printf("deleted
succssfully");
}
/*OUTPUT:
1.create
2-
insert at front
3-insert
at middle
4-insert
at end
5-display
6.delete_at_front 7.delete_at_middle 8.delete_at_end 9-exit
EnterUrchoice:
1
Enter
Inserted ele: 10
Inserted
successfullyif u wants to continue press 'y' or 'n’: n
EnterUrchoice:
5 28938256,10,0 -> NULL
Enter
ur choice: 2 enter ele: 20
Inserted
successfully
enter
ur choice : 5
28938256,20,28938288
-> 28938320,10,0 -> NULL
enter
ur choice : 3 enter Inserted ele:25
enter
where it to be inserted at what position number:2 inserted successfully
enter
ur choice : 5
28938256,20,28938352
-> 28938320,25,28938288 -> 28938352,10,0 -> NULL
enter
ur choice : 3 enter Inserted ele:35
enter
where it to be inserted at what position number:3 inserted successfully
enter
ur choice : 5
28938256,20,28938352 ->
28938320,25,28938384 -> 28938352,35,28938288 ->
28938384,10,0
-> NULL
enter
ur choice : 6 deleted succssfully
enter
ur choice : 5
28938256,25,28938384
-> 28938352,35,28938288 -> 28938384,10,0 -> NULL
enter
ur choice : 7
enter
deleted position number:2 deleted succssfully
enter
ur choice : 5
28938256,25,28938288
-> 28938352,10,0 -> NULL
enter
ur choice : 8 deleted succssfully
enter
ur choice : 5 28938256,25,0 -> NULL
enter
ur choice : 9