Swapping Nodes in Double Linked List

Question

I'm trying to implement a function that swap two nodes of my double linked list, in order to sort the content of the current directory. But my function seems to 'delete' some elements of my list, here is the code :

void node_swap(struct s_node *left, struct s_node *right)
{
  struct s_node *tmp;

  tmp = left->prev;
  if (tmp)
   {
      tmp->next = right;
      right->prev = tmp;
   }
  else
      right->prev = NULL;

  left->prev = right;
  left->next = right->next;
  right->next = left;
  right->next->prev = left->prev;
}

I can't see what's wrong in this ?

Accepted Answer

If you write down what you want to do, you can realize a really simple and straightforward solution.

[[working code is at the end of the answer]]

For example, if you have two nodes you want to swap (say A and B), there are two possibilites according to the position of the nodes. They could be adjacent or not.

Must Read

Adjacent case

In the adjacent case, you can write:

[X] - [A] - [B] - [Y]

A->prev = X;
A->next = B;
B->prev = A;
B->next = Y;

If you swap A with B, you will end up this:

[X] - [B] - [A] - [Y]

A->prev = B;
A->next = Y;
B->prev = X;
B->next = A;

This is what you want to get. You have to rearrange the pointers to swap the two nodes A and B.

If you use a matrix form the rule will be more intuitive:

     A B               A B 
prev X A    =>    prev B X
next B Y          next Y A

Or just write the matrices alone:

X A   --\   B X
B Y   --/   Y A

Notice, that the swapping matrix rotates 90 degrees clockwise. If you index the elements in the matrix, you can make up an assotiation table:

0 1  --\  2 0
2 3  --/  3 1

So, if you store the pointers in an array, you can easily rearrange them:

0,1,2,3 -> 2,0,3,1

Swapping Nodes in Double Linked List

4 Answers

Must Read

Adjacent case

Alexander Ross