Swapping Linked List Nodes in C... YEARGGH!

Call Me Jimmy

I have been trying to simply swap two nodes in a linked list for fcking ages... tried so many ways and each time it hasn't worked... I really need help, this is driving me crazy!

ok so here is one of the (failed) attempts:

typedef struct lnode
{
	void		*data;
	lnode		*next;

}llnode;

// I understand how completely wrong this is, but it's like
// my 50th attempt, i've tried the more straightforward stuff

void swapNodes(lnode **n1,lnode **n2)
{
	lnode *temp;

	temp = *n1;

	*n1 = *n2;

	n2 = &temp;

}

so any help would be greatly appreciated!

ianhobo

Just a quick glance, you seem to have all the right elements, but you've made things over complicated for yourself!

In your structure declaration, your data value , did you mean it to be a pointer? Typically it wouldnt be a pointer, but something like "int data".
Only the second member would be a pointer, as it points to the next list structure.

So with that in mind, some of your dereferencing has become a bit muddled, you should only need one level indirection (*) for your swap function, not two (**) . there should be no pointers to pointers needed here
your passing in **, you should only need *

        lnode *temp;

	temp = *n1;

Here, you've created a pointer of type lnode called temp, but you've set it equal to what n1 points at, rather than the address of where n1 structure is.
try simply

       temp = n1;

So as a starting point, make your "void *data" an "int data", and try rethink what your trying to do,

satchmo

Nothing wrong with data in a linked list being a pointer, and it doesn't make any difference to what he's trying to do here.

Almost there Jimmy.. like ianhobo said, just pass in single pointers as parameters and swap them around like they were regular datatypes (ie no dereferencing).

Call Me Jimmy

Thanks guys, i got it early this morning

See I had tried the simple swapping regular pointers before that and for some reason I lost a pointer in the operation so I rewrote it to return the new first pointer and it worked. Here is what I did, it had an element of luck about it, what do you guys think, it works but would it be what you would expect?

lnode* swap(lnode *n1, lnode *n2)
{
	lnode *temp;
	temp = n2->next;
	n2->next = n1;
	n1->next = temp;
	return n2;
}

for some reason if i dont return n2 it doesn't work in my list

ronivek

Looks fine.

What are you doing with the returned pointer?

Call Me Jimmy

ronivek wrote: »

Looks fine.

What are you doing with the returned pointer?

well it was for adjacent nodes and it wouldnt work unless i returned a pointer so i called it like

firstpointertoswap = swap(first,second)

but now I need to know something else.

If I have a Linked list where the the data fields are void pointers (so pointers to any type)
when I free each node, will that free the stuff pointed to by the void data pointers?
More importantly, when I allocate memory for a node (defined above) that doesn't allocate memory for the data does it?

Call Me Jimmy

YEAARGH, I wrote it in what I thought was C (compiling in visual C++).
But now I have changed the name ending to .c it doesn't compile! million errors!

Can anyone have a glance at this and tell me if I have used anything that isn't C specific?!

// constants used for setting the order of list
#define ORDER_NONE 1
#define ORDER_ASCENDING 2

// defines one list node
// internally used by linked list
typedef struct lnode
{
	void			*data;
	struct lnode	*next;
 
}lnode;

//defines what each list will have
// user will see this
typedef struct llist
{
	lnode	*head;
	int		order;
	int		(*compareFunc)(void *data1, void *data2);
}llist;


/*
=======================
 function prototypes
=======================
*/
void add			(llist &list, void *data);
void removeFirst	(llist &list);
void setOrder		(llist &list,int order);
void insertBefore	(llist &list, lnode *target,lnode *prev, void *data);
void freeListMemory	(llist &list);
void freeNodes		(lnode *head);
void* getFirst		(llist &list);

lnode* newNode		(void *data);
llist newList		();

bool isEmpty		(llist &list);

int	compareInts		(void *x, void *y); // for comparing two ints, not used
void print			(llist &list);	// for debugging, prints ints
lnode* swap			(lnode *n1, lnode *n2); //no longer used


/*
=====================
getFirst

returns a pointer to the first data element in the list
=====================
*/
void* getFirst(llist &list)
{
	if(isEmpty(list))
		return NULL;
	else
		return list.head->data;
}

/*
=====================
removeFirst

Removes and deletes the first node in the list
=====================
*/
void removeFirst(llist &list)
{
	if(isEmpty(list))
		return;

	lnode *second;
	second = list.head->next;
	free(list.head);
	list.head = second;
}

/*
====================
newList

Returns a new initialized list
====================
*/
llist newList()
{
	llist list;
	list.head = NULL;
	return list;
}

/*
=================
setOrder

Sets the method for adding items to the list
ORDER_NONE - the data will be appended to the end of the list
ORDER_ASCENDING - the data will be put in lower to higher order
=================
*/

void setOrder(llist &list,int order)
{
	list.order = order;
}

/*
===============
isEmpty

Determines if the list is empty
===============
*/

bool isEmpty(llist &list)
{
	if(list.head == NULL)
		return true;
	else
		return false;
}


/*
=================
Add

Adds a new node with the data to the list
=================
*/
void add(llist &list, void *data)
{
	lnode *curr;
	lnode *prev;
	
	switch(list.order)
	{

	case ORDER_NONE:
		//list is empty
		if(isEmpty(list))
		{
			list.head = newNode(data);
		}
		//list is not empty so traverse the list and add the node
		else
		{
			curr = list.head;

			while(curr->next)
			{
				curr = curr->next;
			}

			curr->next = newNode(data);

		}break;

	case ORDER_ASCENDING:

		if(isEmpty(list))
		{
			list.head = newNode(data);
		}
		else
		{
			curr = list.head;
			prev = NULL;
			//therein lies da rub

			while((list.compareFunc(data,curr->data)) > 0 )
			{
				prev = curr;
				if(curr->next)
					curr = curr->next;
				else
				{
					curr = NULL;
					break;
				}
			}

			insertBefore(list,curr,prev,data);

		}
	}
}

/*
=================
freeListMemory

Traverses a list releasing each nodes' memory
================
*/

void freeListMemory(llist &list)
{
	if(isEmpty(list))
		return;
	
	freeNodes(list.head);
	list.head = NULL;
}

/*
=================
freeNodes

Releases the memory of all nodes starting with the head
=================
*/
void freeNodes(lnode *head)
{
	if(head->next)
		freeNodes(head->next);

	free(head);
}

/*
==================
insertBefore

attempts to insert the data before the target node in the list
==================
*/
void insertBefore(llist &list, lnode *target,lnode *prev, void *data)
{
	lnode *newnode;
	//nodes given dont exist
	if(!target)
	{
		target = newNode(data);
		prev->next = target;
		return;
	}

	newnode = newNode(data);

	if(isEmpty(list))
	{
		list.head = newnode;
	}
	//target is the head 
	else if(!prev)
	{
		list.head = newnode;
		newnode->next = target;
	}
	else
	{
		prev->next = newnode;
		newnode->next = target;

	}
}

/*
==================
swap

swaps two nodes (not used anymore)
==================
*/
lnode* swap(lnode *n1, lnode *n2)
{
	lnode *temp;
	temp = n2->next;
	n2->next = n1;
	n1->next = temp;
	return n2;
}

/*
================
newNode

Creates space for a new node and gives it data
================
*/
lnode* newNode(void *data)
{

	lnode* node = (lnode*)malloc(sizeof(lnode));
	node->data = data;
	node->next = NULL;
	return node;
}


/*
=======================
print

for debugging - prints list of ints
=======================
*/
void print(llist &list)
{
	lnode *curr;

	if(isEmpty(list))
		return;

	curr = list.head;
	while(curr)
	{
		int *pInt = (int*)(curr->data);
		printf("%d\n",*pInt);
		curr = curr->next;
	}	
}

int compareInts(void *x, void *y)
{
	int a = *(int*)x;
	int b = *(int*)y;

	if(a > b)
		return 1;
	else if(a < b)
		return -1;
	else
		return 0;
}

Thanks

ianhobo

What are some of the errors that your getting?
And type of file was it before?

Is this for a college project or work? Did you write it all yourself?? hmmm
Because some parts of it would have some generally advanced C concepts, well beyond the complexity of understanding linked lists anyway.
Just curious

Regarding your memory question, if you declared, you delete it

Call Me Jimmy

ianhobo wrote: »

What are some of the errors that your getting?
And type of file was it before?

Is this for a college project or work? Did you write it all yourself?? hmmm
Because some parts of it would have some generally advanced C concepts, well beyond the complexity of understanding linked lists anyway.
Just curious

Regarding your memory question, if you declared, you delete it

I'll take it as a compliment that you question whether I wrote it! Yea I did! This is for learning btw.

Ok so the errors, I have only started getting them since I made it a .c instead of a .cpp. I get about 62 of these "error C2143: syntax error : missing ')' before '&'" argggh and have no idea why its happening!

ianhobo

ha ha I only question mainly because of your funky function pointer in one of your structs,

ok, I don't have MSVS here, its eclipse for me, so ill copy and paste and see what happens.
I presume its just the normal includes your using. stdio.h, anything else?

But there is something questioning in my head whether the referencing might differ in c and cpp?

What happen if you pass the list node as * rather than &?
Even change it for just one of the functions, and see if the error goes away....

I'l get back to you in a while

Call Me Jimmy

ianhobo wrote: »

ha ha I only question mainly because of your funky function pointer in one of your structs,

ok, I don't have MSVS here, its eclipse for me, so ill copy and paste and see what happens.
I presume its just the normal includes your using. stdio.h, anything else?

But there is something questioning in my head whether the referencing might differ in c and cpp?

What happen if you pass the list node as * rather than &?
Even change it for just one of the functions, and see if the error goes away....

I'l get back to you in a while

thanks! The only includes i have are stdlib and stdio

ianhobo

it appears that pass by reference of the form

void fnct(int &var);

is c++ only, C doesn't appear to support this passing type

http://www.techiwarehouse.com/cms/articles.php?cat=18 (half way down)
http://www.maths.cam.ac.uk/undergrad/catam//ccatsl/manual/node50.html

What you will have to do, and what works in the copy and paste of your code that I did, was to remove your '&' from your function prototpes and replace with '*'.
The consequence of this is that throughout your code you will have to change all your functions from x.y->z to x->y->z

It is a bit confusing though, the compiler that I use in work *does* suppport it, but its a custom compiler for a specific paltform, but what I've read this morning seems to suggest that in general, you can't do it in C.
Hope that helps!

Anyone else any thoughts, explanations?

Call Me Jimmy

ianhobo wrote: »

it appears that pass by reference of the form

void fnct(int &var);

is c++ only, C doesn't appear to support this passing type

http://www.techiwarehouse.com/cms/articles.php?cat=18 (half way down)
http://www.maths.cam.ac.uk/undergrad/catam//ccatsl/manual/node50.html

What you will have to do, and what works in the copy and paste of your code that I did, was to remove your '&' from your function prototpes and replace with '*'.
The consequence of this is that throughout your code you will have to change all your functions from x.y->z to x->y->z

It is a bit confusing though, the compiler that I use in work *does* suppport it, but its a custom compiler for a specific paltform, but what I've read this morning seems to suggest that in general, you can't do it in C.
Hope that helps!

Anyone else any thoughts, explanations?

EDIT: errors gone
thanks a lot for the help! really appreciate it! So regarding freeing nodes... if I free a node that only frees the pointers? It wont free whats pointed to by the void pointers? And unless I malloc the actual data then it wont wont be on the heap? Like if i malloc the size of an lnode, that wont provide space or accomodate the space for the stuff that will be pointed to by the void pointers?

ianhobo

if you have a structure/node which has a pointer to a data type as a member, you would have to declare memory for that pointer member to point at.

If you then create your nodes through malloc, you will have to free both the memory for the structure/node, and for the memory that its pointer member is pointing at.

Suggestion:

Create a freeNode function responsible for freeing the memory that is used for the node.
In here, have an if statement checking if this particular nodes pointer data member is null. If it is null, dont worry about it, if its not null free the memory, then free the memory for the node

Hope that helps

Ian

ianhobo

Call Me Jimmy wrote: »

if I free a node that only frees the pointers? It wont free whats pointed to by the void pointers? And unless I malloc the actual data then it wont wont be on the heap? Like if i malloc the size of an lnode, that wont provide space or accomodate the space for the stuff that will be pointed to by the void pointers?

Didn't you say you wrote this? ha ha

Your code/linked lists doesn't seem to be concerned with the memory of the structure members void pointers.
It accepts a pointer when createing a new node, and copies this pointer, so presumably this has been allocated elsewhere, so you still have to free this memory after the lists and nodes are free'd

think about the way that your function to create a new node works, and basically reverse this process,
But careful that the data which the structures are pointing to isn't still being used my some other function, as the list didn't allocate them, they could easily be in use by other functions.

If deleting the list and nodes is part of an exit function for example, then you could use what I said in my previous post about about freeing the member memory along with the node, but again, you have to be sure that the memory won't be free'd anywhere else either, freeing the same memory more than once can cause strange things to happen!

Having had a closer look at the code, don't just include the method of deleting the memory that the member pointer is pointing when freeing the nodes without fully understanding the implications.

ok, hope that hasnt caused any confusion!
Do you get me?

Call Me Jimmy

ianhobo wrote: »

Didn't you say you wrote this? ha ha

Your code/linked lists doesn't seem to be concerned with the memory of the structure members void pointers.
It accepts a pointer when createing a new node, and copies this pointer, so presumably this has been allocated elsewhere, so you still have to free this memory after the lists and nodes are free'd

think about the way that your function to create a new node works, and basically reverse this process,
But careful that the data which the structures are pointing to isn't still being used my some other function, as the list didn't allocate them, they could easily be in use by other functions.

If deleting the list and nodes is part of an exit function for example, then you could use what I said in my previous post about about freeing the member memory along with the node, but again, you have to be sure that the memory won't be free'd anywhere else either, freeing the same memory more than once can cause strange things to happen!

Having had a closer look at the code, don't just include the method of deleting the memory that the member pointer is pointing when freeing the nodes without fully understanding the implications.

ok, hope that hasnt caused any confusion!
Do you get me?

I did write it but i was assuming that freeing a node just freed everything associated with it, whereas now i have more knowledge (which makes it harder funnily enough ) I found out about the heap corruption as I tried yer first suggestion though! That implies that all data added has been malloc'd. I think I'm beginning to understand properly though thanks for the time anyway

ianhobo

ok, good. It can be very confusing at times! I still get stumped quite often, and its back to the aul pen and paper to draw out my memory!

I found out about the heap corruption as I tried yer first suggestion though! That implies that all data added has been malloc'd.

Probably the same memory has been free'd twice, (the list free function, and then later on in the code somewhere else), resulting in heap corruption.
As your list functions don't malloc any memory for the data members, all memory would have either been previously malloced, or are pointers to locally declared data

thanks for the time anyway

Your welcome, glad I could help, anytime