Thread: swapping nodes in double linked list

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    12

    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;
    	}
    }

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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 ;
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    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);

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    matsp is on the mark as thats exactly the case in this scenario ie
    sizeof pointer to Object < sizeof Object

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by matsp View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Dino View Post
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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;
    }

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    12
    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.

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    12
    Quote Originally Posted by iMalc View Post
    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.
    Last edited by a0161; 10-30-2008 at 05:51 PM.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    12
    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.

  13. #13
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by a0161 View Post
    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
    Quote Originally Posted by a0161 View Post
    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
    Last edited by itCbitC; 10-30-2008 at 05:47 PM.

  14. #14
    Registered User
    Join Date
    Oct 2008
    Posts
    12
    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.

  15. #15
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Yes, my example, while a good example for some problem maybe not pertinent, was incomplete.
    Mainframe assembler programmer by trade. C coder when I can.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Help with swapping nodes in a linked list
    By Axel in forum C Programming
    Replies: 3
    Last Post: 10-18-2005, 09:16 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM