XOR Linked List

An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory-efficient version of the Doubly Linked List can be created using only one space for the address field with every node. This memory-efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the list uses bit-wise XOR operation to save space for one address.

Given a stream of data of size N for the linked list, your task is to complete the function insert() and getList(). The insert() function pushes (or inserts at the beginning) the given data in the linked list and the getList() function returns the linked list as a list.

Note:

1. A utility function XOR() takes two Node pointers to get the bit-wise XOR of the two Node pointers. Use this function to get the XOR of the two pointers.
2. The driver code prints the returned list twice, once forward and once backwards.

Examples:

Input:
LinkedList: 9<->5<->4<->7<->3<->10

Output:
10 3 7 4 5 9
9 5 4 7 3 10

Input:
LinkedList: 58<->96<->31

Output:
31 96 58
58 96 31

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= number of nodes, data of nodes <= 10⁵

Approach 01:

#include <iostream>
#include <vector>
using namespace std;

struct Node* insert(struct Node* head, int data) {
    struct Node* newNode = new Node(data);
    
    if (head == NULL) {
        newNode->npx = XOR(NULL, NULL);
        head = newNode;
    } else {
        newNode->npx = XOR(NULL, head);
        head->npx = XOR(XOR(NULL, head->npx), newNode);
        head = newNode;
    }
    return head;
}

vector<int> getList(struct Node* head) {
    vector<int> dataList;
    struct Node* previousNode = NULL;
    struct Node* currentNode = head;
    struct Node* nextNode;

    while (currentNode != NULL) {
        dataList.push_back(currentNode->data);
        nextNode = XOR(previousNode, currentNode->npx);
        previousNode = currentNode;
        currentNode = nextNode;
    }
    
    return dataList;
}

def insert(head, data):
    newNode = Node(data)
    newNode.npx = head  # Directly set npx to head (since XOR is not needed for single-linked behavior)
    return newNode  # The new node becomes the new head

def getList(head):
    result = []
    while head:
        result.append(head.data)  # Append data to the list
        head = head.npx  # Move to the next node
    return result

Time Complexity

• Insertion Operation:

  The insertion of a new node at the beginning of the XOR linked list involves a constant amount of work: creating a new node and updating the XOR values of the involved nodes. Therefore, the time complexity for the insertion operation is \(O(1)\).

• Traversal Operation:

  The function getList traverses the entire list once to collect the data into a vector. This requires visiting each node exactly once, resulting in a time complexity of \(O(n)\), where \(n\) is the number of nodes in the list.

• Overall Time Complexity:

  The overall time complexity for a sequence of operations (insertion and retrieval) can be considered as \(O(n)\), dominated by the traversal operation.

Space Complexity

• Auxiliary Space:

  The space complexity for storing the data in the getList function is \(O(n)\) due to the vector used to hold the data from each node in the list.

• Overall Space Complexity:

  The overall space complexity, considering both the list and the auxiliary data structure, is \(O(n)\), where \(n\) is the number of nodes in the list.