Click here to Skip to main content
14,364,319 members

ATL / WTL / STL

 
PinnedHOW TO ANSWER A QUESTION PinPopular
Chris Maunder16-Jul-09 4:09
adminChris Maunder16-Jul-09 4:09 
PinnedHow to get an answer to your question PinPopular
Chris Maunder16-Jul-09 4:05
adminChris Maunder16-Jul-09 4:05 
QuestionTo insert a node at the back of a XOR doubly linked list Pin
Tarun Jha17-Oct-19 10:38
memberTarun Jha17-Oct-19 10:38 
here is the method to insert a node at the front in the XORed doubly linked list or also known as memory efficient doubly linked list :
// To write a memory efficient linked list
#include <iostream>
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
};

// return XORed value of the node address
Node *XOR(Node *a, Node *b){
    return ((Node *)( (uintptr_t)(a) ^ (uintptr_t)(b) ));
}

// insert a node at the beggining 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 node is inserted at the beggining, npx of the new node will always be XOR of curent head and null
    new_node->npx = XOR((*head_ref), nullptr);

    // if the 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 != nullptr){
        // (*head_ref)->npx is XOR of null and next.
        // so if we do XOR of it with null, we get next
        Node *next = XOR((*head_ref)->npx, nullptr);
        (*head_ref)->npx = XOR(new_node, next);
    }

    // change head
    *head_ref = new_node;
}

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

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

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

        // get the address of next node : curr->npa 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 function
int main(){
    Node *head = nullptr;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
    insert(&head, 50);
    insert(&head, 60);

    printList(head);

    return 0;
}


Here is the code i have tried to put an element at the back of the list:
Node *insert(Node **last, int data){
    // allocate memory for new node
    Node *new_node = new Node();
    new_node->data = data;

	new_node->npx = XOR(*last, nullptr);

	if(*last != nullptr) {
		Node *prev = XOR((*last)->npx, nullptr);
		(*last)->npx = XOR(prev, new_node);
	}

	// *last = new_node;
	return (new_node);
}

// Driver function
int main(){
    Node *head = nullptr;
    head = insert(&head, 10);
    head = insert(&head, 20);
    head = insert(&head, 30);
    head = insert(&head, 40);
    head = insert(&head, 50);
    head = insert(&head, 60);

    printList(head);

    return 0;
}

But it is not working
output: it is same in both the cases

Thank you
QuestionWhy non-template function does not compile where as template function compiles? Pin
PBMBJoshi3-May-19 0:23
memberPBMBJoshi3-May-19 0:23 
AnswerRe: Why non-template function does not compile where as template function compiles? Pin
Richard MacCutchan3-May-19 0:29
protectorRichard MacCutchan3-May-19 0:29 
AnswerRe: Why non-template function does not compile where as template function compiles? Pin
k505410-Oct-19 9:53
memberk505410-Oct-19 9:53 
QuestionAdvice on interdependent asynchronous functions and task queuing? Pin
arnold_w8-Feb-19 0:07
memberarnold_w8-Feb-19 0:07 
AnswerRe: Advice on interdependent asynchronous functions and task queuing? Pin
arnold_w8-Feb-19 0:34
memberarnold_w8-Feb-19 0:34 
QuestionRecommended way to deal with queues and pointers to buffers Pin
arnold_w3-Feb-19 10:09
memberarnold_w3-Feb-19 10:09 
AnswerRe: Recommended way to deal with queues and pointers to buffers Pin
Richard MacCutchan3-Feb-19 23:19
protectorRichard MacCutchan3-Feb-19 23:19 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
arnold_w4-Feb-19 0:40
memberarnold_w4-Feb-19 0:40 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
Richard MacCutchan4-Feb-19 0:48
protectorRichard MacCutchan4-Feb-19 0:48 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
arnold_w4-Feb-19 4:15
memberarnold_w4-Feb-19 4:15 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
Richard MacCutchan4-Feb-19 4:46
protectorRichard MacCutchan4-Feb-19 4:46 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
arnold_w4-Feb-19 4:55
memberarnold_w4-Feb-19 4:55 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
Richard MacCutchan4-Feb-19 5:04
protectorRichard MacCutchan4-Feb-19 5:04 
GeneralRe: Recommended way to deal with queues and pointers to buffers Pin
Business2sell18-Feb-19 19:08
professionalBusiness2sell18-Feb-19 19:08 
QuestionCan a union in standard C "skip" members? Pin
arnold_w31-Jan-19 23:46
memberarnold_w31-Jan-19 23:46 
AnswerRe: Can a union in standard C "skip" members? Pin
Richard MacCutchan1-Feb-19 0:18
protectorRichard MacCutchan1-Feb-19 0:18 
GeneralRe: Can a union in standard C "skip" members? Pin
arnold_w1-Feb-19 0:47
memberarnold_w1-Feb-19 0:47 
GeneralRe: Can a union in standard C "skip" members? Pin
Richard MacCutchan1-Feb-19 0:52
protectorRichard MacCutchan1-Feb-19 0:52 
GeneralRe: Can a union in standard C "skip" members? Pin
arnold_w1-Feb-19 1:13
memberarnold_w1-Feb-19 1:13 
GeneralRe: Can a union in standard C "skip" members? Pin
Richard MacCutchan1-Feb-19 2:42
protectorRichard MacCutchan1-Feb-19 2:42 
GeneralRe: Can a union in standard C "skip" members? Pin
arnold_w1-Feb-19 3:08
memberarnold_w1-Feb-19 3:08 
GeneralRe: Can a union in standard C "skip" members? Pin
Richard MacCutchan1-Feb-19 3:57
protectorRichard MacCutchan1-Feb-19 3:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.