Doubly Linked List: Delete from End
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct
node
{
int
data;
struct
node *llink;
struct
node *rlink;
};
typedef
struct node* NODE;
NODE getnode();
NODE insert_at_end(NODE first, int
item);
NODE delete_at_end(NODE first);
void display(NODE first);
NODE
getnode()
{
NODE
x;
x
=(NODE) malloc(sizeof(struct node));
x->llink=NULL;
x->rlink=NULL;
return x;
}
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;
}
}
}
NODE
insert_at_end(NODE first, int item)
{
int
val;
NODE
cur, temp;
temp
= getnode();
temp->data
= item;
if(first == NULL) /*Case
1: List is empty*/
{
return
temp;
}
cur= first; /*Case 2: List not empty*/
while(cur->rlink!=NULL)
{
cur
= cur->rlink;
}
cur->rlink = temp;
temp->llink = cur;
return
first;
}
NODE
delete_at_end(NODE first)
{
NODE
prev=NULL, cur;
if(first
== NULL) /*Case
1: List is empty*/
{
printf("\nList
is empty. Cannot delete.");
return
NULL;
}
if(first->rlink == NULL) /*Case 2: List has
only one node*/
{
printf("\nItem
that got deleted is %d", first->data);
free(first);
return
NULL;
}
cur = first; /*Case 3: List is not empty*/
while(cur->rlink!=NULL)
{
prev
= cur;
cur
= cur->rlink;
}
prev->rlink = NULL; /*Delete the Last node.
Update the prev node’s pointer*/
printf("\nItem
that got deleted is %d", cur->data);
free(cur);
return
first;
}
void
main()
{
int
ch, item;
NODE
first = NULL;
while(1)
{
printf("\n\n~~MENU~~");
printf("\n1.Insert
at end");
printf("\n2.Delete
from end");
printf("\n3.Display");
printf("\n4.exit");
printf("\nEnter
your choice: ");
scanf("%d",
&ch);
switch(ch)
{
case
1: printf("\nEnter the value: ");
scanf("%d", &item) ;
first = insert_at_end(first, item);
break;
case 2: first
= delete_at_end(first);
break;
case
3: display(first);
break;
case 4: exit(0);
}
}
}
Output:
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 1
Enter the value: 11
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 1
Enter the value: 12
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 3
Contents are: 11 12
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 2
Item that got deleted is 12
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 2
Item that got deleted is 11
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 2
List is empty. Cannot delete.
~~MENU~~
1.Insert
at end
2.Delete
from end
3.Display
4.exit
Enter
your choice: 3
Contents are:
List is empty. Nothing to display.
