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; }

The code above is based on the discussion at http://bytes.com/topic/c/answers/219236-double-linked-list-elements-swap

`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.

## 3 comments:

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!

@thijs: What you write about node2 is true, but

swapstill works correctly, becausenode1->prev->next = node1;later will change it, so at the endnode2->nextwill point tonode1, as expected.Ah I see, you're right!

Arg pointers...

Post a Comment