Doubly linked list SWAP HELP!

[alex067]

I am having an issue calling my swap function.

My swap function looks as such:

void Double :: swap(Dnode *x, Dnode *y)

An error is occurred where it says "Incomplete type not allowed"

 void Double::Toswap(int x)
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	int size = x;
	bool ToSwitch = false;
	bool Switch = false;
	Dnode *current = head;
	Dnode *temp;
	temp = NULL;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current->next != NULL) && (Switch = false))
	{
		if ((counter == pos1) && (ToSwitch = false))
		{
			Dnode *first = new Dnode;
			first = current;
			first->next = current;
			first->prev = NULL;
			ToSwitch = true;
		}
		if ((counter == pos2) && (Switch = false))
		{
			Dnode *second = new Dnode;
			second = current;
			Switch = true;
		}
		current = current->next;
		counter++;
	}

	void swap(first, second);
}

[alex067]

need urgent help

[alex067]

bump

[Bdanielz]

It sounds like you need to overload your () operator and implement a swap.
and because you are working with pointers you will at least need to follow to rule of three.

http://en.wikipedia.org/wiki/Rule_of_three_%28C%2B%2B_programming%29

If you intend to get help with your actual code, I would strongly suggest posting the code you are working with and talk about what is confusing you.

[alex067]

I am having an issue calling my swap function.

My swap function looks as such:

void Double :: swap(Dnode *x, Dnode *y)

An error is occurred where it says "Incomplete type not allowed"

 void Double::Toswap(int x)
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	int size = x;
	bool ToSwitch = false;
	bool Switch = false;
	Dnode *current = head;
	Dnode *temp;
	temp = NULL;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current->next != NULL) && (Switch = false))
	{
		if ((counter == pos1) && (ToSwitch = false))
		{
			Dnode *first = new Dnode;
			first = current;
			first->next = current;
			first->prev = NULL;
			ToSwitch = true;
		}
		if ((counter == pos2) && (Switch = false))
		{
			Dnode *second = new Dnode;
			second = current;
			Switch = true;
		}
		current = current->next;
		counter++;
	}

	void swap(first, second);
}

[alex067]

help please

[D80DSL3A]

I'm going to guess that no one is responding because your code is such a wreck. Sorry!
Let me list several immediately obvious problems. Maybe that will give you something to move forward with.
1) The variable x passed to the function is never used, except to initialize another variable size, which is also never used. So x is pointless.
2) The code from lines 17-32 will never execute. The Switch = false in line 15 makes the whole condition false. Use == not = here. Same for line17.
3) You allocate new nodes on lines 19 and 27. This is a swap function. New nodes are created only when making a list longer. New node allocation doesn't belong in this function.
4) first and second are local to the if statement bodies where they're declared. They are both out of scope at line 35.

Pretty much the whole function needs to be reworked.

What is this function supposed to be doing? Is it supposed to find which node has the value x stored in it, then swap that node with the next node?
We could probably help with that, but please reply with a clear description of the Toswap functions purpose.

[alex067]

Thank you so much for the input! It has helped me clear some major logical errors.

Ok so the purpose of the function is to obtain 2 node positions of 1 and 3, and swap them by re-linking/de-linking the position of the nodes, rather than swapping the data themselves.

The function is illustrated to go through a loop and increment a counter, if the counter first equals any one of the 2 positions to swap, it will enter an if statement which is designed to transfer the data of the current node (traversing node, the counter is designed to keep a numerical position of the traversing node) to another node called First. Then, the if statement flags the bool ToSwitch to true, which acts as a safety net to not go into this if statement again, since we got what we came for. The same principle is found for obtaining the second node.

Then, the void swap(Dnode *x, Dnode *y) is a function which will take those 2 found positions of the node and do the swapping.

My current code:

void Double::Toswap()
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	bool ToSwitch = false;
	bool Switch = false;
	bool found1;
	bool found2;
	Dnode *current = head; 
	Dnode *first = new Dnode;
	Dnode *second = new Dnode;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current->next != NULL) && (Switch == false))
	{
		if ((counter == pos1) && (ToSwitch == false))
		{
			first = current;
			first->next = current;
			first->prev = NULL;
			ToSwitch = true;
			found1 = true;
		}
		if ((counter == pos2) && (Switch == false))
		{
			second = current;
			Switch = true;
			found2 = true;
		}
		if (found2 == true && found1 == true) //if we found both positions
		{
			void swap(first, second);
		}
		current = current->next;
		counter++;
		
	}

	
}

[D80DSL3A]

Ok. The purpose of the function seems clear enough. Does it work now?
I'd recommend to separate testing of Toswap() from testing swap().
ie. don't call swap yet. Instead, just display the data held by first and second so you can see that the correct nodes have been found and saved to them.

You should call swap after the while loop exits.
Like so:

while(....)
{
    // first and second are found. The while is terminated.
}

// swap(first, second);// hold off on testing this
cout << first->value << ' ' << second->value;// examine values to verify the Toswap function is finding the correct nodes. 

Questions:
1) Why loop while current->next ? Do you want to avoid the last node for some reason?
If not, loop while( current ).

2) I think the bool values aren't needed. The pointers themselves can be tested instead.
You really don't need to be allocating new nodes!!
If you make lines 12,13 this instead:

Dnode *first = NULL;
Dnode *second = NULL;

then you can use first and second as the bool values!

Dnode *current = head;
Dnode *first = NULL;
Dnode *second = NULL;

while( current && !(first && second) )// loop will end when both pointers have been assigned
{
     if(counter == pos1) first = current;
     if(counter == pos2) second = current;
     current = current->next;
     counter++;
}

Lines like 20 and 21 in your code actually wreck the list! You've assigned current->next = current. None of that is needed. The swap function will make all needed changes to other pointer assignments.

See if all this helps.

[alex067]

Thank you once again for the input. The program gave me the correct value of the right nodes, so the first and second obtained the right node.

Now, when I want to call my swap function to actually swap, the major issue lies there.
A host of errors on the code of line which says:
void swap(first, second);

too many initializers
swap: illegal use of type void
initializing cannot convert Dnode to int
expected a ')'
incomplete type is not allowed

void Double::Toswap()
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	bool ToSwitch = false;
	bool Switch = false;
	Dnode *current = head; 
	Dnode *first = NULL;
	Dnode *second = NULL;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current) && (Switch && ToSwitch == true))
	{
		if ((counter == pos1) && (ToSwitch == false))
		{
			first = current;
			ToSwitch = true;
		}
		if ((counter == pos2) && (Switch == false))
		{
			second = current;
			Switch = true;
		}
		current = current->next;
		counter++;
		
	}
	cout << first->value; 
	cout << second->value;
	void swap(first, second);

	
}

void Double :: swap(Dnode *x, Dnode *y)
{	
	if (x->prev)
	{
		(x->prev)->next = y;
	}
	if (y->prev)
	{
		(y->prev)->next = x;
	}
	if (x->next)
	{
		(x->next)->prev = y;
	}
	if (y->next)
	{
		(y->next)->prev = x;
	}
	Dnode *temp;
	temp = x->prev;
	x->prev = y->prev;
	y->prev = temp;
	temp = x->next;
	x->next = y->next;
	y->next = temp;

	temp = y = x = NULL;

}

[D80DSL3A]

Try removing the 'void' on line 32. It's a function call. This may clear the errors.

I tested your swap function.
It works for swapping non adjacent nodes. Nice job!
It fails however if x->next == y. So it would fail if pos1=2, pos2=3 for example.
I had to write separate code in my own swap function to deal with the two cases.
You also need to watch for swaps involving the head node. Your test case is one of these. pos1 = head. You'll need to re assign head.
Likewise for tail, if you're keeping one.

[alex067]

I removed the void, but how did your program run?

My program keeps crashing when it reaches the swap function.

Ah yes, mine does not work for adjacent nodes, how could I fix this?

[D80DSL3A]

I don't know why your program is crashing.
I wrote the Toswap function a bit different than yours. I went with the while loop I showed above.
But, you tested your Toswap() and found it worked. Also, your swap function works for non adjacent nodes. So???

I added code to my swap() to treat adjacent nodes as a separate case:

void Double :: swap(Dnode *x, Dnode *y)
{
    if( x->next == y )
    {
        // code for the adjacent nodes case
    }
    else
    {
        // code for non adjacent case
    }
}

[alex067]

It is saying that the problem first starts at the very first if statement on the swap function
if (x->prev)

#include <iostream>

using namespace std;

class Dnode
{
private:
	int value;
	Dnode *next;
	Dnode *prev;

	friend class Double;
};

class Double
{

private:
	Dnode *head;
	Dnode *tail;
public:
	Double()
	{
		head = NULL;
		tail = NULL;
	}
	bool IfEmpty() const;
	void add(int num);
	void addFront(int num);
	void addEnd(int num);
	void Insert(int num, int pos);
	void reverse();
	void Toswap();
	void swap(Dnode *x, Dnode *y);
	void size(int &size);
	void display();
	~Double();
};

bool Double :: IfEmpty() const
{
	return (head->next == tail); //return true if head next points to the tail 
}

void Double :: addFront(int num)
{
	Dnode *ptr = new Dnode;
	ptr->value = num;
	ptr->prev = NULL;
	ptr->next = NULL;

	if (head == NULL) //if list is empty

	{
		head = ptr;
	}
	else //if the link is not empty

	{
		head->prev = ptr;
		ptr->next = head;
		head = ptr;
	}

}

void Double::add(int num) //adds element to the last 
{
	Dnode *ptr = new Dnode;
	ptr->value = num;

	if (head == NULL)
	{
		addFront(num);
	}
	else //if list not empty 
	{
		Dnode * current = head;
		
		while (current->next != NULL)
		{
			current = current->next;
		}
		current->next = ptr;
		ptr->prev = current; 
		ptr->next = NULL;
	}
	 ptr = NULL;

}

void Double::size(int &size)
{
	int counter = 0;
	Dnode *current = head;
	while (current)
	{
		current = current->next;
		counter++;
	}
	size = counter;
	
}

void Double::Toswap()
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	bool ToSwitch = false;
	bool Switch = false;
	Dnode *current = head; 
	Dnode *first = NULL;
	Dnode *second = NULL;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current) && (Switch && ToSwitch == true))
	{
		if ((counter == pos1) && (ToSwitch == false))
		{
			first = current;
			ToSwitch = true;
		}
		if ((counter == pos2) && (Switch == false))
		{
			second = current;
			Switch = true;
		}
		current = current->next;
		counter++;
		
	}
	swap(first, second);
	first = second = current = NULL;

	
}

void Double :: swap(Dnode *x, Dnode *y)
{	
	if (x->prev)
	{
		(x->prev)->next = y;
	}
	if (y->prev)
	{
		(y->prev)->next = x;
	}
	if (x->next)
	{
		(x->next)->prev = y;
	}
	if (y->next)
	{
		(y->next)->prev = x;
	}
	Dnode *temp;
	temp = x->prev;
	x->prev = y->prev;
	y->prev = temp;
	temp = x->next;
	x->next = y->next;
	y->next = temp;

	temp = y = x = NULL;

}

void Double::display()
{	
		
		Dnode *current = head;
		while (current)
		{
			cout << current->value << " ";
			current = current->next; //start pointing to the next node

		}
		current = NULL;
}

Double::~Double()
{
	Dnode *current = head;
	
	while (current)
	{
		Dnode *temp = current->next;
		delete current;
		current = temp;
	}
	current = NULL;
	delete head;
	delete tail;
}

int main()
{
	Double one;
	int size;

	one.addFront(0);
	one.addFront(2);
	one.addFront(3);
	one.addFront(4);

	one.display(); //4 3 2 0 
	cout << endl;
	one.add(1);
	one.display(); // 4 3 2 0 1 

	one.size(size);


	one.Toswap(); //swap first node and second node
	one.display();
	cout << endl;



	system("PAUSE");
	return 0;

}

[D80DSL3A]

Re test your Toswap function.
You assign both Switch and ToSwitch = false where declared, then loop on the condition:
while ((current) && (Switch && ToSwitch == true)). The loop will stop if either bool is false. I think the loop is never entered therefore both first and second still = NULL when swap is called.

I see other problems in your code but they're unrelated to the present problem, so maybe get to them later.

EDIT: My testing shows this is exactly what's happening. So you still need to fix Toswap. It's not time to test swap yet.

You need to learn to debug your own code. I tested your Toswap function by inserting a couple of cout statements to help show what's going on:

void Double::Toswap()
{
	int pos1, pos2, counter;
	pos1 = 1;
	pos2 = 3;
	counter = 1;
	bool ToSwitch = false;
	bool Switch = false;
	Dnode *current = head; 
	Dnode *first = NULL;
	Dnode *second = NULL;
	cout << "Switching node 1 and 3 of the current node list" << endl;

	while ((current) && (Switch && ToSwitch == true))
	{
                cout << "Got in!!\n";
		if ((counter == pos1) && (ToSwitch == false))
		{
			first = current;
			ToSwitch = true;
		}
		if ((counter == pos2) && (Switch == false))
		{
			second = current;
			Switch = true;
		}
		current = current->next;
		counter++;
		
	}
        cout << "In Toswap: first = " << first << " second = " << second << endl;
//	swap(first, second);
	first = second = current = NULL;	
}

The "Got in!!" statement (line 16) does not appear, but "first = 0 second = 0" (line 31) does.
This means the loop was never entered and that first and second still = NULL, as suspected.