HarishGadade

Double Linked List

Linear Search and Binary Search PPT

Restrictions of SLL

- if we want to display the linked list in both directions is not possible in singled linked list.

- if we want to delete any arbitrary node from the linked list say P, then we need the preceding node of P.

In such situation use Doubly Linked List.

//Double Linked List Implementation

#include<stdio.h>
#include<stdlib.h>
struct node
{
    struct node *Llink;
    int data;
    struct node *Rlink;
};
struct node *create(struct node *);
void display_forward(struct node *);
void display_backword(struct node*);
struct node *getnode(int);
struct node *findlast(struct node *);
void insert(struct node *start);
struct node *delet(struct node *head);
void main()
{
    struct node *head=NULL;
    int choice;
    while(1)
    {
        printf("\n1. Create DLL");
        printf("\n2. Display Froward");
        printf("\n3. Display Backword");
        printf("\n4. Insert into DLL");
        printf("\n5. Delete from DLL ");
        printf("\n0. Exit");
        printf("\nEnter your choice : ");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
                head=create(head);
                break;
            case 2:
                display_forward(head);
                break;
            case 3:
                display_backword(head);
                break;
            case 4:
                insert(head);
                printf("\nForward Display   : ");
                display_forward(head);
                printf("\nBackword Display : ");
                display_backword(head);
                break;
            case 5:
                head=delet(head);
                printf("\nForward Display   : ");
                display_forward(head);
                printf("\nBackword Display : ");
                display_backword(head);
                break;
            case 0:
                exit(0);
                break;

            default:
                printf("\nWrong choice!!");
        }
    }
}

struct node *getnode(int x)
{
    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->Llink=NULL;
    temp->data=x;
    temp->Rlink=NULL;
    return(temp);
}
struct node *findlast(struct node *head)
{
    struct node *ptr;
    for(ptr=head;ptr->Rlink!=NULL;ptr=ptr->Rlink);
    return(ptr);
}
struct node *create(struct node *head)
{
    struct node *ptr,*temp;
    int x;
    char ch;
    do
    {
        printf("\nEnter Node Data : ");
        scanf("%d",&x);
        temp=getnode(x);
        if(head==NULL)
            head=temp;
        else
        {
            ptr=findlast(head);
            ptr->Rlink=temp;
            temp->Llink=ptr;
        }
        printf("\nWant to add one more node(y/n) : ");
        scanf("%s",&ch);
    }while(ch=='y');
    return(head);
}
void display_forward(struct node *head)
{
    struct node *ptr;
    for(ptr=head;ptr!=NULL;ptr=ptr->Rlink)
    {
        printf("%d ",ptr->data);
    }
}
void display_backword(struct node* head)
{
    struct node *ptr;
    for(ptr=findlast(head);ptr!=NULL;ptr=ptr->Llink)
        printf("%d ",ptr->data);
}
void insert(struct node *head)
{
    struct node *temp,*ptr;
    int x,value;
    printf("\nEnter node after which you want to insert : ");
    scanf("%d",&value);
    printf("\nEnter New Node to Insert : ");
    scanf("%d",&x);
    temp=getnode(x);
    for(ptr=head;ptr!=NULL && ptr->data!=value;ptr=ptr->Rlink);
    if(ptr->Rlink==NULL)    //If inserting after last node
    {
        ptr->Rlink=temp;
        temp->Llink=ptr;
    }
    else        // if inserting in between two nodes
    {
        temp->Rlink=ptr->Rlink;
        ptr->Rlink->Llink=temp;
        ptr->Rlink=temp;
        temp->Llink=ptr;
    }
}
struct node *delet(struct node *head)
{
    struct node *ptr;
    int value;
    printf("\nEnter node to be deleted : ");
    scanf("%d",&value);
    for(ptr=head;ptr!=NULL && ptr->data!=value;ptr=ptr->Rlink);
    if(ptr->Llink==NULL)    //if Deleting node is first
    {
        head=ptr->Rlink;
        head->Llink=NULL;
        free(ptr);
    }
    else if(ptr->Rlink==NULL)   // if Deleteing node is last
    {
        ptr->Llink->Rlink=NULL;
        free(ptr);
    }
    else        //If Deleting Node is Arbitrary node
    {
        ptr->Llink->Rlink=ptr->Rlink;
        ptr->Rlink->Llink=ptr->Llink;
        free(ptr);
    }
    return(head);
}
Output of above program is
/*
harish@harish-Inspiron-3537:~/harish/ds/DSF$ gcc dll.c
harish@harish-Inspiron-3537:~/harish/ds/DSF$ ./a.out

1. Create DLL
2. Display Froward
3. Display Backword
4. Insert into DLL
5. Delete from DLL
0. Exit
Enter your choice : 1

Enter Node Data : 10

Want to add one more node(y/n) : y

Enter Node Data : 20

Want to add one more node(y/n) : y

Enter Node Data : 30

Want to add one more node(y/n) : y

Enter Node Data : 40

Want to add one more node(y/n) : n

1. Create DLL
2. Display Froward
3. Display Backword
4. Insert into DLL
5. Delete from DLL
0. Exit
Enter your choice : 2
10 20 30 40
1. Create DLL
2. Display Froward
3. Display Backword
4. Insert into DLL
5. Delete from DLL
0. Exit
Enter your choice : 5

Enter node to be deleted : 10

Forward Display   : 20 30 40
Backword Display : 40 30 20
1. Create DLL
2. Display Froward
3. Display Backword
4. Insert into DLL
5. Delete from DLL
0. Exit
Enter your choice : 0
harish@harish-Inspiron-3537:~/harish/ds/DSF$
*/

Data Strucrures

Double Linked List