Doubly Linked List: Operations
Doubly Linked List Operations:
1) Insert at beginning2) Insert at end
3) Insert after the given key node
4) Insert before the given key node
5) Insert at specified position
6) Delete from the beginning
7) Delete from the end
8) Delete the specified key node
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *llink;
struct node *rlink;
};
typedef struct node* NODE;
NODE getnode()
{
NODE x;
x =(NODE) malloc(sizeof(struct node));
if(x==NULL)
{
printf("\nInsufficient memory");
exit(0);
}
x->llink=NULL;
x->rlink=NULL;
return x;
}
NODE insert_at_front(NODE first)
{
int val;
NODE temp;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d",&val);
temp->data = val;
if(first == NULL)
{
return temp;
}
temp->rlink = first;
first->llink = temp;
return temp;
}
NODE insert_at_end(NODE first)
{
int val;
NODE cur,temp;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d",&val);
temp->data = val;
if(first == NULL)
{
return temp;
}
cur= first;
while(cur->rlink!=NULL)
{
cur = cur->rlink;
}
cur->rlink = temp;
temp->llink = cur;
return first;
}
NODE delete_at_midle(NODE first)
{
int val,key;
NODE prev, cur, temp;
prev =NULL;
if(first==NULL)
{
printf("\nList empty cannot delete");
return NULL;
}
printf("\nEnter the key:");
scanf("%d",&key);
if(first->data == key)
{
if(first->rlink==NULL )
{
printf("\nItem that got deleted is %d", first->data);
free(first);
return NULL;
}
else
{
temp = first;
first = first->rlink;
first->llink = NULL;
printf("\nThe node %d is deleted",temp->data);
free(temp);
return first;
}
}
else
{
cur = first;
while(cur != NULL)
{
if( cur->data == key)
break;
prev = cur;
cur = cur->rlink;
}
if(cur==NULL)
{
printf("\nKey element not found");
return first;
}
if(cur->rlink==NULL)
{
prev->rlink=NULL;
}
else
{
prev->rlink = cur->rlink;
cur->rlink->llink = prev;
}
printf("\nItem that got deleted is %d", cur->data);
free(cur);
return first;
}
}
NODE insert_after(NODE first)
{
int val,key;
NODE temp, cur;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d",&val);
temp->data = val;
if(first == NULL)
return temp;
printf("\nEnter the key after which node to be inserted:");
scanf("%d",&key);
cur = first;
while(cur != NULL)
{
if( cur->data == key)
break;
cur = cur->rlink;
}
if(cur==NULL)
{
printf("\nKey element not found");
return first;
}
if(cur->rlink ==NULL)
{
cur->rlink =temp;
temp->llink =cur;
}
else
{
temp->rlink = cur->rlink;
cur->rlink->llink = temp;
cur->rlink =temp;
temp->llink =cur;
}
return first;
}
NODE insert_before(NODE first)
{
int val,key;
NODE temp, cur, prev;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d",&val);
temp->data = val;
if(first==NULL)
return temp;
printf("\nEnter the key before which node to inserted:");
scanf("%d",&key);
if(first->data == key)
{
temp->rlink = first;
first->llink =temp;
return temp;
}
prev = NULL;
cur = first;
while(cur != NULL)
{
if( cur->data == key)
break;
prev = cur;
cur = cur->rlink;
}
if(cur==NULL)
{
printf("\nKey element not found");
return first;
}
prev->rlink = temp;
temp->llink = prev;
temp->rlink = cur;
cur->llink =temp;
return first;
}
NODE delete_at_front(NODE first)
{
NODE temp;
if(first == NULL)
{
printf("\nDoubly Linked List is empty");
return NULL;
}
if(first->rlink== NULL)
{
printf("\nThe node %d is deleted",first->data);
free(first);
return NULL;
}
temp = first;
first = first->rlink;
first->llink = NULL;
printf("\nThe node %d is deleted",temp->data);
free(temp);
return first;
}
NODE insert_at_pos(NODE first)
{
int val, pos, i;
NODE temp, cur, prev;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d",&val);
temp->data = val;
if(first==NULL)
return temp;
printf("\nEnter the position where node to inserted:");
scanf("%d",&pos);
if(pos==1)
{
temp->rlink = first;
first->llink =temp;
return temp;
}
prev = NULL;
cur = first;
for(i =1; cur != NULL && i<pos; i++)
{
prev = cur;
cur = cur->rlink;
}
if(cur==NULL)
{
printf("\nThere are less than %d elements", pos);
return first;
}
else
{
prev->rlink = temp;
temp->llink = prev;
temp->rlink = cur;
cur->llink=temp;
return first;
}
}
NODE delete_at_end(NODE first)
{
NODE prev,cur;
if(first == NULL)
{
printf("\nDoubly Linked List is empty");
return NULL;
}
if(first->rlink == NULL)
{
printf("\nThe node %d is deleted",first->data);
free(first);
return NULL;
}
prev=NULL;
cur=first;
while(cur->rlink!=NULL)
{
prev=cur;
cur = cur->rlink;
}
cur->llink = NULL;
prev->rlink = NULL;
printf("\nThe node %d is deleted",cur->data);
free(cur);
return first;
}
NODE create_list(NODE first)
{
int i, n;
printf("\nCreating the list: ");
printf("\nEnter the number of nodes: ");
scanf("%d",&n);
if(n==0)
return first;
printf("\nEnter the VALUES for nodes: ");
for(i=1;i<=n;i++)
first= insert_at_end(first);
return first;
}
void display(NODE first)
{
NODE cur;
cur = first;
printf("\nContents are:");
if(cur == NULL)
printf("\nList is empty. Nothing to display.");
else
{
while(cur!=NULL)
{
printf("%d ", cur->data);
cur = cur->rlink;
}
}
}
void main()
{
int ch;
NODE first = NULL;
while(1)
{
printf("\n\n~~MENU~~");
printf("\n1.Create a list(any insertion)");
printf("\n2.Insert at front");
printf("\n3.Insert after a given key");
printf("\n4.Insert before a given key");
printf("\n5.Insert at pos");
printf("\n6.Insert at end");
printf("\n7.Delete from front");
printf("\n8.Delete from middle using key");
printf("\n9.Delete from end");
printf("\n10.exit");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: first = create_list(first);
display(first);
break;
case 2: first = insert_at_front(first);
display(first);
break;
case 3: first = insert_after(first);
display(first);
break;
case 4: first = insert_before(first);
display(first);
break;
case 5: first = insert_at_pos(first);
display(first);
break;
case 6 : first = insert_at_end(first);
display(first);
break;
case 7: first = delete_at_front(first);
display(first);
break;
case 8: first = delete_at_midle(first);
display(first);
break;
case 9: first = delete_at_end(first);
display(first);
break;
case 10: exit(0);
}
}
}
Output:
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 1
Creating the list:
Enter the number of nodes: 3
Enter the VALUES for nodes:
Enter the value to be inserted: 11
Enter the value to be inserted: 12
Enter the value to be inserted: 13
Contents are:11 12 13
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 2
Enter the value to be inserted: 14
Contents are: 14 11 12 13
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 6
Enter the value to be inserted: 16
Contents are:14 11 12 13 16
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 3
Enter the value to be inserted: 66
Enter the key after which node to be inserted: 13
Contents are:14 11 12 13 66 16
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 4
Enter the value to be inserted: 33
Enter the key before which node to inserted:13
Contents are:14 11 12 33 13 66 16
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 5
Enter the value to be inserted: 44
Enter the position where node to inserted:4
Contents are:14 11 12 44 33 13 66 16
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 7
The node 14 is deleted
Contents are:11 12 44 33 13 66 16
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 9
The node 16 is deleted
Contents are:11 12 44 33 13 66
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 8
Enter the key:11
The node 11 is deleted
Contents are:12 44 33 13 66
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 8
Enter the key:33
Item that got deleted is 33
Contents are:12 44 13 66
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 10
