Given a XOR linked list and two integers position and value, the task is to insert a node containing value as the positionth node of the XOR Linked List.
Examples:
Input: 4<–>7<–>9<–>7, position = 3, value = 6
Output: 4<–>7<–>6<–>9<–>7
Explanation:
Inserting a node at the 3rd position with value 6 modifies the given XOR Linked List to 4<–>7<–>6<–>9<–>7.Input: 4<–>7<–>9<–>7, position=6, value=6
Output: Invalid Position
Explanation: Since the given list consists of only 4 elements, 6th position is an invalid position in the given list.
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say ctr to keep a count of the nodes traversed in the given XOR linked list.
- Traverse the given XOR linked list. For every node of the XOR Linked List, check if the position of the current node in equal to position or not. If found to be true, then insert the node in the given XOR linked list.
- Otherwise, increment ctr by 1.
- If the entire list is traversed and positionth node was not obtained, then print “Invalid Position”.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};// Function to find the XOR of two nodesstruct Node* XOR(struct Node* a, struct Node* b){ return (struct Node*)((uintptr_t)(a)^ (uintptr_t)(b));}// Function to insert a node with// given value at given positionstruct Node* insert(struct Node** head, int value, int position){ // If XOR linked list is empty if (*head == NULL) { // If given position // is equal to 1 if (position == 1) { // Initialize a new Node struct Node* node = new Node(); // Stores data value in // the node node->data = value; // Stores XOR of previous // and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If required position was not found else { cout << "Invalid Position\n"; } } // If the XOR linked list // is not empty else { // Stores position of a node // in the XOR linked list int Pos = 1; // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Stores the XOR of next // node and previous node struct Node* next = XOR(prev, curr->nxp); // Traverse the XOR linked list while (next != NULL && Pos < position - 1) { // Update prev prev = curr; // Update curr curr = next; // Update next next = XOR(prev, curr->nxp); // Update Pos Pos++; } // If the position of the current // node is equal to the given position if (Pos == position - 1) { // Initialize a new Node struct Node* node = new Node(); // Stores pointer to previous Node // as (prev ^ next ^ next) = prev struct Node* temp = XOR(curr->nxp, next); // Stores XOR of prev and new node curr->nxp = XOR(temp, node); // Connecting new node with next if (next != NULL) { // Update pointer of next next->nxp = XOR(node, XOR(next->nxp, curr)); } // Connect node with curr and // next curr<--node-->next node->nxp = XOR(curr, next); node->data = value; } // Insertion node at beginning else if (position == 1) { // Initialize a new Node struct Node* node = new Node(); // Update curr node address curr->nxp = XOR(node, XOR(NULL, curr->nxp)); // Update new node address node->nxp = XOR(NULL, curr); // Update head *head = node; // Update data value of // current node node->data = value; } else { cout << "Invalid Position\n"; } } return *head;}// Function to print elements of// the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer // in current node struct Node* curr = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; // Stores XOR pointer of // in next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print current node cout << curr->data << " "; // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Driver Codeint main(){ /* Create following XOR Linked List head-->20<-->40<-->10<-->30 */ struct Node* head = NULL; insert(&head, 10, 1); insert(&head, 20, 1); insert(&head, 30, 3); insert(&head, 40, 2); // Print the new list printList(&head); return 0;} |
C
// C++ program to implement// the above approach#include <inttypes.h>#include <stdio.h>#include <stdlib.h>// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};// Function to find the XOR of two nodesstruct Node* XOR(struct Node* a, struct Node* b){ return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));}// Function to insert a node with// given value at given positionstruct Node* insert(struct Node** head, int value, int position){ // If XOR linked list is empty if (*head == NULL) { // If given position // is equal to 1 if (position == 1) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores data value in // the node node->data = value; // Stores XOR of previous // and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If required position was not found else { printf("Invalid Position\n"); } } // If the XOR linked list // is not empty else { // Stores position of a node // in the XOR linked list int Pos = 1; // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Stores the XOR of next // node and previous node struct Node* next = XOR(prev, curr->nxp); // Traverse the XOR linked list while (next != NULL && Pos < position - 1) { // Update prev prev = curr; // Update curr curr = next; // Update next next = XOR(prev, curr->nxp); // Update Pos Pos++; } // If the position of the current // node is equal to the given position if (Pos == position - 1) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores pointer to previous Node // as (prev ^ next ^ next) = prev struct Node* temp = XOR(curr->nxp, next); // Stores XOR of prev and new node curr->nxp = XOR(temp, node); // Connecting new node with next if (next != NULL) { // Update pointer of next next->nxp = XOR(node, XOR(next->nxp, curr)); } // Connect node with curr and // next curr<--node-->next node->nxp = XOR(curr, next); node->data = value; } // Insertion node at beginning else if (position == 1) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Update curr node address curr->nxp = XOR(node, XOR(NULL, curr->nxp)); // Update new node address node->nxp = XOR(NULL, curr); // Update head *head = node; // Update data value of // current node node->data = value; } else { printf("Invalid Position\n"); } } return *head;}// Function to print elements of// the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer // in current node struct Node* curr = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; // Stores XOR pointer of // in next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print current node printf("%d ", curr->data); // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Driver Codeint main(){ /* Create following XOR Linked List head-->20<-->40<-->10<-->30 */ struct Node* head = NULL; insert(&head, 10, 1); insert(&head, 20, 1); insert(&head, 30, 3); insert(&head, 40, 2); // Print the new list printList(&head); return (0);} |
Python3
# importing necessary modulesimport ctypes# creating a node classclass Node: def __init__(self, data): self.data = data self.link = 0# creating a XOR linked list classclass XorLinkedList: # constructor def __init__(self): self.head = None self.nodes = [] # method to return a new instance of type def type_cast(self, id): return ctypes.cast(id, ctypes.py_object).value # method to traverse linked list def forward_traversal(self): # if linked list is empty if(self.head == None): print("Empty") else: prev_id = 0 current = self.head # print the first node of linked list print(current.data, end="->") next_id = 1 # print the whole linked list while(next_id): next_id = prev_id ^ current.link if(next_id): prev_id = id(current) current = self.type_cast(next_id) print(current.data, end="->") # method to insert a node at a given position def insert_at_position(self, key, position): # a node can be inserted below 1 position if(position < 1): print("Can't insert") # if node to be inserted at the beginning elif(position == 1): n = Node(key) # if linked list is empty, update the head if(self.head == None): self.head = n # if linked list is not empty, update the link fielf of head, newly inserted node and head pointer. else: self.head.link = id(n) ^ self.head.link n.link = id(self.head) self.head = n self.nodes.append(n) # if node to be inserted at position>1 else: # if linked list is empty and node to be inserted at position>1 if(self.head == None): print("Out of range") else: n = Node(key) current = self.head m = id(current) i = 1 prev_id = 0 next_id = 1 # Traverse the linked list until desired position is reached while(next_id and i < position-1): next_id = prev_id ^ current.link prev_id = id(current) if(next_id): current = self.type_cast(next_id) m = id(current) i = i+1 else: break if(i == position-1): next_id = prev_id ^ current.link current.link = current.link ^ next_id ^ id(n) # if position is not the last if(next_id): nxt = self.type_cast(next_id) nxt.link = id(n) ^ nxt.link ^ id(current) n.link = id(current) ^ id(nxt) # if position is the last else: n.link = id(current) self.nodes.append(n) # if position exceeds the length of linked list else: print("out of range")# creating a XOR linked list objectobj = XorLinkedList()obj.insert_at_position(10, 1)obj.insert_at_position(20, 1)obj.insert_at_position(30, 3)obj.insert_at_position(40, 2)obj.forward_traversal() |
Output
20 40 10 30
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
