How do I swap elements in a List?

Question

I am trying to learn about data structures and algorithms on my own. I wrote my own double-linked list in C and now I want to write some algorithms to perform on the list. What is the preferred way to swap list items? Is it better to swap the content or to rearrange the pointers which point to the next and previous list item?

Answer 1

Rearrange the pointers. Swapping the data items can have side effects. In particular, you may have stored a reference to a node somewhere outside of the function, and usually when you rearrange the order of nodes in a list, you don't want people holding a reference to a node to suddenly find that the node points to new data. That's because generally the important, identifying characteristic of a node is the data it points to not its position in the list.

Answer 2

The canonical swap is done via pointer rearranging, has no side effects and is of course faster:

void swap (node *a, node *b) {
    node *tmp;

    tmp = a;
    a = b;
    b = tmp;
}

Answer 3

Depending on the kind of content being stored in the elements of the linked list, swapping the actual content of the element would be tricky (think about a linked list of different length strings for instance) so therefore it's easier to swap the pointers which point to the next and previous list items.

Answer 4

Depends on how you've allocated the content.

If you're storing the pointer to the content, then switching the content isn't a big deal. If you have a big structure that's part of your node, then switching the pointers could be more efficient than copying the whole content.

Answer 5

I tend to side with what most people have already said. A bit of background will probably help: swapping pointers is guaranteed to work whereas swapping objects may not always be as simple as it looks. Think of temporaries that may/will be created and exceptions (and I mean in general and not a C++ language feature way) can occur and actually leave your container (list) in an undesirable state. Look for invariants in your container -- which is that a swap should leave the list size intact as well as the elements intact and design thereon.