Convert A Singly Linked List to An XOR Linked List

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

XOR Linked List

XOR linked list is the memory-efficient version of the doubly linked list, in which the next pointer of every node stores the XOR of the previous and next node’s address. A XOR linked list uses only one address space per node to store the address of the previous and next node, while a doubly linked list uses two address spaces per node to store the address of the previous and next list node (prev, next).

To learn more about XOR linked list, please visit this article Memory Efficient Doubly Linked List.

Problem Statement

In this problem, we are given a singly linked list and have to convert it to the XOR linked list.

Problem Statement Understanding

In this problem, we will be discussing how we can convert a singly linked list to XOR linked list. We will be provided with a singly linked list as the input, and our task will be to somehow convert this singly linked list to a XOR linked list.

Given singly linked list

Converted XOR linked list

An important XOR property:

  • If A XOR B = C, then A XOR C = B, as well as B XOR C = A.

Approach

In a XOR linked list, each pointer stores the XOR of prev and next node address, so the approach is:

  • First, we traverse the singly linked list and keep track of the previous node in a pointer.
  • While we are traversing the list, we will change the next pointer of every node as curr.next = XOR(prev, next).

Algorithm

1) Create three nodes:

  • A current node, initially pointing to the head.
  • A previous node, initially pointing to the null.
  • A next node, initially pointing to the current.next.
    2) Iterate while current is not null:
  • Update next to current.next.
  • Update current.next to XOR(prev, next).
  • Update previous to current.
  • Update current to next.

printingXOR()

  • In the PrintingXOR function, we will start with a node previous, which will point to NULL, and a node current, which will point to the head.
  • Now, we will print current.data.
  • For the traversal, we will now need the address of the next node. We can get that by calculating address(previous node) XOR address(current.next).
  • After getting the next node address, we will update our previous to current and current to the next node address.
  • This process will go on till we reach the end of the list.

Algorithm

1) Create a previous node, a current node, and a next node.
2) Make previous point to NULL and current to the head.
3) Iterate while current is not null:

  • Print current.data.
  • Store the address of the next node as address(previous) XOR address(current.next).
  • Update the previous to current and the current to the next node address.

Code Implementation

// Linked list node
class Node {
    int data;
    Node next;

    Node(int item) {
        data = item;
        next = null;
    }
}

public class PrepBytes {
    static Node root;

    // Printing singly linked list
    static void printing(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }

    static Node XOR(Node a, Node b) {
        return b;
    }

    // This function will convert singly linked list
    // to XOR linked list
    static void convertToXOR(Node head) {
        Node current = head;
        Node prev = null;
        Node next = current.next;

        while (current != null) {

            next = current.next;

            current.next = XOR(prev, next);

            prev = current;

            current = next;
        }
    }

    // This function will print the converted XOR linked list
    static void printingXOR(Node head) {
        Node curr = head;
        Node prev = null;
        Node next;
        
        while (curr != null) {

            // print current node
            System.out.print(curr.data + " ");

            next = XOR(prev, curr.next);
            prev = curr;
            curr = next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        PrepBytes prep = new PrepBytes();
        prep.root = new Node(53);
        prep.root.next = new Node(69);
        prep.root.next.next = new Node(96);
        prep.root.next.next.next = new Node(27);
        System.out.println("Singly Linked List Before Conversion: ");
        printing(root);
        convertToXOR(root);
        System.out.println("After Conversion to XOR Linked List: ");
        printingXOR(root);
    }
}

Output

Singly Linked List Before Conversion:
53 69 96 27
After Conversion to XOR Linked List:
53 69 96 27

Time Complexity: O(n), as we are only traversing the list.

So, in this article, we have tried to explain the most effective way to convert singly linked list to XOR linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *