Linked List, void pointer, problems.

Hi folks,
I have been writing a linked list today just for a bit of learning, all was going well and the list is fine, I can add and remove nodes and everything, I didnt start to have any problems until I wanted to do a simple node by node search for a key, I think the problem is being caused by the way I am casting a void pointer.

Code:

typedef struct _llnode LLNODE; struct _llnode { LLNODE *next; LLNODE *prev; int x; }; typedef struct _llist LLIST; struct _llist { LLNODE *head; LLNODE *tail; unsigned char cnt; }; /* Usage: Traverse forward or backwards through a list. */ void *llist_travrse(void *node, TRAV_DIRECTION dir) { if(dir == TRAVERSE_FORWARD) return (void *)(((LLNODE*)node)->next); else return (void *)((LLNODE*)node)->prev; } /* Usage: Look through a list for a specific value. */ void *llist_search(LLIST *list, int key) { void *temp = &((LLIST*)list)->head; //Search the entire list for the value specified. while(temp != NULL) { //We have found the key. if(((LLNODE *)temp)->x == key) { return (void *)temp; } else { temp = llist_travrse(&temp, TRAVERSE_FORWARD); } } return NULL; }

When I call the llist_travrse I was expecting the value to be returned to be equal to the next node in the list whereas what seems to happen is that the value being returned is actually equal to the value of the current node, I fear I am overlooking something simple here!?

I have just changed to the new MPLab X IDE as well which I think could be adding to my confusion!

Cheers for any help!

Pheetuz.

The main reason for the problem is that there are several unnecessary casts.
Declare temp as an LLNODE*, and remove every cast you can.

The cause is probably due to passing &temp instead of temp.

As for why it's doing what it's doing... it's because the 'next' pointer is the first item in the struct, so following the next pointer is exactly equivalent to just dereferencing a pointer to the node.

Thanks iMalc.

Got it working in the end, you were right about the &temp thing and as for the casting I did have it like below before but changed it when I couldn't get it to work.

Code:

/* Usage: Look through a list for a specific value. */ void *llist_search(LLIST *list, int key) { LLNODE *temp = list->head; while(temp != NULL) { //We have found the key. if(temp->x == key) { return (void *)temp; } else { temp = llist_travrse(temp, TRAVERSE_FORWARD); } } return NULL; }

Many thanks,

Pheetuz.

That looks great now.

You're welcome!

Having another problem with this linked list so thought I would post it in the same thread.

Basically I have already found a way around the problem that I am having but do not understand why my solution is different to what I was doing in the first place.

The function I am writing is one to remove a node from a list, the problem is specifically occuring when I try to remove the head by making the next node in the list the head and changing its "prev" pointer to NULL.

These are the structure definitions:

Code:

typedef struct _llnode LLNODE; struct _llnode { LLNODE *next; LLNODE *prev; int x; }; typedef struct _llist LLIST; struct _llist { LLNODE *head; LLNODE *tail; unsigned char cnt; };

This is what I originally had as my code:

Code:

void llist_remove(LLIST *list, LLNODE *node) { LLNODE *ptr; if(node == list->head) { //Then assign the second node the head status. list->head = list->head->next; //Remove the link to the previous head. list->head->prev = NULL; //WRONG!!! } }

But this did not nullify the prev pointer on the new head. (I am not using sentinal nodes and the list is correct in that each node points where it should.)

The code that I am now using that correctly nullifys the prev pointer is:

Code:

void llist_remove(LLIST *list, LLNODE *node) { LLNODE *ptr; if(node == list->head) { //Then assign the second node the head status. list->head = list->head->next; //Point ptr at new head. ptr = list->head; //Remove the link to the previous head. ptr->prev = NULL; } }

I do not understand the difference between the two above proceedures and although I have got it working in the bottom code snippet I would like to know what I was doing wrong in the first place!

Many thanks!

Pheetuz.

There shouldn't be a difference between those two functions. This suggests that the fix actually occured elsewhere.

Agreed. There is no difference between those two functions (both look correct). I've use the first one because it's shorter. May as well remove the unused variable too.
The problem, or fix, must have been elsewhere.

Oh wait, this can't be the whole function because it only removes from the head, so I'm guessing that you've only shown a cut down version of that function and in the process of cutting it down you've accidentally left out the part that shows the problem.
Please post the whole function as it is in your code.

This is the code below, you can see from my comments where the "problem" lies, really don't see what the problem is though, it could be the IDE that I am using though as it is still in beta, haven't tried it on another IDE.

Code:

void llist_remove(LLIST *list, LLNODE *node) { LLNODE *ptr; //Invalid node, probably from a search gone wrong. if(node != list->head && node->next == NULL) { return; } if(node == list->head) { //Then assign the second node the head status. list->head = list->head->next; //Point ptr at new head. ptr = list->head; //Remove the link to the previous head. ptr->prev = NULL; //Remove the link to the previous head. //list->head->prev = NULL; //WRONG!!! but how is it different to the above two statements??? } else if(node == list->tail) { //Then assign the second to last node the tail status. list->tail = list->tail->prev; //Make ptr point to the new tail. ptr = list->tail; //Remove the link to previous tail. ptr->next = NULL; } //If the node is not at either end of the list. else { //Point the node before the one to remove at the node after the one to remove. node->prev->next = node->next; //Point the node after the one to remove at the node before the one to remove. node->next->prev = node->prev; } //Decrement count because element has been removed. list->cnt --; }

Cheers for your help guys.

Again, both pieces of code should do the same thing.
But your code is not properly setting next and prev ptrs.
Try rewriting your algorithm along these lines:

If node has a next node, the next node gets node->prev.
If node has a prev node, the prev node gets node->next.
If node is the head node, the head node becomes node->next.
If node is the tail node, the tail node becomes node->prev.
Decrement cnt (which should probably be an int or unsigned int.)

Also, you probably want to delete node after unlinking it from the list.

Lines 5-7 look wrong to me as they'd prevent you from removing the last node in the list, which would match the conditions in the if-statement. I recommend that you simply remove those lines. They are perhaps half the problem.

The other half of the problem is that you're not handling the case of removing the sole item from a list of just one item. In that case you need to fixup both head and tail. Basically any time you remove from the list you need to fix up two things. Those two things might be:
(1) prev and next, or (2) prev and head, or (3) tail and next, or (4) head and tail.

You can either handle all four cases separately, or you can come up with a way of doing it where it does whichever of those things are needed. Hint: You either need to fix up next or head, and also prev or tail.