XOR Linked List

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

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

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?