**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