XOR Linked List

Introduction :-

→ Memory Efficient implementation of Doubly Linked Lists.

→ In this, we use ONE POINTER for both moving forward and backward.

In XOR LL, we store XOR of previous Node Address and next Node Address in current Node Address Part :-

Iteration Forward :-

Iteration Backward :-

C++ Implementation :-

#include<bits/stdc++.h>
#include <cinttypes>
using namespace std;

class Node{
   public:
      int data;
      Node* xnode;
};

/*
reinterpret_cast :-
It is used to convert a pointer of some data type into a pointer of another data type,
   int* p = new int(65);
   char* ch = reinterpret_cast<char*>(p);  // here ch = A, as p casted to char pointer and assigned to ch pointer.
*/

Node* Xor(Node* x, Node* y){
   return reinterpret_cast<Node*>( reinterpret_cast<uintptr_t>(x) ^ reinterpret_cast<uintptr_t>(y));
}


void insertFirst(Node** head,int data){
   Node* new_node = new Node();
   new_node -> data = data;

   new_node -> xnode = *head;

   if (*head != NULL) {
      (*head)-> xnode = Xor(new_node, (*head) -> xnode);
   }
 
   *head = new_node;
}

void printList(Node* head)
{
   Node* curr = head;
   Node* prev = NULL;
   Node* next;
 
   while (curr != NULL) {
      cout << curr -> data << " ";
      next = Xor(prev, curr -> xnode);
      prev = curr;
      curr = next;
   }

   cout<<"\n\n";
   curr = prev;
   next = NULL;
   while (curr != NULL) {
      cout << curr -> data << " ";
      prev = Xor(next, curr -> xnode);
      next = curr;
      curr = prev;
   }
}

int main(){

   Node* head = NULL;
   insertFirst(&head, 10);
   insertFirst(&head, 20);
   insertFirst(&head, 30);
   insertFirst(&head, 40);
 
   printList(head);
   
   return 0;
}

Thanks For reading…

Keep Coding and Exploring…..