Doubly Linked List node swapping issue

Question

I'm trying to reorder my DLL by an int value within the node struct (age). It works when i access the int directly, but i'm trying to swap entire nodes so that I won't have to swap every variable in the struct when the list gets reordered.

void DLL::ReOrg(node* head, int DLL_Size)
{

node* temp = head;
int holder;


for(int j = 0; j < DLL_Size; j++)
{

        while(temp != NULL)
        {

                    if (temp->next != NULL && (temp->age < temp->next->age) )
                    {
                        holder = temp->age;

                        temp->age = temp->next->age;
                        temp->next->age = holder;
                    }
                    else
                            temp = temp->next;//increment node
            }
            temp = head;

}


}

This works but when i try to do something like:

node* holder;

...

holder = temp;
temp = temp->next;
temp->next = holder;

My program will compile and run a blank screen. Any guidance would be appreciated. I'm guessing it would be easier just to swap all my variables (there aren't many), but I wanted to make my code cleaner. thanks.

Answer 1

It's because you don't actually re-link the nodes, so you get an infinite loop. You need to change the next link of the previous node as well as the prev link on the next-next node.

---

If your list is doubly-linked, and you have a previous pointer and a next pointer, then you can do something like this:

node* next = temp->next;

// Fix the links of the previous node, and the next-next node
if (temp->prev)
    temp->prev->next = next;

if (next->next)
    next->next->prev = temp;

// Relink the two nodes that should be swapped
temp->next = next->next;
next->next = temp;

next->prev = temp->prev;
temp->prev = next;