Open In App

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

Last Updated : 06 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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-Banner

XOR Linked List

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

file

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.

  1. Ordinary Representation
  2. XOR List Representation

file

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:

file

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
}

Types of XOR Linked List:

There are two main types of XOR Linked List:

  1. Singly Linked XOR List: A singly XOR linked list is a variation of the XOR linked list that uses the XOR operation to store the memory address of the next node in a singly linked list. In this type of list, each node stores the XOR of the memory address of the next node and the memory address of the current node.
  2. Doubly Linked XOR List: A doubly XOR linked list is a variation of the XOR linked list that uses the XOR operation to store the memory addresses of the next and previous nodes in a doubly linked list. In this type of list, each node stores the XOR of the memory addresses of the next and previous nodes.

Traversal in XOR linked list:

Two types of traversal are possible in XOR linked list.

  1. Forward Traversal
  2. 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.

traversing-XOR-forward-(1)

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.

traversing-XOR-backward-(1)

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()
C#
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;
}

Basic Operations of XOR Linked list:

  • Insertion
  • Deletion

Insertion at Beginning in XOR Linked List:

Below is the steps for insert an element at beginning in XOR Linked List:

  • Create a new node , initialize the data and address to the (NULL ^ address of head)
  • Then check, If the list is empty, return with that node;
  • Otherwise, assign the XOR of the head node to the XOR(new_node address, XOR(head->both, nullptr))

Insertion at end in XOR Linked List:

Below is the steps for insert an element at end in XOR Linked List:

  • Create a new node , initialize the data and address to the (NULL ^ add. of tail)
  • Then check, If the list is empty, return with that node;
  • Otherwise, assign the XOR of the tail node to the XOR(XOR(tail->both, nullptr), new_node address)

Deletion at Beginning in XOR Linked List:

Below is the steps for delete an element at beginning in XOR Linked List:

  • Check if the head pointer is not null (i.e., the list is not empty).
  • Find the next node’s address using XOR by performing XOR(head->both, nullptr)
  • Delete the current head node to free up the memory.and Update the head pointer to point to the calculated next node.

Deletion at End in XOR Linked List:

Below is the steps for delete an element at beginning in XOR Linked List:

  • Check if the tail pointer is not null (i.e., the list is not empty).
  • If the list is not empty:
    • Find the previous node’s address using XOR by performing XOR(tail->both, nullptr). This gives you the previous node in the list.
    • Delete the current tail node to free up the memory.
    • Update the tail pointer to point to the calculated previous node.

Below is the implementation of the above approach:

C++
// for uintptr_t
#include <cstdint>
#include <iostream>

struct Node {
    int data;
    // XOR of next and prev
    Node* both;
};

class XORLinkedList {
private:
    Node* head;
    Node* tail;
    // XOR function for Node pointers
    Node* XOR(Node* a, Node* b);

public:
    // Constructor to initialize an empty
    // list
    XORLinkedList();
  
    // Insert a node at the head of the list
    void insert_at_head(int data);
  
    // Insert a node at the tail of the list
    void insert_at_tail(int data);
  
    // Delete a node from the head
    // of the list
    void delete_from_head();
  
    // Delete a node from the tail
    // of the list
    void delete_from_tail();
  
    // Print the elements of the list
    void print_list();
};

XORLinkedList::XORLinkedList()
{
    head = tail = nullptr; // Initialize head and tail to
                           // nullptr for an empty list
}

Node* XORLinkedList::XOR(Node* a, Node* b)
{
    return (
      
        // XOR operation for Node pointers
        Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}

void XORLinkedList::insert_at_head(int data)
{
    Node* new_node = new Node();
    new_node->data = data;
    new_node->both = XOR(nullptr, head);

    if (head) {
        head->both
            = XOR(new_node, XOR(head->both, nullptr));
    }
    else {
        // If the list was empty, the new
        // node is both the head and the
        // tail
        tail = new_node;
    }
    // Update the head to the new node
    head = new_node;
}

void XORLinkedList::insert_at_tail(int data)
{
    Node* new_node = new Node();
    new_node->data = data;
    new_node->both = XOR(tail, nullptr);

    if (tail) {
        tail->both
            = XOR(XOR(tail->both, nullptr), new_node);
    }
    else {
        // If the list was empty, the new
        // node is both the head and the
        // tail
        head = new_node;
    }
    // Update the tail to the new node
    tail = new_node;
}

void XORLinkedList::delete_from_head()
{
    if (head) {
        Node* next = XOR(head->both, nullptr);
        delete head;
        head = next;

        if (next) {
            next->both = XOR(next->both, head);
        }
        else {
            // If the list becomes empty,
            // update the tail to nullptr
            tail = nullptr;
        }
    }
}

void XORLinkedList::delete_from_tail()
{
    if (tail) {
        Node* prev = XOR(tail->both, nullptr);
        delete tail;
        tail = prev;

        if (prev) {
            prev->both = XOR(prev->both, tail);
        }
        else {
            // If the list becomes empty, update the head to
            // nullptr
            head = nullptr;
        }
    }
}

void XORLinkedList::print_list()
{
    Node* current = head;
    Node* prev = nullptr;
    while (current) {
        std::cout << current->data << " ";
        Node* next = XOR(prev, current->both);
        prev = current;
        current = next;
    }
    std::cout << std::endl;
}

int main()
{
    XORLinkedList list;
    list.insert_at_head(10);
    list.insert_at_head(20);
    list.insert_at_tail(30);
    list.insert_at_tail(40);
    // prints 20 10 30 40
    list.print_list();
    list.delete_from_head();
    // prints 10 30 40
    list.print_list();
    list.delete_from_tail();
    // prints 10 30
    list.print_list();
    return 0;
}
Java
import java.util.HashMap;

class Node {
    int data;
    int both; // This will hold the XOR of the next and previous node IDs

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

class XORLinkedList {
    private Node head;
    private Node tail;
    // HashMap to store Node objects by their IDs. This is necessary because Java doesn't
    // provide direct access to objects based on memory location.
    private HashMap<Integer, Node> nodes;

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

    private int _xor(int a, int b) {
        // Helper function to get the XOR of two IDs
        return a ^ b;
    }

    public void insertAtHead(int data) {
        // Inserts a new node with the provided data at the head of the list
        Node newNode = new Node(data);
        int newId = System.identityHashCode(newNode);
        nodes.put(newId, newNode);

        if (head != null) {
            // Adjusting both values for the new node and existing head
            newNode.both = _xor(0, System.identityHashCode(head));
            head.both = _xor(newNode.both, System.identityHashCode(head));
        } else {
            // If the list is empty, the new node becomes the tail
            tail = newNode;
        }
        head = newNode;
    }

    public void insertAtTail(int data) {
        // Inserts a new node with the provided data at the tail of the list
        Node newNode = new Node(data);
        int newId = System.identityHashCode(newNode);
        nodes.put(newId, newNode);

        if (tail != null) {
            // Adjusting both values for the new node and existing tail
            newNode.both = _xor(System.identityHashCode(tail), 0);
            tail.both = _xor(newNode.both, System.identityHashCode(tail));
        } else {
            // If the list is empty, the new node becomes the head
            head = newNode;
        }
        tail = newNode;
    }

    public void deleteFromHead() {
        // Deletes the head node from the list
        if (head != null) {
            // If there's a next node after the head, update its both value
            int nextNodeId = _xor(0, head.both);
            Node nextNode = nodes.getOrDefault(nextNodeId, null);

            if (nextNode != null) {
                nextNode.both = _xor(System.identityHashCode(head), nextNode.both);
            } else {
                tail = null;
            }

            // Remove the current head from the nodes HashMap and update the head pointer
            nodes.remove(System.identityHashCode(head));
            head = nextNode;
        }
    }

    public void deleteFromTail() {
        // Deletes the tail node from the list
        if (tail != null) {
            // If there's a previous node before the tail, update its both value
            int prevNodeId = _xor(tail.both, 0);
            Node prevNode = nodes.getOrDefault(prevNodeId, null);

            if (prevNode != null) {
                prevNode.both = _xor(System.identityHashCode(tail), prevNode.both);
            } else {
                head = null;
            }

            // Remove the current tail from the nodes HashMap and update the tail pointer
            nodes.remove(System.identityHashCode(tail));
            tail = prevNode;
        }
    }

    public void printList() {
        // Prints the entire list from head to tail
        Node current = head;
        int prevId = 0;
        while (current != null) {
            System.out.print(current.data + " ");
            // Compute the ID of the next node
            int nextId = _xor(prevId, current.both);

            // Move the pointers
            prevId = System.identityHashCode(current);
            current = nodes.getOrDefault(nextId, null);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        XORLinkedList list = new XORLinkedList();
        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtTail(30);
        list.insertAtTail(40);
        list.printList(); // Expected: 20 10 30 40
        list.deleteFromHead();
        list.printList(); // Expected: 10 30 40
        list.deleteFromTail();
        list.printList(); // Expected: 10 30
    }
}
Python
class Node:
    def __init__(self, data):
        self.data = data
        self.both = 0  # This will hold the XOR of the next and previous node IDs

class XORLinkedList:
    def __init__(self):
        self.head = self.tail = None
        # Dictionary to store Node objects by their IDs. This is necessary because Python doesn't
        # provide direct access to objects based on memory location.
        self.nodes = {}  

    def _xor(self, a, b):
        """Helper function to get the XOR of two IDs."""
        return a ^ b

    def insert_at_head(self, data):
        """Inserts a new node with the provided data at the head of the list."""
        new_node = Node(data)
        new_id = id(new_node)
        self.nodes[new_id] = new_node
        
        if self.head:
            # Adjusting both values for new node and existing head
            new_node.both = self._xor(0, id(self.head))
            self.head.both = self._xor(new_node.both, id(self.head))
        else:
            # If list is empty, the new node becomes the tail
            self.tail = new_node
        self.head = new_node

    def insert_at_tail(self, data):
        """Inserts a new node with the provided data at the tail of the list."""
        new_node = Node(data)
        new_id = id(new_node)
        self.nodes[new_id] = new_node
        
        if self.tail:
            # Adjusting both values for new node and existing tail
            new_node.both = self._xor(id(self.tail), 0)
            self.tail.both = self._xor(new_node.both, id(self.tail))
        else:
            # If list is empty, the new node becomes the head
            self.head = new_node
        self.tail = new_node

    def delete_from_head(self):
        """Deletes the head node from the list."""
        if self.head:
            # If there's a next node after the head, update its both value
            next_node_id = self._xor(0, self.head.both)
            next_node = self.nodes.get(next_node_id) if next_node_id else None
            
            if next_node:
                next_node.both = self._xor(id(self.head), next_node.both)
            else:
                self.tail = None
            
            # Remove the current head from the nodes dictionary and update the head pointer
            del self.nodes[id(self.head)]
            self.head = next_node

    def delete_from_tail(self):
        """Deletes the tail node from the list."""
        if self.tail:
            # If there's a previous node before the tail, update its both value
            prev_node_id = self._xor(self.tail.both, 0)
            prev_node = self.nodes.get(prev_node_id) if prev_node_id else None
            
            if prev_node:
                prev_node.both = self._xor(id(self.tail), prev_node.both)
            else:
                self.head = None
            
            # Remove the current tail from the nodes dictionary and update the tail pointer
            del self.nodes[id(self.tail)]
            self.tail = prev_node

    def print_list(self):
        """Prints the entire list from head to tail."""
        current = self.head
        prev_id = 0
        while current:
            print(current.data, end=" ")
            # Compute the ID of the next node
            next_id = self._xor(prev_id, current.both)
            
            # Move the pointers
            prev_id = id(current)
            current = self.nodes.get(next_id)
        print()

if __name__ == '__main__':
    list_ = XORLinkedList()
    list_.insert_at_head(10)
    list_.insert_at_head(20)
    list_.insert_at_tail(30)
    list_.insert_at_tail(40)
    list_.print_list()  # Expected: 20 10 30 40
    list_.delete_from_head()
    list_.print_list()  # Expected: 10 30 40
    list_.delete_from_tail()
    list_.print_list()  # Expected: 10 30
C#
using System;
using System.Collections.Generic;

class Node {
    public int Data;
    public IntPtr Both; // XOR of next and previous node IDs
    public int Id; // Unique ID for the node

    public Node(int data, int id)
    {
        Data = data;
        Both = IntPtr.Zero;
        Id = id;
    }
}

class XORLinkedList {
    private Node head;
    private Node tail;
    private Dictionary<int, Node> nodes
        = new Dictionary<int, Node>();
    private int counter
        = 0; // Counter to simulate unique IDs

    // Helper function to get the XOR of two IDs
    private IntPtr XOR(IntPtr a, IntPtr b)
    {
        return (IntPtr)((ulong)a ^ (ulong)b);
    }

    // Get the next unique ID
    private int GetNextId() { return ++counter; }

    // Insert a node with the provided data at the specified
    // position
    public void Insert(int data, bool atBeginning = false)
    {
        int newNodeId = GetNextId();
        Node newNode = new Node(data, newNodeId);
        nodes[newNodeId] = newNode;

        if (head != null && !atBeginning) {
            newNode.Both
                = XOR((IntPtr)tail.Id, IntPtr.Zero);
            tail.Both
                = XOR(XOR((IntPtr)tail.Both, IntPtr.Zero),
                      (IntPtr)newNodeId);
        }
        else {
            newNode.Both = XOR(
                IntPtr.Zero, head != null ? (IntPtr)head.Id
                                          : IntPtr.Zero);

            if (head != null) {
                head.Both = XOR(
                    (IntPtr)newNodeId,
                    XOR((IntPtr)head.Both, IntPtr.Zero));
            }
            else {
                tail = newNode;
            }

            head = newNode;
        }
    }

    // Delete a node from the specified position
    public void Delete(bool fromBeginning = true)
    {
        if (head != null) {
            int idToDelete
                = fromBeginning ? head.Id : tail.Id;
            int nextNodeId = (int)XOR(
                IntPtr.Zero,
                fromBeginning ? head.Both : tail.Both);
            Node nextNode = nodes.ContainsKey(nextNodeId)
                                ? nodes[nextNodeId]
                                : null;

            if (nextNode != null) {
                nextNode.Both = XOR(nextNode.Both,
                                    (IntPtr)idToDelete);
            }
            else {
                tail = null;
            }

            nodes.Remove(idToDelete);

            if (fromBeginning) {
                head = nextNode;
            }
            else {
                tail = nextNode;
            }
        }
    }

    // Print the elements of the list
    public void PrintList()
    {
        Node current = head;

        while (current != null) {
            Console.Write(current.Data + " ");
            int nextId
                = (int)XOR(IntPtr.Zero, current.Both);
            current = nodes.ContainsKey(nextId)
                          ? nodes[nextId]
                          : null;
        }

        Console.WriteLine();
    }
}

class Program {
    static void Main()
    {
        XORLinkedList list = new XORLinkedList();
        list.Insert(10);
        list.Insert(20, true);
        list.Insert(30);
        list.Insert(40);

        // prints 20 10 30 40
        list.PrintList();

        list.Delete(true);
        // prints 10 30 40
        list.PrintList();

        list.Delete(false);
        // prints 10 30
        list.PrintList();
    }
}
JavaScript
class Node {
  constructor(data, id) {
    this.data = data;
    this.both = 0; // XOR of next and previous node IDs
    this.id = id;  // Unique ID for the node
  }
}

class XORLinkedList {
  constructor() {
    this.head = this.tail = null;
    this.nodes = new Map();
    this.counter = 0; // Counter to simulate unique IDs
  }

  _xor(a, b) {
    return a ^ b;
  }

  getNextId() {
    return ++this.counter;
  }

  insert(data, atBeginning = false) {
    const newNodeId = this.getNextId();
    const newNode = new Node(data, newNodeId);
    this.nodes.set(newNodeId, newNode);

    if (this.head && !atBeginning) {
      newNode.both = this._xor(this.tail.id, 0);
      this.tail.both = this._xor(this._xor(this.tail.both, 0), newNodeId);
    } else {
      newNode.both = this._xor(0, this.head ? this.head.id : 0);
      if (this.head) {
        this.head.both = this._xor(newNodeId, this._xor(this.head.both, 0));
      } else {
        this.tail = newNode;
      }
      this.head = newNode;
    }
  }

  delete(fromBeginning = true) {
    if (this.head) {
      const idToDelete = fromBeginning ? this.head.id : this.tail.id;
      const nextNodeId = this._xor(0, fromBeginning ? this.head.both : this.tail.both);
      const nextNode = this.nodes.get(nextNodeId) || null;

      if (nextNode) {
        nextNode.both = this._xor(nextNode.both, idToDelete);
      } else {
        this.tail = null;
      }

      this.nodes.delete(idToDelete);
      if (fromBeginning) {
        this.head = nextNode;
      } else {
        this.tail = nextNode;
      }
    }
  }

  printList() {
    let current = this.head;

    while (current) {
      process.stdout.write(current.data + " ");
      const nextId = this._xor(0, current.both);
      current = this.nodes.get(nextId) || null;
    }

    process.stdout.write('\n');
  }
}

// Example usage
const list = new XORLinkedList();
list.insert(10);
list.insert(20, true);
list.insert(30);
list.insert(40);

list.printList();
list.delete(true);
list.printList();
list.delete(false);
list.printList();

Output
20 10 30 40 
10 0 10 
10 0 10 

Time Complexity: O(n)
Auxiliary Space: O(1)

Advantages and Disadvantages Of XOR Linked List:

Advantages:

  • XOR linked lists use less memory compared to traditional doubly linked lists. This is because they only need one “pointer” (the XOR of the previous and next pointers) instead of two separate pointers, which can save memory in applications where memory is a critical resource.
  • XOR linked lists can be traversed in both directions (forward and backward) without the need for an additional pointer to the previous node.
  • Insertion and deletion at both the head and tail of the list can be done in constant time (O(1)), just like in traditional singly linked lists. This makes them efficient for certain operations.

Disadvantages:

  • XOR linked lists are more complex to implement and maintain than traditional linked lists.
  • XOR linked lists are not a standard data structure in most programming languages and libraries.


Previous Article
Next Article

Similar Reads

XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
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. A function to insert a new node at the beginning.A function to travers
10 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