XOR Linked List

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Implement doubly linked list using XOR of prev and next pointers to save space.

Algorithm

1Each node stores XOR(prev, next). To traverse: next = XOR(prev, node.xorVal). Track previous pointer while traversing.

Common Pitfalls

•XOR trick: address(prev) XOR address(next) stored. Given prev, compute next = stored XOR prev. O(n) traversal.

XOR Linked List.java

Java

// Approach: Each node stores XOR of prev and next address. Traverse by XORing current address with known prev.
// Time: O(n) Space: O(n)
class Node {
    int data;
    Node npx;

    Node(int x) {
        data = x;
        npx = null;
    }
}

class Solution {
    // function should insert the data to the front of the list
    static Node insert(Node head, int data) {
        Node new_node = new Node(data);
        if (head == null) {
            head = new_node;
            return head;
        }
        new_node.npx = head;
        head = new_node;
        return head;
    }

    // function to print the linked list
    static ArrayList<Integer> getList(Node head) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.data);
            head = head.npx;
        }

        return list;
    }
}

Was this solution helpful?