## 2010-01-31

### How to swap two nodes in a doubly linked list

This blog post gives example C code how to swap two elements (nodes, items) of a doubly linked list. The code works for both circular and non-circular lists, even if the two arguments are the same, or if they are adjacent in the list. (It is surprisingly complicated to give a correct and elegant solution.)

```#include <stdlib.h>  /* NULL */

typedef int node_data_t;  /* can be any other type as well */

struct node {
struct node* prev;
struct node* next;
node_data_t data;
};

/** If node1 and node2 are non-NULL members of a doubly-linked list
* (circular or not), swap their data fields.
*/
void swap_data(struct node* node1, struct node* node2) {
node_data_t temp_data = node1->data;
node1->data = node2->data;
node2->data = temp_data;
}

/** If node1 and node2 are non-NULL members of a doubly-linked list
* (circular or not), swap their data fields. If node1 or node2 is the head
* of the non-circular list, return the new head.
*/
struct node* swap(struct node* node1, struct node* node2) {
struct node* temp;
temp = node1->next;
node1->next = node2->next;
node2->next = temp;
if (node1->next != NULL)
node1->next->prev = node1;
if (node2->next != NULL)
node2->next->prev = node2;
temp = node1->prev;
node1->prev = node2->prev;
node2->prev = temp;
if (node1->prev != NULL)
node1->prev->next = node1;
if (node2->prev == NULL)
return node2;
node2->prev->next = node2;
return node1;
}```

swap_data is simpler, and it's also faster if the data is small (i.e. at most 2 pointers). However, swap_data cannot be used when there are external pointers inside the data.

thijs said...

if node1 and node2 are directly linked, e.g. when node1->next == node2 then

temp = node1->next;
node1->next = node2->next;
node2->next = temp;

will result in

temp == node2
and thus
node2->next == node2

i.e. node 2 linking to itself!

pts said...

@thijs: What you write about node2 is true, but swap still works correctly, because node1->prev->next = node1; later will change it, so at the end node2->next will point to node1, as expected.

thijs said...

Ah I see, you're right!

Arg pointers...