Thread: 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;

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;

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.

Sorry guys, neither works.

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

Pos2 is before Pos1.

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?

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.

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

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.

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

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.

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