c++ - Is anything wrong with my doubly linked list swap function?

Question

I have a function which is used to swap 2 nodes:

void swap(Node<T>* a, Node<T>* b) {
    if(a->m_prev)
        a->m_prev->m_next = b;
    if(b->m_prev)
        b->m_prev->m_next = a;
    if(a->m_next)
        a->m_next->m_prev = b;
    if(b->m_next)
        b->m_next->m_prev = a;

    Node<T>* temp;
    temp = a->m_prev;
    a->m_prev = b->m_prev;    
    b->m_prev = temp;
    temp = a->m_next;
    a->m_next = b->m_next;    
    b->m_next = temp;
}

However when used with my recursive selection sort:

void selectionSort(Node<T>* head) {
    if(next(head) == NULL) {
        return;
    }
    Node<T>* minimum = min(head);

    swap(head,minimum);

    selectionSort(minimum->m_next);
}

About half way through the sort, it sets one of my nodes' next pointer to NULL, then when I print my list, it is sorted up to that value correctly, but the rest is missing because a pointer was incorrectly set to NULL.

I checked and:

My initial list is correct and has no incorrectly connected nodes.

My swap function is only called with non-null valid nodes.

So I blame the swap function. Is there anything wrong with it?

Answer 1

I think the problem occurs when a is adjacent to b in the list. For example, if b->prev points to a (meaning a is just before b in the list) then the line

b->prev->next = a; 

is equivalent to

a->next = a;

which clearly isn't what you want.

Here are some tips on how to approach the problem of swapping nodes in a doubly linked list. The nodes to be swapped, A and B, will be referred to as internal nodes. Other nodes in the list are external nodes. The external nodes that are near A and/or B shall be designated W, X, Y, and Z. External nodes far from A and B shall be designated with ellipsis. When swapping the internal nodes, there will be 2, 3, or 4 external nodes involved in the swap, as shown below

case 1: widely separated (four external nodes)      ... W A X ... Y B Z ...
case 2: separated by one (three external nodes)     ... W A X B Z ...
case 3: adjacent (two external nodes, A first)      ... W A B Z ...
case 4: adjacent (two external nodes, B first)      ... W B A Z ...

It should be possible to handle the first two cases with a single set of code (the fact that X is connected to both A and B in case 2 should have no effect on the swap implementation). The last two cases can be handled by swapping the function arguments if B is ahead of A, so that variable a always points to the first node and variable b always points to the second node. Thus, the four cases are reduced to two cases, modeled as

cases 1&2:   ... W A X ... Y B Z ...
cases 3&4:   ... W A B Z ...

In cases 1&2 there are 4 pointers on the internal nodes that need to be updated, and 4 pointers on the external nodes that need to be updated. In cases 3&4, there are 4 pointers on the internal nodes that need to be updated, but only 2 pointers on the external nodes that need to be updated.

I suggest sitting down with a pencil and paper and first identifying the pointers that need to be updated, and then determine what you want the final value of each pointer to be. Knowing that, the coding part should be easy.