Insertion in a Doubly Linked List

Singly Linked List is the list that holds the links to the next node and so on, each node points to the next node, but the main drawback is it does not point to the last node in the list,

Such a linked representation is called Doubly Linked List

Representation of Doubly Linked List:

A Doubly Linked List is a linear data structure, each node of which has one or more data fields but has only two link fields namely leftLink( lLink ) and rightLink( rLink ). The lLink field of a given node point to the node on its left and its rLink fields points to the one on the right.
A doubly Linked list may or may not have a head node. Again, it may or may not be circular.

Advantages of Doubly Linked List:

1. The availability of two links lLink and rLink permits forward and backward movement during the processing of the list.
2. The deletion of node X from the list calls only for the value X to be known.

Operations on a Doubly Linked List:

Insert Operation: To insert a node in a Doubly linked List check if the linked list is empty or not, if empty modify the head, if not empty insert at the end of the list.

Algorithm: To insert node X to the right of the node Y in  a Doubly Linked List

INSERT_DL ( X , Y )
    LLINK ( X ) = Y;
    RLINK ( X ) = RLINK( Y );
    LLINK ( RLINK ( Y )) = X;
    RLINK ( Y ) = X;
end INSERT_DL; 
Java code: 
Node insertEnd( Node head, int data )
{
    Node temp = new Node ( data );
    if( head == null )
        return temp;
    Node curr = head;
    while( curr.rLink != null )
        curr = curr.rLink;
    curr.rLink = temp;
    temp.lLink = curr;
    return head;
}

Explanation:

In the above code Node head points to the head of the linked list and data is the data to be inserted,

we create a new temporary node namely Temp  and store the data into the temporary node.

We check if the head of the linked list is empty or not if empty we return the data as the new head.

if there is some node in the list we iterate to the end of the list and append it to the last node creating the link to the new node from the last node.

If my data = 40, and

My list = 10->20->30->null

appending 40 at the end of the list

Output:

10->20->30->40->null

This is how we input a new node at the end of the linked list and change the lLink and rLink to point o the newly inserted node.