CODEWITHSUNDEEP
cswapdoubly-linked-list
Eutherpy
Eutherpy

Reputation: 4571

Sorting doubly linked list by swapping nodes

I was implementing Huffman's algorithm and for that I used a doubly linked list. The implementation demands sorting the list, but simply swapping data isn't enough - I need to swap entire nodes. However, this is turning out to be a bit more complicated than I anticipated.

I used this variation of selection sort, but it causes an access violation error. I'm assuming it's because I'm trying to access some NULL pointer, which the two conditions were supposed to prevent.

Any help or suggestion would be appreciated.

void sortiraj()
{
    Node *curr = top, *nxt;
    for (int i = 0; i < num - 1; ++i)
    {
        nxt = curr->next;
        for (int j = i + 1; j < num; ++j)
        {
            if (curr->prob > nxt->prob)
            {
                //swap prev
                if (curr != top)
                {
                    Node *temp_prev = curr->prev;
                    curr->prev = nxt->prev;
                    nxt->prev = temp_prev;
                }

                //swap next
                if (nxt != last)
                {
                    Node *temp_next = curr->next;
                    curr->next = nxt->next;
                    nxt->next = temp_next;
                }
            }
            nxt = nxt->next;
        }
        curr = curr->next;
    }
}

Upvotes: 0

Views: 856

Answers (1)

Mido
Mido

Reputation: 665

If the current node is the TOP node, you still need to swap the previous pointers. This is because you need to indicate that the new top has it's "previous pointer" set to NULL and the old top has it's "previous pointer" set to the new top.

The same goes with the "Next pointer".

You don't need a condition to swap the previous and next flags. You instead need the conditions to indicate that the top and last nodes have been changed.

Moreover, When swapping, you can't just swap the previous pointers. This is because, it will mean that one of them will be pointing to itself. The proper way to do it would be like this

nxt->prev = curr->prev;
curr->prev = nxt;

The same thing applies when swapping the next pointer.

Upvotes: 2

Related Questions