Showing posts with label doubly linked list. Show all posts
Showing posts with label doubly linked list. Show all posts

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.

Doubly Linked List: Delete from Front

Doubly Linked List: Delete from Front


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

struct node
{
            int data;
            struct node *llink;
            struct node *rlink;
};
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->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_front(NODE first, int item)
{
            int val;
            NODE temp;
            temp = getnode();
            temp->data = item;
           
            if(first == NULL)
            {
                                    return temp;
            }

            temp->rlink = first;
            first->llink = temp;
            return temp;
}

NODE delete_at_front(NODE first)
{
            NODE temp;
            if(first == NULL)                         /*Case 1: List is empty*/
            {
                        printf("\nList is empty. Cannot delete.");
                        return NULL;
            }
             
            /*Case 2: List has only one node*/
            if(first->rlink == NULL) 
            {
                        printf("\nItem that got deleted is %d", first->data);
                        free(first);
                        return NULL;
            }
         
            /*Case 3: List is not empty*/
            temp = first;                                                  
            first = first->rlink;
            first->llink = NULL;
            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.
  

Doubly Linked List: Insert at End

Doubly Linked List: Insert at End


#include<stdio.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);
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;
            }
/*Case 2: List not empty.  Update the link field of last node to point to temp node.*/
            cur = first;
             while(cur->rlink != NULL)
            {
                        cur = cur->rlink;
            }         
            cur->rlink = temp;
            temp->llink = cur;
            return first;
}

void main()
{
            int ch, item;
            NODE first = NULL;
            while(1)
            {
                        printf("\n\n~~MENU~~");
                        printf("\n1.Insert at end");
                        printf("\n2.Display");
                        printf("\n3.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:             display(first);
                                                            break;
                                    case 3:     exit(0);
                        }
            }
}
Output:
~~MENU~~
1.Insert at end
2.Display
3.exit
Enter your choice: 1
Enter the value: 11

~~MENU~~
1.Insert at end
2.Display
3.exit
Enter your choice: 1
Enter the value: 12

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

Contents are: 11        12