swapping nodes in double linked list

Hi there,

I am practicing making a double linked list. And I make a function to swap two nodes of double linked list but there's a problem in setting temporary variable to keep node's original link address...

To switch two node pointers, object1 and object2, I made another two local node pointers, temp1 and temp2, to store object1 and object2's original addresses.

But in the middle of process when I changed object's link, temp1 and temp2's addresses are also changed..

I don't want to lose the address that I set first in temp1 and temp2..

Can anybody help me to figure out how I can fix it or
show me the right-working swap function working by handling links in double linked list?


it's my struct for double linked list.

Code:

typedef struct _object Object;

struct _object
{
	unsigned long	ID;
	char	 *	name;
	int		age;
	
	Object *		prev;
	Object *		next;
};

And bellow is swap function that I made..

Code:

//swapping two nodes(object1 and object2)
void objectSwap(Object *object1, Object *object2){
	Object *temp1=object1; /* store object1's original address to temp1 */
	Object *temp2=object2; /* store object2's original address to temp2 */


	//error checking
	if(object1 == NULL || object2 == NULL){ 
		fprintf(stderr, "objectSwap() :: No node to swap.\n");
	}
	else{	
		printf("temp1->prev : %d\t temp1->next : %d\n", temp1->prev, temp1->next);
		printf("temp2->prev : %d\t temp2->next : %d\n", temp2->prev, temp2->next);


//******************************** in this part *************************************/

		object1->next=temp2->next;  /* set object1's next link to temp2(object2)'s next link */
		object1->prev=temp2->prev; /* set object1's previous link to temp2(object2)'s previous link */	

//************* I lost temp1's original address that I had stored at first****************/


		printf("temp1->prev : %d\t temp1->next : %d\n", temp1->prev, temp1->next);
		printf("temp2->prev : %d\t temp2->next : %d\n", temp2->prev, temp2->next);

		if(temp2->prev != NULL) /* if temp2(object2)'s previous link is NULL that means temp2 is the first node(head) in the list. */
			temp2->prev->next=object1;
		if(temp2->next != NULL) /* if temp2(object2)'s next link is NULL that means temp2 is the last node(tail) in the list. */
			temp2->next->prev=object1;

		/* same process for object2 */
		object2->next=temp1->next;
		object2->prev=temp1->prev;

		if(temp1->prev != NULL)
			temp1->prev->next=object2;
		if(temp1->next != NULL)
			temp1->next->prev=object2;
	}
}

You should only need one temporary object.

Code:

temp1->prev = object1->prev ; 
temp1->next = object1->next ; 

object1->prev = object2->prev ; 
object1->next = object2->next ; 

object2->prev = temp1->prev ; 
object2->next = temp1->next ;

Dino is right; you need only one temp variable for swapping the two objects and you are not losing temp1's original address but temp1->next and
temp1->prev are each pointing to a new Object. Print the contents of the temp1 pointer before and after the swap ie

Code:

 printf("Before Swap :: temp1 is %p\t temp2 is %p\n", temp1, temp2);
                printf("temp2->prev : %d\t temp2->next : %d\n", temp2->prev, temp2->next);
//******************************** in this part *************************************/

		object1->next=temp2->next;  /* set object1's next link to temp2(object2)'s next link */
		object1->prev=temp2->prev; /* set object1's previous link to temp2(object2)'s previous link */	

//************* I lost temp1's original address that I had stored at first****************/
		printf("temp1->prev : %d\t temp1->next : %d\n", temp1->prev, temp1->next);
                printf("After Swap :: temp1 is %p\t temp2 is %p\n", temp1, temp2);

Why are you monkeying with link pointers? A node is a node is a node. Just swap the contents. There is no need to move nodes around.

Originally Posted by brewbuck

Why are you monkeying with link pointers? A node is a node is a node. Just swap the contents. There is no need to move nodes around.

Unless of course the payload object you are storing is HUGE and the links are small, and thus it's beneficial to change the pointers rather than swapping the payloads.

--
Mats

matsp is on the mark as thats exactly the case in this scenario ie
sizeof pointer to Object < sizeof Object

Originally Posted by matsp

Unless of course the payload object you are storing is HUGE and the links are small, and thus it's beneficial to change the pointers rather than swapping the payloads.

Good point. But if the payload is "huge" I might hold it by pointer in the node anyway, reducing it back to a pointer swap again.

Keeping the payload off somewhere else might be nice if you were, for instance, using a custom allocator to allocate those payloads.

Originally Posted by Dino

You should only need one temporary object.

Assuming you mean "temporary pointer", then I beg to differ. To be fully generic and able to swap any two nodes, you need pointers to:
The node before object1
The node after object1
The node before object2
The node after object2
Then there are special cases to handle, when the node after object1 is object2 or the node after object2 is object1. Not to mention handling when any of those first four are NULL because the item is at an end of the list.

On this occasion, the code posted doesn't work because it is too simplistic. It does not handle all the cases mentioned. Usually it's the other way around, but seriously it's not trivial to completely swap (by relinking) two node in a doubly linked list!

Which sort of supports brewbuck's point that one should merely have a node that contains a pointer to the datastructure. The pointers could easily be swapped:

Example:

Code:

struct node_t
{
  void *data;
  struct node_t *prev, *next;
};

void swap(struct node_t *a, struct node_t *b)
{
  assert(a && b);

  void *temp = a->data;
  a->data = b->data;
  b->data = temp;
}

you are not losing temp1's original address but temp1->next and
temp1->prev are each pointing to a new Object.

You're right. I didn't see what I wanted was not to lose temp1->next and temp1->prev.

Originally Posted by iMalc

Then there are special cases to handle, when the node after object1 is object2 or the node after object2 is object1. Not to mention handling when any of those first four are NULL because the item is at an end of the list.

On this occasion, the code posted doesn't work because it is too simplistic. It does not handle all the cases mentioned. Usually it's the other way around, but seriously it's not trivial to completely swap (by relinking) two node in a doubly linked list!

I agree with you. I thought only what to do if one of these two is the first or the last node of double linked list. And if nodes to swap are consequtive, it won't work.

Don't I need to check and change both side of object's links which point to the object to replace?

for exampe, there are 5 nodes.
A - B - C - D - E
And I want to swap B and D(by handling nodes). So I set B and D's next, prev link pointers for new place. I also think that I have to change A's next link and C's prev link and C's next and E's prev to make like bellow.
A - D - C - B - E

In this case, I think it's not enough to make only one temporary pointer.

Sorry for my ignorance.

Originally Posted by a0161

Don't I need to check and change both side of object's links which point to the object to replace?

Yes you need to check both sides of the link ie *prev and *next

Originally Posted by a0161

for exampe, there are 5 nodes.
A - B - C - D - E
And I want to swap B and D(by handling nodes). So I set B and D's next, prev link pointers for new place. I also think that I have to change A's next link and C's prev link and C's next and E's prev to make like bellow.
A - D - C - B - E

In this case, I think it's not enough to make only one temporary pointer.

IMHO the min no. of pointers needed for the swap is two as in a pointer to A and a pointer to C and here's the pseudo-code to swap B and D around.

Code:

/* install B in D's place */
ptr_to_B->prev = ptr_to_D->prev
ptr_to_B->next = ptr_to_D->next
ptr_to_D->prev->next = ptr_to_B
ptr_to_D->next->prev = ptr_to_B

/* install D in B's place */
ptr_to_D->prev = ptr_to_A
ptr_to_D->next = ptr_to_C
ptr_to_A->next = ptr_to_D
ptr_to_C->prev = ptr_to_D

Thank you for providing pseudo-code

Now I got there are another conditions that I didn't consider.
The code I made does not cover every condition.

Yes, my example, while a good example for some problem maybe not pertinent, was incomplete.