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.
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
Not adjacent case
You can make up a similar rule for the not adjacent case as well:
[W] - [A] - [X] - ... - [Y] - [B] - [Z]
A->prev = W;
A->next = X;
B->prev = Y;
B->next = Z;
Swap A with B:
[W] - [B] - [X] - ... - [Y] - [A] - [Z]
A->prev = Y;
A->next = Z;
B->prev = W;
B->next = X;
A B A B
prev W Y => prev Y W
next X Z next Z X
W Y --\ Y W
X Z --/ Z X
0 1 --\ 1 0
2 3 --/ 3 2
0,1,2,3 -> 1,0,3,2
Pointers towards the nodes
Because we are dealing with linked lists, it is not enough to change the pointers in the particular nodes. We have to update the pointers that points to our nodes that we want to swap. This pointers are located in the neighbourhood of the swapable objects.
Notice, that the pointers that are located in the nodes that our pointers points to are always pointing to ourselves.
A->prev->next = A
A->next->prev = A
So after you update the pointers according to the association rule, you only have to point the outer pointers to the given node, and you are done! Just make sure, that the neighbour exists of course.
You need to also check if node A is linked before node B. If not, you need to swap the two parameters. Thanks kralyk for the heads up.
This is enough information to write the necessary functions that do the swapping.
Swapping function and its helper functions
int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}
Working program for presentation
The optput of the following program:
Initial state: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [2]: [2]-[1]-[3]-[4]
[1] <-> [2]: [1]-[2]-[3]-[4]
[2] <-> [1]: [2]-[1]-[3]-[4]
[2] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [3]: [3]-[2]-[1]-[4]
[1] <-> [3]: [1]-[2]-[3]-[4]
[3] <-> [1]: [3]-[2]-[1]-[4]
[3] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [4]: [4]-[2]-[3]-[1]
[1] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [1]: [4]-[2]-[3]-[1]
[4] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [3]: [1]-[3]-[2]-[4]
[2] <-> [3]: [1]-[2]-[3]-[4]
[3] <-> [2]: [1]-[3]-[2]-[4]
[3] <-> [2]: [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [4]: [1]-[4]-[3]-[2]
[2] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [2]: [1]-[4]-[3]-[2]
[4] <-> [2]: [1]-[2]-[3]-[4]
--------------------------------
[3] <-> [4]: [1]-[2]-[4]-[3]
[3] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [3]: [1]-[2]-[4]-[3]
[4] <-> [3]: [1]-[2]-[3]-[4]
You can run the code in a second, by following this link:
http://codepad.org/UHcmmag1
Updated link with the corrected swapping function: http://codepad.org/LbRYjvPr
#include <stdio.h>
#include <stdlib.h>
typedef struct node_v {
int id;
struct node_v* prev;
struct node_v* next;
} Node_v;
typedef Node_v* Node;
void print(Node node) {
while (node->prev != NULL)
node = node->prev;
printf(" [%d]",node->id);
while (node->next != NULL) {
node = node->next;
printf("-[%d]",node->id);
}
printf("\n");
}
void connect(Node first,Node second) {
first->next = second;
second->prev = first;
}
Node createNode(int id) {
Node node = (Node)malloc(sizeof(Node_v));
node->id = id;
node->prev = NULL;
node->next = NULL;
return node;
}
int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}
int main() {
Node n1 = createNode(1);
Node n2 = createNode(2);
Node n3 = createNode(3);
Node n4 = createNode(4);
connect(n1,n2);
connect(n2,n3);
connect(n3,n4);
printf("\nInitial state:");
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [2]: ");
swap(n1, n2);
print(n1);
printf("[1] <-> [2]: ");
swap(n1, n2);
print(n1);
printf("[2] <-> [1]: ");
swap(n2, n1);
print(n1);
printf("[2] <-> [1]: ");
swap(n2, n1);
print(n1);
printf("--------------------------------\n");
printf("[1] <-> [3]: ");
swap(n1, n3);
print(n2);
printf("[1] <-> [3]: ");
swap(n1, n3);
print(n2);
printf("[3] <-> [1]: ");
swap(n3, n1);
print(n2);
printf("[3] <-> [1]: ");
swap(n3, n1);
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [4]: ");
swap(n1, n4);
print(n3);
printf("[1] <-> [4]: ");
swap(n1, n4);
print(n3);
printf("[4] <-> [1]: ");
swap(n4, n1);
print(n3);
printf("[4] <-> [1]: ");
swap(n4, n1);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [3]: ");
swap(n2, n3);
print(n3);
printf("[2] <-> [3]: ");
swap(n2, n3);
print(n3);
printf("[3] <-> [2]: ");
swap(n3, n2);
print(n3);
printf("[3] <-> [2]: ");
swap(n3, n2);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [4]: ");
swap(n2, n4);
print(n3);
printf("[2] <-> [4]: ");
swap(n2, n4);
print(n3);
printf("[4] <-> [2]: ");
swap(n4, n2);
print(n3);
printf("[4] <-> [2]: ");
swap(n4, n2);
print(n3);
printf("--------------------------------\n");
printf("[3] <-> [4]: ");
swap(n3, n4);
print(n4);
printf("[3] <-> [4]: ");
swap(n3, n4);
print(n4);
printf("[4] <-> [3]: ");
swap(n4, n3);
print(n4);
printf("[4] <-> [3]: ");
swap(n4, n3);
print(n4);
printf("--------------------------------\n");
return 0;
}
char *
is clearly faster than swapping 4struct s_node *
s.