Showing posts with label Singly Linked List. Show all posts
Showing posts with label Singly Linked List. Show all posts

Thursday 22 September 2016

Singly Linked List : Delete from End

Singly Linked List : Delete from End


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

struct node
{
            int data;
            struct node *link;
};
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->link = NULL;
            return x;
}

NODE insert_at_end(NODE first, int item)
{

            NODE temp, cur;
            temp = getnode();
            temp->data = item;

            /*Case 1: List is empty*/
            if(first == NULL)
                        return temp;

             /*Case 2: List has nodes: Traverse till the end of the list*/
            cur = first;
            while(cur->link!=NULL)
            {
                        cur = cur->link;
            }

            /*Set the link field of last node to point to temp node*/
            cur->link = temp;
            return first;
}

NODE delete_at_end(NODE first)
{
            NODE cur, prev;

            /*Case 1: List is empty. */
            if(first == NULL)
            {
                        printf("\nList is empty. Cannot delete.");
                        return NULL;
            }

             /*Case 2: List has only one node. Deleting that node makes list empty. */
            if(first->link ==NULL)
            {
                        printf("\nItem that got deleted is %d", first->data);
                        free(first);
                        return NULL;
            }
           
            /*Case 3: List having more than one node.
                        Delete the last node. Update the link of last but one node. */
            prev =NULL;
            cur = first;
            while(cur->link!=NULL)
            {
                        prev = cur;
                        cur = cur->link;
            }
            prev->link =NULL;
            printf("\nItem that got deleted is %d", cur->data);
            free(cur);
            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->link;
                        }
            }
}

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.

~~MENU~~
1.Insert at end
2.Delete from end
3.Display
4.exit
Enter your choice: 4



Also Check,


Singly Linked List: Delete from Front

Singly Linked List: Delete from Front


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

struct node
{
            int data;
            struct node *link;
};
typedef struct node * NODE;

NODE getnode();
void display(NODE first);
NODE insert_at_front(NODE first, int item);
NODE delete_at_front(NODE first);

NODE getnode()
{
            NODE x;
            x = (NODE)malloc(sizeof(struct node));
            x->link = 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->link;
                        }
            }
}

NODE insert_at_front(NODE first, int item)
{
            NODE temp;
            temp = getnode();
            temp->data = item;

            /*Case 1: List is empty.*/
            if(first == NULL)
            return temp;

            /*Case 2: List has nodes.*/
            temp->link = first;
            return temp;
}

NODE delete_at_front(NODE first)
{
            NODE temp;
            /*Case 1: List is empty. Nothing to delete. */
            if(first==NULL)
            {
                        printf("\nList is empty. Cannot delete.");
                        return NULL;
            }

            /*Case 2: List has only one node. Deleting this node makes list empty. */
            if(first->link ==NULL)
            {
                        printf("\nItem that got deleted is %d", first->data);
                        free(first);
                        return NULL;
            }

            /*Case 3: List has more than one node. Delete the front node. Update the first pointer. */
            temp = first;
            first = first->link;
            printf("\nItem that got deleted is %d", temp->data);
            free(temp);
            return first;
}

void main()
{
             int ch, item;
            NODE first = NULL;
            while(1)
            {
                        printf("\n\n~~MENU~~");
                        printf("\n1.Insert at front");
                        printf("\n2.Delete from front");
                        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_front(first, item);
                                                            break;
                                    case 2:             first = delete_at_front(first);
                                                            break;
                                    case 3:             display(first);
                                                            break;
                                    case 4:                         exit(0);
                        }
            }
}

Output:

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 1
Enter the value: 11

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 1
Enter the value: 12

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 3
Contents are: 12        11

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 2
Item that got deleted is 12

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 2
Item that got deleted is 11

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 2
List is empty. Cannot delete.

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit
Enter your choice: 3

Contents are:
List is empty. Nothing to display.

~~MENU~~
1.Insert at front
2.Delete from front
3.Display
4.exit