Doubly Linked List

Doubly linked list is an another Data Structure, that is an advance version of singly linked list. In this data structure, a node can have previous and next pointer that allows the list to be traverse in both the direction.

Doubly Linked List:

1. Each node point not only its successor(previous) but the predecessor(next)
2. There are two NULL point that is at last node next and at the first node prev.
3. Easy to traverse the list in both the direction

Advantage over singly Linked List

•  Doubly link list allow the traversal in both the direction. Therefore, suitable for sorting the elements of the list. 

Disadvantage over singly Linked List

• Every node of DLL required extra space to store another prev pointer.
• All operation required additional pointer to previous to be maintained

 

Implementation of structure

#include
#include

struct node
{
int data;
struct node *prev,*next;
}*head=NULL,*temp=NULL;

struct node *createNode()
{
int n;
struct node *newNode=(struct node*)malloc(sizeof(struct node));
printf("enter the data\n");
scanf("%d",&n);
newNode->data=n;
newNode->prev=NULL;
newNode->next=NULL;
return newNode;
}

void insertAtBeg()
{
if(head==NULL)
{
temp=createNode();
head=temp;
}
else
{
temp=createNode();
temp->next=head;
head->prev=temp;
head=temp;
}
}

void insertAtend()
{
if(head==NULL)
{
printf("list is empty");
exit(0);
}
else
{
struct node *p=head;
while(p->next!=NULL)
{
p=p->next;
}
temp=createNode();
temp->prev=p;
p->next=temp;
temp->next=NULL;
}
}

void delfront()
{
if(head==NULL)
{
printf("list is empty");
exit(0);
}
else
{
if(head->next==NULL)
{
temp=head;
head=NULL;
free(temp);
}
else
{
temp=head;
head=temp->next;
head->prev=NULL;
free(temp);
}
}
printf("Delete was sucessfully\n");
}

void delend()
{
if(head==NULL)
{
printf("List is empty\n");
exit(0);
}
else
{
if(head->next==NULL)
{
temp=head;
head=NULL;
free(temp);
}
else
{
struct node *p=head;
while(p->next!=NULL)
{
p=p->next;
}
temp=p;
temp=temp->prev;
temp->next=NULL;
free(p);
}
}
printf("Delete was sucessfull");
}

void display()
{
if(head==NULL)
{
printf("List is empty\n");
exit(0);
}
else
{
temp=head;
while(temp!=NULL)
{
printf("%d",temp->data);
printf("-><- span="">
temp=temp->next;

}
}
}

int main()
{
int choice;
while(1)
{
printf("1: Insert at Begining\n");
printf("2: Display the list\n");
printf("3: Insert at end\n");
printf("4: Delete from front\n");
printf("5: Delete from end\n");
printf("6: Exit\n");
printf("------------------------------\n");
printf("enter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
    insertAtBeg();
    break;
case 2:
    display();
    break;
case 3:
    insertAtend();
    break;
case 4:
    delfront();
    break;
case 5:
    delend();
    break;
case 6:
    exit(0);
    break;
default :
    printf("enter choice is incorrect");
}
}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Output