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 traverse the list in a forwarding direction.
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++
#include <bits/stdc++.h>
#include <cinttypes>
using namespace std;
class Node
{
public :
int data;
Node* npx;
};
Node* XOR (Node *a, Node *b)
{
return reinterpret_cast <Node *>(
reinterpret_cast < uintptr_t >(a) ^
reinterpret_cast < uintptr_t >(b));
}
void insert(Node **head_ref, int data)
{
Node *new_node = new Node();
new_node->data = data;
new_node->npx = *head_ref;
if (*head_ref != NULL)
{
(*head_ref)->npx = XOR(new_node, (*head_ref)->npx);
}
*head_ref = new_node;
}
void printList (Node *head)
{
Node *curr = head;
Node *prev = NULL;
Node *next;
cout << "Following are the nodes of Linked List: \n" ;
while (curr != NULL)
{
cout<<curr->data<< " " ;
next = XOR (prev, curr->npx);
prev = curr;
curr = next;
}
}
int main ()
{
Node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
printList (head);
return (0);
}
|
Java
import java.util.*;
class Node {
public int data;
public Node npx;
}
public class Main {
public static Node XOR (Node a, Node b) {
return (Node) (a ^ b);
}
public static void insert(Node[] head_ref, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.npx = head_ref[ 0 ];
if (head_ref[ 0 ] != null ) {
head_ref[ 0 ].npx = XOR(new_node, head_ref[ 0 ].npx);
}
head_ref[ 0 ] = new_node;
}
public static void printList (Node head) {
Node curr = head;
Node prev = null ;
Node next;
System.out.println( "Following are the nodes of Linked List: " );
while (curr != null ) {
System.out.print(curr.data + " " );
next = XOR(prev, curr.npx);
prev = curr;
curr = next;
}
}
public static void main (String[] args) {
Node[] head = new Node[ 1 ];
insert(head, 10 );
insert(head, 20 );
insert(head, 30 );
insert(head, 40 );
printList(head[ 0 ]);
}
}
|
Python3
import ctypes
class Node:
def __init__( self , data):
self .data = data
self .npx = 0
class XorLinkedList:
def __init__( self ):
self .head = None
self .__nodes = []
def XOR( self , a, b):
return a ^ b
def insert( self , data):
node = Node(data)
node.npx = id ( self .head)
if self .head is not None :
self .head.npx = self .XOR( id (node),
self .head.npx)
self .__nodes.append(node)
self .head = node
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 (curr.data, end = ' ' )
next_id = self .XOR(prev_id, curr.npx)
prev_id = id (curr)
curr = self .__type_cast(next_id)
def __type_cast( self , id ):
return ctypes.cast( id , ctypes.py_object).value
if __name__ = = '__main__' :
obj = XorLinkedList()
obj.insert( 10 )
obj.insert( 20 )
obj.insert( 30 )
obj.insert( 40 )
obj.printList()
|
C#
using System;
class Node
{
public int data;
public Node prev;
public Node next;
}
class Program
{
static void Insert( ref Node head_ref, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = head_ref;
if (head_ref != null )
head_ref.prev = new_node;
head_ref = new_node;
}
static void PrintList(Node head)
{
Console.WriteLine( "Following are the nodes of Linked List: " );
while (head != null )
{
Console.Write(head.data + " " );
head = head.next;
}
}
static void Main( string [] args)
{
Node head = null ;
Insert( ref head, 10);
Insert( ref head, 20);
Insert( ref head, 30);
Insert( ref head, 40);
PrintList(head);
}
}
|
Javascript
class Node {
constructor(data, npx) {
this .data = data;
this .npx = npx;
}
}
function XOR(a, b) {
return (a ^ b);
}
function insert(head_ref, data) {
let new_node = new Node(data, null );
new_node.npx = head_ref;
if (head_ref != null ) {
head_ref.npx = XOR(new_node, head_ref.npx);
}
head_ref = new_node;
}
function printList(head) {
let curr = head;
let prev = null ;
let next;
console.log( "Following are the nodes of Linked List: " );
while (curr != null ) {
console.log(curr.data);
next = XOR(prev, curr.npx);
prev = curr;
curr = next;
}
}
let head = null ;
insert(head, 10);
insert(head, 20);
insert(head, 30);
insert(head, 40);
printList(head);
|
C
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
struct Node
{
int data;
struct Node* npx;
};
struct Node* XOR ( struct Node *a, struct Node *b)
{
return ( struct Node*) (( uintptr_t ) (a) ^ ( uintptr_t ) (b));
}
void insert( struct Node **head_ref, int data)
{
struct Node *new_node = ( struct Node *) malloc ( sizeof ( struct Node) );
new_node->data = data;
new_node->npx = *head_ref;
if (*head_ref != NULL)
{
(*head_ref)->npx = XOR(new_node, (*head_ref)->npx);
}
*head_ref = new_node;
}
void printList ( struct Node *head)
{
struct Node *curr = head;
struct Node *prev = NULL;
struct Node *next;
printf ( "Following are the nodes of Linked List: \n" );
while (curr != NULL)
{
printf ( "%d " , curr->data);
next = XOR (prev, curr->npx);
prev = curr;
curr = next;
}
}
int main ()
{
struct Node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
printList (head);
return (0);
}
|
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)
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!