## Pages

### 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;