Algorithm for Insertion of node in Two way linked list using single pointer field


TwoWayLinkedList_SinglePtr(List,Start,End,Value,Node,Curr,Prev,NextNode,N_NextNode)

Concept: In 2way linked list with single pointer, each node consists of 1 data part and 1 pointer part. The pointer part will now contain XOR of the address of Previous and Next Node. Reason behind using difference XOR is, if XORing for A and B gives C then XORing of C with A gives B and XORing of C with B gives A as result, So that it is easy to find Next Node's Address by using XOR with stored values.
List: It is actually the list in which Node is to be inserted.
START: Pointer contains the address of Starting Node.
END: Pointer contains the address of Ending Node.
Node: Node which is to be inserted.
Curr: Pointer pointing the current node, this will be used to traverse the list
Prev: Pointer pointing the Previous node
Value: Value of a Node after which new node is to be inserted
NextNode: this will contain address of the node which is next to current node
N_NextNode: this will contain address of Node which is next to NextNode.



Initialization: i=0
Step 1: [If List is empty and New node is the first node to be inserted]
             If START = null then
                     START=Node; END=Node
                     End;
Step 2: Curr = START
Step 3: [Find the node after which new node is to be inserted]
              a.  Repeat step b to c untill the node after which new node is to be inserted or Curr!=END.
              b.  if Curr-> Data = Value then
                       break;
              c.  TEMP = Curr
                   if PREV = null then
                       Curr = Curr->Next
                   else
                       Curr = PREV xor Curr->Next
                   PREV = TEMP
Step 4: [Now Curr contains the address of the node after which we have to insert new node, PREV contains the address of the previous node to Curr]
                [If node is to be inserted at last position]
                if Curr = END then
                    Node->Next = Curr;
                    Curr->Next = PREV xor Node
                    END = Node;
                    End;
            
Step 5:
             a.  [If New node is to be inserted at 2nd place in the list]
                  If PREV = null then
                      i.  [There is only 1 node in the list]
                             if START = END then
                                 Curr->Next = Node;
                                 Node->Next = Curr;
                                 END = Node;
                                 End;
                      ii. [ If there are multiple nodes in the list]
                                 NextNode = Curr->Next;
                                 N_NextNode = Curr xor NextNode->Next
                                
                                [if there are only two nodes in the list]
                                A) if N_NextNode =0 then
                                        Curr->Next = Node;
                                        NextNode->Next = Node;
                                        Node->Next = Curr xor NextNode
                                     else
                                       Curr->Next = Node;
                                        Node->Next = NextNode xor Curr
                                        NextNode->Next = N_NextNode xor Node
                       iii. End;
               b. [If new node is to be inserted in the middle of the list]
                           NextNode = Curr->Next xor PREV;
                           N_NextNode = Curr xor NextNode->Next
                           Curr->Next = PREV xor Node
                           Node->Next = Curr xor NextNode
                                [If new Node is to be inserted at 2nd Last position]
                                If N_NextNode=0 then
                                       NextNode->Next = Node
                                else
                                       NextNode->Next = N_NextNode xor Node
               c. End;

No comments:

Post a Comment