Data Structure - [Doubly Linked List]

♠ Posted by Unknown in , at 11:26

Doubly Linked list Operations


A doubly linked list is defined as a collection of nodes. Each node has three parts.
1.      Information
2. Pointer to previous node
3.      Pointer to next node


Image: Doubly Linked List Node

Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.


Doubly linked list creation algorithm

Step 1 :  [Initilization]
1)      Start. Next = null
2)      Previous. Next = null
Step 2 :   [Assign address of start variable to node]
               Node = address of start
Step 3 :    [Make left and right links of a node]
1)      Next [node] = node [make link to node]
2)      Previous [node] = node [make link to node]
3)      Node = Next [node] [Move  pointer to next node]
4)      Info [node] = value [Information value of a node]
5)      Next  [node] = NULL  [Assign NULL  to the address field]
Step 4 :    [ Call  Step 3]
                Repeat Step 3 to create required number of nodes for linked list
Step  5 :   End .

Algorithm for traversing a doubly inked list


Step 1 :  [initialization]
              Node = start. Next [points to the first node in the list]
Step 2 :  [Traverse the list in forward direction]
               Repeat while Next [node] # NULL process Info [Node]
Step 3 :  [Traverse the list in backward direction]
               Repeat while Node # NULL  Process Info [Node]
Step 4 :  Exit.

Algorithm to insert a node at right of the right most node

Step 1 :    [Initialization]
                Node =Start
Step 2 :    [Create a new node]
  New = Create  a Node
Step 3 :    [Read information associated with newly created node]
                 Info [Newly] = value
Step 4 :    [Perform the insertion]
 I)  Next [new] = node
II)                  Previous [New] = Previous [node]
III)                Next [Previous[node]] = New
IV)               Next [Node] = New
Step 5 :   Exit

Algorithm to delete right most node

Step 1 : [Initialization]
             Node  = Start
Step 2 : [Initialization counter]
             Counter = 0
Step 3 : [check the list]
             If  Node  = Null
             Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
             Repeat while Node # NULL
I)                    Node = Next [Node]
II)                  Counter = Counter + 1
Step 5 : [perform deletion]
             Node = Start
             Repeat through (II) while counter # 1
I)                    Node = Next [Node]
II)                  Counter = Counter – 1
III)                Next [previous[node]] = Next [Node]
IV)               Previous [Next [node]] = previous [node]
V)                 Delete (node)
Step 6 : Exit.

Algorithm to delete a desired node

Step 1 : [Initialization]
             Node = Start
Step 2 : [Check the list]
             If node = NULL
             Output “underflow” and Exit
Step 3 : [Set the counter ]
             Search = 0
Step 4 : [Input the node number to which you want to delete]
             Node delete = value
Step 5 : [Perform deletion]
             Repeat while Node # NULL
             If Search = Delete _Node
             Next [Previous [Node]] = Next [Node]
             Previous [Next[Node]] = Previous [Node]
             Delete (Node)
             Else
                   Node = Next [node]
                   Search = Search + 1
Step 6 : Exit


Example:

#include<stdio.h>
#include<malloc.h>
struct dnode
{
            struct dnode *prv;
            int data;
            struct dnode *next;
};

main()
{
            struct dnode *p;
            int ans;
            p=NULL;
            clrscr();
            do
            {
                        printf("\n1:enter new node:\n");
                        printf("2:enter new node at begining:\n");
                        printf("3:enter new node at position:\n");
                        printf("4:display value:\n");
                        printf("5:delete node:\n");
                        printf("6:exit\n");
                        printf("enter your choice :");
                        scanf("%d",&ans);
                        switch(ans)
                        {
                                    case 1:
                                                append(&p);
                                                break;
                                    case 2:
                                                addatbeg(&p);
                                                break;
                                    case 3:
                                                addatpos(&p);
                                                break;
                                    case 4:
                                                display(p);
                                                break;
                                    case 5:
                                                deletatpos(&p);
                                                break;
                                    case 6:
                                                exit(0);
                                                break;
                        }
            }while(ans!=6);
            getch();
            return;
}

append(struct dnode **q)
{
            struct dnode *temp,*r;
            int n;
            temp=(*q);
            if(*q==NULL)
            {
                        *q=(struct dnode*)malloc(sizeof(struct dnode*));
                        (*q)->prv=NULL;
                        (*q)->next=NULL;
                        temp=(*q);
            }
            else
            {
                        while(temp->next!=NULL)
                                    temp=temp->next;
                        r=(struct dnode*)malloc(sizeof(struct dnode));
                        temp->next=r;
                        r->prv=temp;
                        r->next=NULL;
                        temp=temp->next;
            }
            printf("Enter value:");
            scanf("%d",&n);
            temp->data=n;
            return;
}

addatbeg(struct dnode **q)
{
            struct dnode *temp;
            int n;
            temp=(struct dnode*)malloc(sizeof(struct dnode));
            temp->prv=NULL;
            temp->next=*q;
            (*q)->prv=temp;
            printf("Enter value:\n");
            scanf("%d",&n);
            temp->data=n;
            (*q) = (*q)->prv;
            return;
}

addatpos(struct dnode **q)
{
            struct dnode *temp;
            int pos,n,flag=0;
            printf("Enter position:\n");
            scanf("%d",&pos);
            while((*q)->next!=NULL)
            {
                        if((*q)->data==pos)
                        {
                                    flag=1;
                                    break;
                        }
                        else
                        {
                                    flag=0;
                        }
                        (*q)=(*q)->next;
            }



            if(flag==1)
            {
                        printf("enter value :");
                        scanf("%d",&n);
                        temp=(struct dnode*)malloc(sizeof(struct dnode));
                        temp->prv=(*q)->prv->next;
                        (*q)->prv->next=temp;
                        temp->next=*q;
                        (*q)->prv=temp;
                        temp->data=n;
            }
            else
            {
                        printf("element is not available:\n");
            }
            return;
}

deletatpos(struct dnode **q)
{
            struct dnode *temp;
            int n;
            printf("Enter the position:\n");
            scanf("%d",&n);
            temp=*q;
            while(temp->next!=NULL)
            {
                        if(temp->data==n)
                        {
                                    if(temp==*q)
                                    {
                                                (*q)=(*q)->next;
                                                (*q)->prv=NULL;
                                    }
                                    else
                                    {
                                                if(temp->next==NULL)
                                                            temp->prv->next=NULL;
                                                else
                                                {
                                                            temp->prv->next=temp->next;
                                                            temp->next->prv=temp->prv;
                                                            free(temp);
                                                }

                                    }
                        }temp=temp->next;

            }
            return;
}

display(struct dnode *q)
{
            while(q!=NULL)
            {
                        printf("%d ",q->data);
                        q=q->next;
            }
            return;}

0 comments:

Post a Comment