Doubly linked list

Concept 

Doubly linked list is a data structure comprising of nodes which store data and pointers to the previous and next node.

A node comprises of the following fields.

pre pointer : This pointer points to the previous node of the list.

data field where data is stored.

next pointer : This pointer points to the next node of the list.

head is a pointer pointing to the 1st node. 
prev pointer of the 1st node and next pointer of the last node point to NULL.

Lets say we have an organization in which some employees work and you have to store their details.You should also be able to add,delete and modify employee details.For better understanding I have taken only employee id in employee details.Here we will treat a employee as node.

Building a linked list

1.  Declare a node structure

typedef struct 
{
        int id;
        struct node *pre,*next;                //for storing address of prev and next node
}node;

2.  Create a linked list

node* create()
{
    node* head;
    head=(node*)malloc(sizeof(node));         /*allocating memory to node
                                                and head is pointing to it  */

    printf("\nEnter employee id ");
    scanf("%d",&head->id);

    head->pre=head->next=NULL;

    return head;
}

3.  Append a node to a linked list

node* append(node* head)
{
    node* curr = (node*)malloc(sizeof(node));  //allocate memory for current node

    node* prev=head;

    printf("\nEnter employee id ");
    scanf("%d",&curr->id);

    while(prev->next!=NULL)                    //traverse the list and go to the last node
        prev=prev->next;

    prev->next=curr;                          /*establish the link between last node
                                               (pointed by prev) and curr node   */

    curr->pre = prev;
    curr->next=NULL;

    return head;
}

4.  Modify a node of a linked list

node* modify(node* head)
{
    node* curr=head;
    int eid,found=0;

    printf("\nEnter Eid of employee whose data is to be modified ");
    scanf("%d",&eid);

    while(curr!=NULL)                                     //traverse list in search of eid
    {
           if(curr->id==eid)
           {
              found = 1;
              break;
           }
           else
              curr=curr->next;
    }
    if(found == 1)                                       //eid is found
    {
            printf("\nEnter employee id ");
            scanf("%d",&curr->id);
    }
    else
            printf("\nEmployee id not found");

    return head;
}

5.  Delete node from a linked list

node* del(node* head)
{
    node *prev,*curr=head;
    int eid;

    printf("\nPlease enter employee id to be deleted ");
    scanf("%d",&eid);

    if(head==NULL)
         return NULL;

    else if(curr->id==eid && curr->next==NULL)          //only 1 node
         head=NULL;

    else if(curr->id==eid && curr->next!=NULL)          //1st node
    {
         head=head->next;
         head->pre=NULL;
    }
    else
    {
         while(curr!=NULL)                              //search eid
         {
              if(curr->id==eid)
                  break;
              else
              {
                 prev=curr;
                 curr=curr->next;
              }
         }

         if(curr!=NULL)                             //if eid found
         {      
              prev->next=curr->next;               /*establish the link between node pointed by prev
                                                     & node next to node pointed by curr */
             (*(curr->next)).pre = prev;
         }
    }

    if(curr!=NULL)                                 //eid found
         free(curr);
    else
         printf("\nEmployee id not found");

    return head;
}

Here curr  = points to the node to be deleted

prev = points to the node just previous to the current node

Suppose we have

We have to delete node pointed by curr,so we need to establish link between node 1 and node 3.

How?

curr->next stores address of node 3.If we assign curr->next(i.e address of node 3) to prev->next then prev->next would point to node 3 and hence link would be established.Then we would free memory pointed to by curr.

Diagram after deletion of node 2.

6.  Display linked list

void display(node* head)
{
    node* curr=head;

    if(curr==NULL)
         printf("\nList is empty");
    else
    {
         printf("\n");
         while(curr!=NULL)
         {
              printf("%d---",curr->id);
              curr=curr->next;
         }
    }
}

Complete code with output