Saturday 24 September 2016

Doubly Linked List: Delete from End

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.

No comments:

Post a Comment