here is the method to insert a node at the front in the XORed doubly linked list or also known as memory efficient doubly linked list :
// To write a memory efficient linked list
#include using namespace std;
// Node structure of a memory efficient doubly linked list
class Node {
public:
int data;
Node *npx; // XOR of next and previous node
};
// return XORed value of the node address
Node *XOR(Node *a, Node *b){
return ((Node *)( (uintptr_t)(a) ^ (uintptr_t)(b) ));
}
// insert a node at the beggining of the XORed linked list and makes the newly inserted node as head
void insert(Node **head_ref, int data){
// allocate memory for new node
Node *new_node = new Node();
new_node->data = data;
// since node is inserted at the beggining, npx of the new node will always be XOR of curent head and null
new\_node->npx = XOR((\*head\_ref), nullptr);
// if the linked list is not empty, then npx of current head node will be XOR of new node and node next to current head
if(\*head\_ref != nullptr){
// (\*head\_ref)->npx is XOR of null and next.
// so if we do XOR of it with null, we get next
Node \*next = XOR((\*head\_ref)->npx, nullptr);
(\*head\_ref)->npx = XOR(new\_node, next);
}
// change head
\*head\_ref = new\_node;
}
// prints contents of doubly linked list in forward direction
void printList(Node *head){
Node *curr = head, *prev = nullptr, *next;
cout << "Following are the nodes of Linked List: \\n";
while(curr != nullptr) {
// print current node
cout << curr->data << " ";
// get the address of next node : curr->npa is next^prev,
// so curr->npx^prev will be next^prev^prev which is next
next = XOR(prev, curr->npx);
// update prev and curr for next iteration
prev = curr;
curr = next;
}
}
// Driver function
int main(){
Node *head = nullptr;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
insert(&head, 50);
insert(&head, 60);
printList(head);
return 0;
}
Here is the code i have tried to put an element at the back of the list:
Node *insert(Node **last, int data){
// allocate memory for new node
Node *new_node = new Node();
new_node->data = data;
new\_node->npx = XOR(\*last, nullptr);
if(\*last != nullptr) {
Node \*prev = XOR((\*last)->npx, nullptr)