Open In App

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

Last Updated : 30 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

In the previous post, we discussed how a Doubly Linked can be created using only one space for the address field with every node. In this post, we will discuss the implementation of a memory-efficient doubly linked list. We will mainly discuss the following two simple functions.

  1. A function to insert a new node at the beginning.
  2. A function to traverse the list in a forwarding direction.
Recommended Practice
XOR Linked List
Try It!

In the following code, insert() function inserts a new node at the beginning. We need to change the head pointer of Linked List, that is why a double pointer is used (See this). Let us first discuss a few things again that have been discussed in the previous post. We store XOR of the next and previous nodes with every node and we call it npx, which is the only address member we have with every node. When we insert a new node at the beginning, npx of the new node will always be XOR of NULL and the current head. And npx of the current head must be changed to XOR of the new node and node next to the current head.
printList() traverses the list in a forwarding direction. It prints data values from every node. To traverse the list, we need to get a pointer to the next node at every point. We can get the address of next node by keeping track of the current node and previous node. If we do XOR of curr->npx and prev, we get the address of next node. 

Implementation:

C++ 
/* C++ Implementation of Memory 
efficient Doubly Linked List */
#include <bits/stdc++.h>
#include <cinttypes> 
using namespace std;

// Node structure of a memory 
// efficient doubly linked list 
class Node 
{ 
    public:
    int data; 
    Node* npx; /* XOR of next and previous node */
}; 

/* returns XORed value of the node addresses */
Node* XOR (Node *a, Node *b) 
{ 
    return reinterpret_cast<Node *>(
      reinterpret_cast<uintptr_t>(a) ^ 
      reinterpret_cast<uintptr_t>(b)); 
} 

/* Insert a node at the beginning of the 
XORed linked list and makes the newly 
inserted node as head */
void insert(Node **head_ref, int data) 
{ 
    // Allocate memory for new node 
    Node *new_node = new Node(); 
    new_node->data = data; 

    /* Since new node is being inserted at the 
    beginning, npx of new node will always be 
    XOR of current head and NULL */
    new_node->npx = *head_ref; 

    /* If linked list is not empty, then npx of 
    current head node will be XOR of new node 
    and node next to current head */
    if (*head_ref != NULL) 
    { 
        // *(head_ref)->npx is XOR of NULL and next. 
        // So if we do XOR of it with NULL, we get next 
        (*head_ref)->npx = XOR(new_node, (*head_ref)->npx); 
    } 

    // Change head 
    *head_ref = new_node; 
} 

// prints contents of doubly linked 
// list in forward direction 
void printList (Node *head) 
{ 
    Node *curr = head; 
    Node *prev = NULL; 
    Node *next; 

    cout << "Following are the nodes of Linked List: \n"; 

    while (curr != NULL) 
    { 
        // print current node 
        cout<<curr->data<<" "; 

        // get address of next node: curr->npx is 
        // next^prev, so curr->npx^prev will be 
        // next^prev^prev which is next 
        next = XOR (prev, curr->npx); 

        // update prev and curr for next iteration 
        prev = curr; 
        curr = next; 
    } 
} 

// Driver code 
int main () 
{ 
    /* Create following Doubly Linked List 
    head-->40<-->30<-->20<-->10 */
    Node *head = NULL; 
    insert(&head, 10); 
    insert(&head, 20); 
    insert(&head, 30); 
    insert(&head, 40); 

    // print the created list 
    printList (head); 

    return (0); 
} 

// This code is contributed by rathbhupendra
C 
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h> // Include stdint.h for uintptr_t

// Node structure of a memory-efficient doubly linked list
typedef struct Node {
    int data;
    struct Node* npx; // XOR of next and previous node
} Node;

// XOR function for C (casted pointer XOR)
Node* XOR(Node* a, Node* b) {
    return (Node*)((uintptr_t)a ^ (uintptr_t)b);
}

// Insert a node at the beginning of the XORed linked list
Node* insert(Node* head_ref, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->npx = head_ref;

    if (head_ref != NULL) {
        head_ref->npx = XOR(new_node, head_ref->npx);
    }

    return new_node; // Return new node as the updated head
}

// Print contents of doubly linked list in forward direction
void printList(Node* head) {
    Node* curr = head;
    Node* prev = NULL;
    Node* next;

    printf("Following are the nodes of Linked List:\n");

    while (curr != NULL) {
        // Print current node
        printf("%d ", curr->data);

        // Get address of next node: curr->npx is XOR of prev and next
        next = XOR(prev, curr->npx);

        // Update prev and curr for next iteration
        prev = curr;
        curr = next;
    }

    printf("\n");
}

// Driver code
int main() {
    /* Create following Doubly Linked List
       head-->40<-->30<-->20<-->10 */
    Node* head = NULL;
    head = insert(head, 10);
    head = insert(head, 20);
    head = insert(head, 30);
    head = insert(head, 40);

    // Print the created list
    printList(head);

    return 0;
}
Java 
// Node structure of a memory-efficient doubly linked list
class Node {
    int data;
    Node npx; // XORed value of the addresses of previous
              // and next nodes

    // Constructor
    public Node(int data)
    {
        this.data = data;
        this.npx = null;
    }
}

public class Main {
    // Returns XORed value of the node addresses
    static Node XOR(Node a, Node b)
    {
        // Converting node addresses to integers and
        // performing XOR operation
        return new Node(System.identityHashCode(a)
                        ^ System.identityHashCode(b));
    }

    // Insert a node at the beginning of the XORed linked
    // list and makes the newly inserted node as head
    static void insert(Node head_ref, int data)
    {
        // Allocate memory for new node
        Node new_node = new Node(data);

        // Since the new node is being inserted at the
        // beginning, npx of the new node will always be XOR
        // of current head and NULL
        new_node.npx = head_ref;

        // If linked list is not empty, then npx of current
        // head node will be XOR of new node and node next
        // to current head
        if (head_ref != null) {
            // head_ref.npx is XOR of NULL and next.
            // So if we do XOR of it with NULL, we get next
            new_node.npx = XOR(new_node, head_ref.npx);
        }

        // Change head
        head_ref = new_node;
    }

    // Prints contents of doubly linked list in forward
    // direction
    static void printList(Node head)
    {
        System.out.println(
            "Following are the nodes of Linked List: ");

        Node curr = head;
        Node prev = null;
        Node next;

        while (curr != null) {
            // Print current node
            System.out.println(curr.data);
            // Get address of next node: curr.npx is
            // next^prev, so curr.npx^prev will be
            // next^prev^prev which is next
            next = XOR(prev, curr.npx);

            // Update prev and curr for next iteration
            prev = curr;
            curr = next;
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        Node head = null;
        insert(head, 10);
        insert(head, 20);
        insert(head, 30);
        insert(head, 40);

        // Print the created list
        printList(head);
    }
}
Python3 
# Python3 implementation of Memory
# efficient Doubly Linked List

# library for providing C 
# compatible data types
import ctypes

# Node class for memory
# efficient doubly linked list
class Node:
    
    def __init__(self, data):
        
        self.data = data
        
        # XOR of next and previous node
        self.npx = 0  

class XorLinkedList:
    
    def __init__(self):
        
        self.head = None
        self.__nodes = []
        
    # Returns XORed value of the node addresses
    def XOR(self, a, b):
        
        return a ^ b
      
    # Insert a node at the beginning of the
    # XORed linked list and makes the newly
    # inserted node as head
    def insert(self, data):
        
        # New node
        node = Node(data)

        # Since new node is being inserted at 
        # the beginning, npx of new node will
        # always be XOR of current head and NULL
        node.npx = id(self.head)

        # If linked list is not empty, then
        # npx of current head node will be 
        # XOR of new node and node next to
        # current head
        if self.head is not None:
            
            # head.npx is XOR of None and next.
            # So if we do XOR of it with None, 
            # we get next
            self.head.npx = self.XOR(id(node), 
                                     self.head.npx)

        self.__nodes.append(node)
        
        # Change head
        self.head = node

    # Prints contents of doubly linked
    # list in forward direction
    def printList(self):
      
        if self.head != None:
            prev_id = 0
            curr = self.head
            next_id = 1
            
            print("Following are the nodes "
                  "of Linked List:")
            
            while curr is not None:
                
                # Print current node
                print(curr.data, end = ' ')
                
                # Get address of next node: curr.npx is
                # next^prev, so curr.npx^prev will be
                # next^prev^prev which is next
                next_id = self.XOR(prev_id, curr.npx)
                
                # Update prev and curr for next iteration
                prev_id = id(curr)
                curr = self.__type_cast(next_id)

    # Method to return a new instance of type
    # which points to the same memory block.
    def __type_cast(self, id):
        
        return ctypes.cast(id, ctypes.py_object).value

# Driver code
if __name__ == '__main__':
    
    obj = XorLinkedList()
    
    # Create following Doubly Linked List
    # head-->40<-->30<-->20<-->10
    obj.insert(10)
    obj.insert(20)
    obj.insert(30)
    obj.insert(40)

    # Print the created list
    obj.printList()

# This code is contributed by MuskanKalra1
C# 
using System;

// Node structure of a doubly linked list
class Node
{
    public int data;
    public Node prev;
    public Node next;
}

class Program
{
    // Insert a node at the beginning of the linked list
    static void Insert(ref Node head_ref, int data)
    {
        // Allocate memory for new node
        Node new_node = new Node();
        new_node.data = data;

        // Set the next of the new node as the current head
        new_node.next = head_ref;

        // If the current head is not null, set the previous of the head as the new node
        if (head_ref != null)
            head_ref.prev = new_node;

        // Set the new node as the head
        head_ref = new_node;
    }

    // Prints the contents of the linked list in forward direction
    static void PrintList(Node head)
    {
        Console.WriteLine("Following are the nodes of Linked List: ");

        while (head != null)
        {
            Console.Write(head.data + " ");
            head = head.next;
        }
    }

    // Driver code
    static void Main(string[] args)
    {
        /* Create following Doubly Linked List 
           head-->40<-->30<-->20<-->10 */
        Node head = null;
        Insert(ref head, 10);
        Insert(ref head, 20);
        Insert(ref head, 30);
        Insert(ref head, 40);

        // Print the created list
        PrintList(head);

        // This code is contributed by Shivam Tiwari
    }
}
Javascript 
class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Insert a node at the beginning of the linked list
function insert(head, data) {
    let new_node = new Node(data);

    if (head !== null) {
        new_node.next = head;
        head.prev = new_node;
    }

    return new_node; // Return the new node as the updated head
}

// Print contents of doubly linked list in forward direction
function printList(head) {
    let curr = head;
    let result = "Following are the nodes of Linked List:\n";

    while (curr !== null) {
        // Print current node
        result += curr.data + " ";
        curr = curr.next;
    }

    console.log(result);
}

// Driver code
let head = null;
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 30);
head = insert(head, 40);

printList(head);

Output
Following are the nodes of Linked List: 
40 30 20 10

Time Complexity: O(n), Where n is the total number of nodes in the given Doubly Linked List
Auxiliary Space: O(1)




https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Memory efficient doubly linked list
Next Article
Reverse a Doubly Linked List

Similar Reads

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, whi
15+ min read
Memory efficient doubly linked list
Asked by Varun Bhatia. Question: Write a code for implementation of doubly linked list with use of single pointer in each node. Solution: C/C++ Code #include &lt;iostream&gt; using namespace std; class Node { public: int data; Node* next; }; class CircularLinkedList { private: Node* head; public: CircularLinkedList() { head = nullptr; } void insert
6 min read
When is Doubly Linked List more Efficient than Singly Linked List?
Did you know there are some cases where a Doubly Linked List is more efficient than a Singly Linked List, even though it takes more memory compared to a Singly Linked List? What are those Cases? Well, we will discuss that in the following article, But first, let's talk about Singly and linked lists: What is a Singly Linked List?A singly linked list
4 min read
Why Linked List is implemented on Heap memory rather than Stack memory?
Pre-requisite: Linked List Data StructureStack vsHeap Memory Allocation The Linked List is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. It is implemented on the heap memory rather than the stack memory. This article discusses the reason behind
14 min read
Sort the given Matrix | Memory Efficient Approach
Given a matrix of N rows and M columns, the task is to sort the matrix in the strict order that is every row is sorted in increasing order and the first element of every row is greater than the first element of the previous row. Examples: Input: M[][] = { {5, 4, 7}, {1, 3, 8}, {2, 9, 6} } Output: 1 2 3 4 5 6 7 8 9 Explanation: Please refer above im
9 min read
How Data Structures can be used to achieve Efficient Memory Utilization
In the world of computer programming, using memory effectively is like fuelling a car efficiently. Similarly, in programming, memory is like the fuel that powers our software. Using memory wisely means making sure we don't waste it and use it for a purpose. To achieve efficient memory use, we use special tools called "data structures." These tools
12 min read
Count of subarrays in range [L, R] having XOR + 1 equal to XOR (XOR) 1 for M queries
Given an array, arr[] of N positive integers and M queries which consist of two integers [Li, Ri] where 1 ? Li ? Ri ? N. For each query, find the number of subarrays in range [Li, Ri] for which (X+1)=(X?1) where X denotes the xor of a subarray. Input: arr[]= {1, 2, 9, 8, 7}, queries[] = {{1, 5}, {3, 4}}Output: 6 1Explanation: Query 1: L=1, R=5: sub
12 min read
Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node. Introduction to Doubly linked list : A Doubly Linked List (D
2 min read
Is two way linked list and doubly linked list same?
Yes, a two-way linked list and a doubly linked list are the same. Both terms refer to a type of linked list where each node contains a reference to the next node as well as the previous node in the sequence. The term “two-way” emphasizes the ability to move in both directions through the list, while “doubly” highlights that there are two links per
3 min read
Reverse a singly Linked List in groups of given size | Set 4 (Space efficient approach)
Given a linked list, write a function to reverse every k node (where k is an input to the function). Examples: Inputs: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6-&gt;7-&gt;8-&gt;NULL, k = 3Output: 3-&gt;2-&gt;1-&gt;6-&gt;5-&gt;4-&gt;8-&gt;7-&gt;NULL Inputs: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6-&gt;7-&gt;8-&gt;NULL, k = 5Output: 5-&gt;4-&gt;3-&gt;2-&gt;1-&gt;8-&gt;
9 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox