Traversal in XOR linked list

Two types of traversal are possible in XOR linked list.

Forward Traversal
Backward Traversal:

Forward Traversal in XOR linked list:

When traversing the list forward, it’s important to always keep the memory address of the previous element. Address of previous element helps in calculating the address of the next element by the below formula:

address of next Node = (address of prev Node) ^ (both)

Here, “both” is the XOR of address of previous node and address of next node.

Forward Traversal of XOR Linked List

Below is the code snippet for forward traversal of the XOR linked list:

C++

Node* prev;
// Curr points to the first node
// of the XOR Linked list
Node* curr = head;
Node* next;
While(curr != NULL)
{
    cout << curr->data;
    // both represents the XOR value .
    next = prev ^ curr->both;
    prev = curr;
    curr = next;
}

Java

// Assuming Node is a class representing a node in the XOR
// Linked list with appropriate properties and methods.

Node prev = null;
// Curr points to the first node
// of the XOR Linked list
Node curr = head;
Node next;
while (curr != null) {
    System.out.print(curr.data);
    // both represents the XOR value .
    next = prev ^ curr.both;
    prev = curr;
    curr = next;
}

// This code is contributed by Susobhan Akhuli

Python

prev = None
# Curr points to the first node
# of the XOR Linked list
curr = head
while curr is not None:
  print(curr.data, end=" ")
  # "both" represents the XOR value.
  next_node = prev ^ curr.both
  prev = curr
  curr = next_node

JavaScript

let prev;
// Curr points to the first node
// of the XOR Linked list
let curr = head;
let next;
while (curr !== null)
{
    console.log(curr.data);
    // both represents the XOR value .
    next = prev ^ curr.both;
    prev = curr;
    curr = next;
}

// This code is contributed by Susobhan Akhuli

Backward Traversal in XOR linked list:

When traversing the list backward, it’s important to always keep the memory address of the next element. Address of next element helps in calculating the address of the previous element by the below formula:

address of previous Node = (address of next Node) ^ (both)

Here, “both” is the XOR of address of previous node and address of next node.

Backward Traversal of XOR Linked List

Below is the code snippet for backward traversal of the XOR linked list:

C++

// Curr points to the last node
//of the XOR Linked list
Node * curr ;
Node *head;
Node *prev, *next=NULL;
while(curr!=NULL)
{
  cout<<curr->data;
  //both represents the XOR value of the node.
  prev= (next) ^ (curr->both);
  next = curr;
  curr = prev;
}

Java

// Curr points to the last node
//of the XOR Linked list
Node curr;
Node head;
Node prev, next = null;

while (curr != null) {
  System.out.println(curr.data);
  //both represents the XOR value of the node.
  prev = (next) ^ (curr.both);
  next = curr;
  curr = prev;
}

Python

import ctypes

class Node:
    def __init__(self, data):
        self.data = data
        self.both = None

def XOR(a, b):
    return ctypes.cast(ctypes.pointer(ctypes.c_int(a)), ctypes.POINTER(ctypes.c_int)).value ^ \
           ctypes.cast(ctypes.pointer(ctypes.c_int(b)), ctypes.POINTER(ctypes.c_int)).value

def main():
    # Curr points to the last node
    curr = None
    head = None
    prev = next_node = None

    while curr is not None:
        print(curr.data),

        # both represents the XOR value of the node.
        prev = XOR(next_node, curr.both)
        next_node = curr
        curr = prev

if __name__ == "__main__":
    main()

using System;
using System.Runtime.InteropServices;

class Program
{
    // Node class definition
    class Node
    {
        public int data;
        public Node both;
    }

    static unsafe void Main()
    {
        // Curr points to the last node
        Node curr = null;
        Node head = null;
        Node prev, next = null;

        while (curr != null)
        {
            Console.Write(curr.data + " ");

            // both represents the XOR value of the node.
            prev = XOR(next, curr.both);
            next = curr;
            curr = prev;
        }
    }

    // Helper method for XOR operation
    static Node XOR(Node a, Node b)
    {
        return (Node)((IntPtr)a ^ (IntPtr)b);
    }
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.both = null;
    }
}

let curr;
let head;
let prev, next = null;

while (curr !== null) {
    console.log(curr.data);
    // both represents the XOR value of the node.
    prev = next ^ curr.both;
    next = curr;
    curr = prev;
}

XOR Linked List – A Memory Efficient Doubly Linked List | Set 1

In this post, we’re going to talk about how XOR linked lists are used to reduce the memory requirements of doubly-linked lists.

We know that each node in a doubly-linked list has two pointer fields which contain the addresses of the previous and next node. On the other hand, each node of the XOR linked list requires only a single pointer field, which doesn’t store the actual memory addresses but stores the bitwise XOR of addresses for its previous and next node.

XOR Linked List

Following are the Ordinary and XOR (or Memory Efficient) representations of the Doubly Linked List:

XOR Linked List Representation.

In this section, we will discuss both ways in order to demonstrate how XOR representation of doubly linked list differs from ordinary representation of doubly linked list.

Ordinary Representation
XOR List Representation

Ordinary Representation of doubly linked list.

Node A:
prev = NULL, next = add(B) // previous is NULL and next is address of B

Node B:
prev = add(A), next = add(C) // previous is address of A and next is address of C

Node C:
prev = add(B), next = add(D) // previous is address of B and next is address of D

Node D:
prev = add(C), next = NULL // previous is address of C and next is NULL

XOR List Representation of doubly linked list.

Lets see the structure of each node of Doubly linked list and XOR linked list:

Below is the representation of a node structure for an XOR linked list:

C++

struct Node {
    int data;

    // "both": XOR of the previous and next node addresses
    Node* both;
};

Java

class Node {
    int data;
    Node both; // XOR of the previous and next node addresses
}

Python

class Node:
    def __init__(self, data):
        self.data = data  # Data stored in the node
        self.prev = None  # Reference to the previous node
        self.next = None  # Reference to the next node

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # Reference to the first node
        self.tail = None  # Reference to the last node

    # Other methods of Doubly Linked List can be implemented here

JavaScript

class Node {
    constructor(data) {
        this.data = data; // Data stored in the node
        this.both = null; // XOR of the previous and next node addresses
    }
}

// In JavaScript, there's no native XOR operation on memory addresses like in C/C++
// You can simulate similar behavior using references or pointers to nodes
// However, JavaScript does not provide direct memory manipulation, so XOR operation on addresses is not feasible
// Instead, you can simply store references to the previous and next nodes directly
// For example:
class DoublyLinkedList {
    constructor() {
        this.head = null; // Reference to the first node
        this.tail = null; // Reference to the last node
    }

    // Other methods of Doubly Linked List can be implemented here
}

Tags:

#Bitwise-XOR #doubly linked list #Advanced Data Structure #DSA #Linked List #Advanced Data Structure #Linked List

Types of XOR Linked List:

Basic Operations of XOR Linked list:

Traversal in XOR linked list

Forward Traversal in XOR linked list:

Backward Traversal in XOR linked list:

XOR Linked List – A Memory Efficient Doubly Linked List | Set 1

Ordinary Representation of doubly linked list.

XOR List Representation of doubly linked list.

Similar Reads