Data Structures and Algorithms - Old Questions

8. How do you insert a nodes at last in doubly linked list? Explain.

Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.

Steps to insert a nodes at last in doubly linked list

1. Allocate memory for the new node as,

        newnode=(NodeType*)malloc(sizeof(NodeType))

2. Assign value to info field of a new node

        set newnode->info=item

3. set newnode->next=NULL

4. if head==NULL

        set newnode->prev=NULL;

        set head=newnode;

5. if head!=NULL

        set temp=head

        while(temp->next!=NULL)

            temp=temp->next;

        end while

        set temp->next=newnode;

        set newnode->prev=temp

6. End