Algorithm for swapping two nodes in a doubly lineked list.

This is a discussion on Algorithm for swapping two nodes in a doubly lineked list. within the C Programming forums, part of the General Programming Boards category; I'm trying to swap two nodes in a doubly linked list and I'm going nutzo trying to get it right. ...

  1. #1
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72

    Algorithm for swapping two nodes in a doubly lineked list.

    I'm trying to swap two nodes in a doubly linked list and I'm going nutzo trying to get it right.

    Here's the algorithm that I've written.

    Please note: I can't just change the data. I tried that and the instructor projetile vomited the work back to me and told me "go home and swap them pointers boy!".

    Anyway, I've been working on this since last night to no avail. can someone assist?
    thanks in advance.

    assuming that:
    POS1, POS2 and temp are all nodes of the same type.
    Code:
    temp = POS2;
        POS1->Prev = POS2->Prev;
        POS1->Next = POS2->Next;
        POS2->Prev = POS1;
        POS2->Next->Prev = POS1;
        temp->Next = POS1->Next;
        temp->Prev = POS1->Prev;
        POS1=temp;
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  2. #2
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    I'm not 100% sure what you're trying to do. But I think this might help:

    Code:
    temp=POS1;
    POS1->next=POS2->next;
    POS1->prev=POS2;
    POS2->next=temp->next;
    POS2->prev=temp->prev;
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I like this way

    n1, n2 are our nodes.
    n1 is before n2.

    n1->prev->next=n2;
    n2->next->prev=n1;
    n1->next=n2->next;
    n2->prev=n1->prev;
    n1->prev=n2;
    n2->next=n1;

    You could in effect produce the same end result without ever switching the nodes at all:

    type var;
    var = node1->var;
    node1->var = node2->var;
    node2->var = var;

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72

    Angry

    Sorry guys, neither works.

    I can't swap the values. I have to move the pointers.

    Pos2 is before Pos1.
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    swopping the pointers is the same as moving the value. The finished nodes will be identical either way.Imagine your linked list is a large line of identical buckets and they are roped together with knotted rope(pointers). Is it easier to swop whats in the buckets or untie and move each one? Whats the end result either way?
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  6. #6
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    Stoned,
    Imagine a mean and gnarly C professor that just handed you back that function and told you... "Any elementary student could do this. Show me how you swap pointers! "

    I've literally been at this for DAYS on this one ****ing algorithm. I am ready to throw in the towel.
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  7. #7
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Code:
    void Swap( struct node* pos1, struct node* pos2)
    {
    struct node temp;
       if(pos1 != pos2)
      {
           temp.prev=pos1->prev;
           temp.next=pos1->next;
           pos1->prev=pos2->prev;
           pos1->next=pos2->next;
           pos2->prev=temp.prev;
           pos2->next=temp.next;
      }
    }
    pointers swopped
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by mlupo
    Sorry guys, neither works.

    I can't swap the values. I have to move the pointers.

    Pos2 is before Pos1.
    Well then you didn't do it right, because that does swap two nodes in a list.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    Stoned, thanks for your patience.

    I did try that algorithem many times. Something's amiss still. Must be something else in my code.

    What happens is that if I swap first and last nodes in the list, the first node is correct, but the last node is not swapped with the first node.

    interesting to say the least. I'm using the example you gave me though. I'll hand it in like that. I'll likely get the back of my hand slapped because I suck at C. But that's better than ...well, I guess I can't think of anything better than that at this point. HAHA

    Thanks again,
    Mike
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  10. #10
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    oops forgot about end nodes. check pointers for NULL. If NULL we have end node and need to mirror pointers. ie. prev=next and next=prev. you'll get the idea.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  11. #11
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    Hey Stoned,
    Also, I tested the algorithm in my driver. In the case where the the two nodes swapped are not end nodes, it essentially removed the nodes between P2 and P1.

    where 3 = P2, 7=P1
    1 2 3 4 5 6 7 8 9

    resulted in something like
    1 2 3 8 9

    I guess the nodes that are swapped are somewhere else in memory lost forever. but I assume that they're
    7 5 6 4

    Interesting... I think it's going to take 8 steps to perform the swap. So it seems that two pointer assignments are missing.
    I'm looking at it on the whiteboard now...but I get confused, even after a good nights sleep. Must be all the skunky rope I smoked as a kid.


    Mike
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  4. doubly linked list error.
    By noob2c in forum C++ Programming
    Replies: 12
    Last Post: 09-01-2003, 11:49 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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