Inserting Node in Two Way Linked List

As we all know, in Two-Way linked list there are two Pointer's fields, with a data Field. One Pointer Field is known as Previous Pointer, which points Previous Node. Previous Pointer will be null, if it is First Node. Another Pointer Field is known as Next Pointer, which points to the next node. Next Pointer will be null if it is last node. There are Two External pointer called Start & End. Start pointer points Starting node of the list, End pointer points the last pointer of the List.

                   

Insert_Node_2wayList(List,DataAfter,Start,End,NewNode)

Here List is a 2 way linked list containing n Nodes. Start, End are the starting and Ending pointers pointing to the First and Last Node of the List. DataAfter is a value in a Node after which the NewNode will have to be inserted. 

Ptr is an intermediate pointer which will be used to traverse the list

Conventions: <> = Not Equals to

Step 1: [checking, if List is empty]

            if Start=null then

                   NewNode->Prev = null

                   NewNode->Next = null

                   Start = NewNode

                   End = NewNode

                   return Success;

Step 2:[Initializing the pointer]

           Ptr = Start

Step 3: [List is Not Empty Now Searching for the Node after which new Node is to be inserted. After this loop Ptr pointer of the node after which new node is to be inserted or null if the node not found]

            While Ptr <> null and Ptr->Data <> DataAfter repeat the step

                          i) Ptr=Ptr->Next

Step 4: [Check, if the Node found or not]

            if Ptr = null then

                 return Failure;

Step 5: [Inserting node]

             NewNode->Prev = Ptr              [New Node's Previous pointer will point current Node]

             NewNode->Next = Ptr->Next  [New Node's Next pointer will point Next Node current Node]

             Ptr->Next->Prev = NewNode  [Next Node of current node will point new node]

             Ptr->Next = NewNode              [Next of Current Node will point new node]

Step 6: return Success;

Algorithm to insert node in Simple Linked List

Insert_LinkedList ( List, Node, Start, Value,Data)

In this algorithm List is a linked list having n nodes. Start is a pointer which contains the address of starting node of the list.Node  is the pointer pointing to the new node. Value is the data of a node from list after which the new node is to be inserted.Data is the value which is to be assigned to the data part of new node.

Node->data contains data and Node->Next points next node. In this algorithm following criteria are followed.

• If List is empty Node will be inserted at starting of list
• If Value found in the list than node will be inserted after the value
• else node will be inserted at the end of list

Ptr is an intermediate pointer which points the current node and used to traverse the list

Step 1: i) Node ->data = Data

Step 2: [Check if list is empty then we will insert new node at the starting point.]

            If Start = null then go to step 3 else go to step 4

Step 3: i) Node->Next=null.

            ii) Start=Node

            iii) Return

Step 4: [assigning the 1st node address to Ptr]

                  Ptr = Start

Step 5: While Ptr->Next is Not null repeat

            i) if Ptr->data = Data then go to step i.a else go to step ii)

                     a) Node->Next = Ptr->Next

                     b) Ptr->Next = Node

                     c) Return

           ii) Ptr = Ptr->Next

Step 6: [If Value that was searched not found, in that case inserting Node at the end of List]

            i)Node->Next = null

           ii)Ptr->Next = Node

Step 7: End

Algorithm: To insert element in array

Algorithm: InsertElementInArray(dataVal, valArray[], n, k,m)

In this algorithm dataVal is an element which is to be inserted in an array named valArray, whose size is n. we have to insert the element dataVal at index k. m is the total present elements in the array where m<n
*considering lower bound of array is 1.

Step 1: [Check for the size of array]
         if n < k then

                   a) RaiseError "Array Index out of bound"

                   b) goto step 5

Step 2: [Shifting the elements from k indexed elements by 1]

           i) for index = m  to k repeat step a to b

                 a) valArray[index+1] = valArray[index]
             
                 b) [Decrements counter]   index = index - 1

           ii) goto to step 3

Step 3: [Now Insert the element]

            valArray[k] = dataVal;

Step 4: Exit

Explanation