Swap nodes in linked list

This is a discussion on Swap nodes in linked list within the C Programming forums, part of the General Programming Boards category; hi all, right i am trying to swap two nodes around in a linked list, as part of a sort ...

  1. #1
    Boaz
    Guest

    Swap nodes in linked list

    hi all, right i am trying to swap two nodes around in a linked list, as part of a sort functions. How while swapping the nodes a round i am tryin to take into account if the nodes been swaped are at the start or end of the linked list, how i have written the following, but its does not work correctly (makes an node within the linked lists disaprear) have you got any ideas whats wrong or do any of you have a function which does what i am looking for that i could have

    regards BOAZ

    Code:
    void swapNodes(pre_rec temp, pre_rec temp1)
    {
        pre_rec templeft, tempright;
    
        templeft = temp->prev;
        tempright = temp1->next;
    
        temp->next = temp1;
        temp1->prev = temp;
    
        if (templeft != NULL)
        {
            templeft->next = temp1;
            temp1->prev = templeft;
        }
        else
        {
            temp1->prev = NULL;
        }
    
        if (tempright != NULL)
        {
            tempright->prev = temp;
            temp->next = tempright;
        }
        else
        {
            temp->next = NULL;
        }
    }

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    This is what I'd do:
    Code:
    void Swap(NODE** Node1, NODE** Node2)
    {
       NODE* Temp = (*Node1);
       (*Node1) = (*Node2);
       (*Node2) = Temp;
    }
    
    void SwapNodes(NODE* Node1, NODE* Node2)
    {
       //Repoint the nodes around the first node
       if(Node1->Prev) Node1->Prev->Next = Node2;
       if(Node1->Next) Node1->Next->Prev = Node2;
    
       //Repoint the nodes around the second node
       if(Node2->Prev) Node2->Prev->Next = Node1;
       if(Node2->Next) Node2->Next->Prev = Node1;
    
       //Swap the Next/Prev pointers for the two nodes
       Swap(&Node1->Next, &Node2->Next);
       Swap(&Node1->Prev, &Node2->Prev);
    }
    EDIT: It even works if they are next to each other or if they are the same nodes, which it doesn't seem to do at a first glance .
    Last edited by Magos; 05-06-2003 at 01:26 PM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    2

    Swap nodes in linked list

    Hi,
    i have written a small code for this. have a look at it

    insert
    Code:
    void swapNodes(node *p, node *q) {
    	printf("\nNode to be swapped p = %d\t q = %d\n", p->val, q->val);
    	node *prevP, *prevQ, *temp;
    	// check if one of it is head or not
    
    	if(p != head && q != head) {
    		for(prevP = head; prevP->next != p; prevP = prevP->next);
    		for(prevQ = head; prevQ->next != q; prevQ = prevQ->next);
    		prevP->next = q;
    		temp = q->next;
    		q->next = p->next;
    		prevQ->next = p;
    		p->next = temp;
    	} else {
    		prevP = prevQ = NULL;
    		if(head == p) {
    		       for(prevQ = head; prevQ->next != q; prevQ = prevQ->next);
    		       head = q;
           		       prevQ->next = p;
    		} else {
    		       for(prevP = head; prevP->next != p; prevP = prevP->next);
    		       head = p;
           		       prevP->next = q;
    		}
    		temp = q->next;
    		q->next = p->next;
    		p->next = temp;
    	}
    }
    Regards,
    Sandeep Patra

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    What is this going to be called from?
    If it's inside a sorting algorithm then you're probably going to have a lot more problems than you realise.
    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"

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Hm, so that's how I coded 6 years ago...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    whats a node ?

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    A node is like a space in a book shelf - it can hold things. You decide via your program, what that "thing" will be (a struct is common), and you decide via pointers on the link, what shelf and column you want that "thing" to rest upon.

    Each node is connected to another node, which makes the term "linked list" a good one.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 04:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21