coderz.py

Problem Statement (Asked By Google)

An XOR-linked list is a memory-efficient version of a doubly linked list. Instead of each node storing separate next and prev pointers, each node contains a single field called both, which stores the result of the XOR operation on the memory addresses of the next and previous nodes.

Implement an XOR-linked list with the following methods:

1. add(element): Adds a new element to the end of the list.
2. get(index): Retrieves the node at the specified index.

If working in a language without native pointer manipulation (like Python), assume the availability of the following functions:

• get_pointer(node): Returns the memory address of the given node.
• dereference_pointer(address): Converts a memory address back to a node.

Write a program to implement the XOR linked list with the described functionalities.
Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

In an XOR linked list, each node stores the XOR of the addresses of its previous and next nodes. This makes the structure memory-efficient since we use only one pointer (both) instead of two (next and prev).

How It Works:

1. For the head node:
   • The both field contains the address of the next node, XORed with 0.
2. For the tail node:
   • The both field contains the address of the previous node.
3. For intermediate nodes:
   • The both field is the XOR of the addresses of the previous and next nodes.

Example:

Given a list like:
A <-> B <-> C <-> D

• A.both = B
• B.both = A ⊕ C
• C.both = B ⊕ D
• D.both = C

To traverse:

• Start at the head with prev = 0.
• XOR the current nodes both with prev to get the next node’s address.
• Repeat to traverse the list.

Java Implementation

Since Java does not allow direct memory manipulation like C or Python, we’ll simulate the XOR linked list using a Map to store node references.

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    int both; // XOR of prev and next node addresses

    public Node(int val) {
        this.val = val;
        this.both = 0;
    }
}

class XorLinkedList {
    private Node head;
    private Node tail;
    private final Map<Integer, Node> memory; // Simulate memory addresses

    public XorLinkedList() {
        this.head = null;
        this.tail = null;
        this.memory = new HashMap<>();
    }

    // Simulate getting a "memory address" for a node
    private int getAddress(Node node) {
        return node != null ? System.identityHashCode(node) : 0;
    }

    // Simulate dereferencing a "memory address"
    private Node dereference(int address) {
        return memory.get(address);
    }

    public void add(int val) {
        Node node = new Node(val);
        memory.put(getAddress(node), node);

        if (head == null) {
            head = tail = node;
        } else {
            node.both = getAddress(tail);
            tail.both ^= getAddress(node);
            tail = node;
        }
    }

    public Node get(int index) {
        if (head == null) {
            throw new IndexOutOfBoundsException("List is empty");
        }

        int prevAddress = 0;
        Node current = head;

        for (int i = 0; i < index; i++) {
            int nextAddress = prevAddress ^ current.both;
            if (nextAddress == 0) {
                throw new IndexOutOfBoundsException("Index out of range");
            }
            prevAddress = getAddress(current);
            current = dereference(nextAddress);
        }
        return current;
    }

    public static void main(String[] args) {
        XorLinkedList list = new XorLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.println("Node at index 0: " + list.get(0).val); // Output: 1
        System.out.println("Node at index 1: " + list.get(1).val); // Output: 2
        System.out.println("Node at index 2: " + list.get(2).val); // Output: 3
        System.out.println("Node at index 3: " + list.get(3).val); // Output: 4
    }
}

Explanation:

1. add Method:
   • For an empty list, initialize both head and tail with the new node.
   • Otherwise, update the current tail’s both to include the XOR of its previous value and the new node’s address.
   • Set the new node’s both to the current tail’s address and update the tail.
2. get Method:
   • Start from the head and traverse by calculating the next node’s address using the XOR of the current node’s both and the previous node’s address.
   • Stop when the index is reached or throw an exception if the index is out of bounds.

Time Complexity:

• add: O(1)
• get: O(N)

This implementation demonstrates how to simulate memory manipulation in Java using Map to store and retrieve node references by their simulated “addresses.”

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.