XOR Linked List: Remove last node of the Linked List
Given an XOR linked list, the task is to delete the node at the end of the XOR Linked List.
Examples:
Input: 4<–>7<–>9<–>7
Output: 4<–>7<–>9
Explanation: Deleting a node from the end modifies the given XOR Linked List to 4<–>7<–>9Input: 10
Output: List is empty
Explanation: After deleting the only node present in the XOR Linked List, the list becomes empty.
Approach: The idea to solve this problem is to traverse the XOR linked list until the last node is reached and update the address of its previous node. Follow the steps below to solve the problem:
- If the XOR linked list is empty, then print “List is empty“.
- Traverse the XOR Linked List until the last node of the Linked List is reached.
- Update the address of its previous node.
- Delete the last node from memory.
- If the list becomes empty after deleting the last node, then print “List is empty”. Otherwise, print the remaining nodes of the linked list.
Below is the implementation of the above approach:
C++
// C++ program for 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){ // If XOR linked list is empty if (*head == NULL) { // 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 the XOR linked list is not empty else { // Stores the address of current node struct Node* curr = *head; // Stores the address of previous node struct Node* prev = NULL; // 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; } 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; }}// Function to delete the last node present in the XOR Linked Liststruct Node* delEnd(struct Node** head){ // Base condition if (*head == NULL) cout << "List is empty"; else { // 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 (XOR(curr->nxp, prev) != NULL) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; } // If the Linked List contains more than 1 node if (prev != NULL) { prev->nxp = XOR(XOR(prev->nxp, curr), NULL); } // Otherwise else { *head = NULL; } // Delete the last node from memory delete(curr); } // Returns head of new linked list return *head;}// Driver Codeint main(){ /* Create the XOR Linked List head-->40<-->30<-->20<-->10 */ struct Node* head = NULL; insert(&head, 10); insert(&head, 20); insert(&head, 30); insert(&head, 40); delEnd(&head); // If the list had a single node if (head == NULL) cout << "List is empty"; else // Print the list after deletion printList(&head); return (0);}// This code is contributed by ajaymakvana |
C
// C program for 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){ // If XOR linked list is empty if (*head == NULL) { // 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 the XOR linked list // is not empty else { // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // 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; } 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; }}// Function to delete the last node// present in the XOR Linked Liststruct Node* delEnd(struct Node** head){ // Base condition if (*head == NULL) printf("List is empty"); else { // 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 (XOR(curr->nxp, prev) != NULL) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; } // If the Linked List contains more than 1 node if (prev != NULL) prev->nxp = XOR(XOR(prev->nxp, curr), NULL); // Otherwise else *head = NULL; // Delete the last node from memory free(curr); } // Returns head of new linked list return *head;}// Driver Codeint main(){ /* Create the XOR Linked List head-->40<-->30<-->20<-->10 */ struct Node* head = NULL; insert(&head, 10); insert(&head, 20); insert(&head, 30); insert(&head, 40); delEnd(&head); // If the list had a single node if (head == NULL) printf("List is empty"); else // Print the list after deletion printList(&head); return (0);} |
Python3
# Python implementation of the above approach. import ctypes# Structure of a node in XOR linked listclass Node: def __init__(self, value): self.value = value self.npx = 0# create linked list classclass XorLinkedList: # constructor def __init__(self): self.head = None self.tail = None self.__nodes = [] # Function to insert a node with given value at given position def insert(self, value): # Initialize a new Node node = Node(value) # Check If XOR linked list is empty if self.head is None: # Update pointer of head node self.head = node # Update pointer of tail node self.tail = node else: # Update curr node address self.head.npx = id(node) ^ self.head.npx # Update new node address node.npx = id(self.head) # Update head self.head = node # push node self.__nodes.append(node) # Function to print elements of the XOR Linked List def printList(self): if self.head != None: prev_id = 0 node = self.head next_id = 1 print(node.value, end=' ') # Traverse XOR linked list while next_id: # Forward traversal next_id = prev_id ^ node.npx if next_id: # Update prev prev_id = id(node) # Update curr node = self.__type_cast(next_id) # Print current node print(node.value, end=' ') else: return # method to check if the linked list is empty or not def isEmpty(self): if self.head is None: return True return False # method to return a new instance of type def __type_cast(self, id): return ctypes.cast(id, ctypes.py_object).value # Function to delete the last node present in the XOR Linked List def delEnd(self): # If list is empty if self.isEmpty(): return "List is empty !" # If list has 1 node elif self.head == self.tail: self.head = self.tail = None # If list has 2 nodes elif self.__type_cast(0 ^ self.head.npx) == (self.tail): self.tail = self.head self.head.npx = self.tail.npx = 0 # If list has more than 2 nodes else: # Stores XOR pointer of in previous Node prev_id = 0 # Stores XOR pointer in current node node = self.head # Stores XOR pointer of in next node next_id = 1 # Traverse XOR linked list while next_id: # Forward traversal next_id = prev_id ^ node.npx if next_id: # Update prev prev_id = id(node) # Update curr node = self.__type_cast(next_id) # update res, x, y, and tail. res = node.value x = self.__type_cast(prev_id).npx ^ id(node) y = self.__type_cast(prev_id) y.npx = x ^ 0 self.tail = y return res # Create following XOR Linked List# head-->40<-->30<-->20<-->10 head = XorLinkedList()head.insert(10)head.insert(20)head.insert(30)head.insert(40)# Delete the first nodehead.delEnd();# Print the following XOR Linked List# head-->30<-->20<-->10 if (head == None): print("List is empty")else: # Print the list after deletion head.printList();# This code is contributed by Nighi goel. |
Output:
40 30 20
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
