Swaping elements doubly linked list

Question

I implement selecting sort and I need to swap elements. I have doubly linked list with previous and next links. And link to the first and last element in List I always need to swap some node b with first node toStartFrom

public void Swap(Node toStartFrom, Node b) {
        Boolean NextToEachOther = (toStartFrom.next == b);
        toStartFrom.next = b.next;
        b.previous = toStartFrom.previous;
        if (NextToEachOther) {
            toStartFrom.previous = b;
            b.next = toStartFrom;
        } else {
            toStartFrom.previous = b.previous;
            b.next = toStartFrom.next;
        }
    }

    public void display() {
        Node current = first;
        while (current != null) {
            ...printing...
            current = current.next;
        }
    }

But it doesn't work. No errors just doesn't sort in right order. And not diplays any elements after sort after toStartFrom node.

What did you observe when you stepped through your code in a debugger on a simple data-set? — Oliver Charlesworth
Also, for a doubly linked-list where one of the elements is guaranteed to be the head, you will need to update 6 references. Draw a picture to see why. — Oliver Charlesworth
In debuging it's Ok they are swaped in debuging maybe I have a problem with displaying. — Nikita
You mean it works properly when you run it in the debugger, but not when you run it for real? Or do you mean that it just doesn't crash? — Oliver Charlesworth

Akron Akron · Accepted Answer · 2011-10-26T23:31:07

You need to also update the nodes that are next to the 2 being swapped

For instance, consider this list:

first -> a -> b -> c

If you wish to swap first and b then you must also update a's and c's next and prev references.

Edit: This code should be placed before your code that does the swap and right after the Boolean declaration

Edit2: Also, if you have refences to the head/tail of the list, you need to update those too. I don't see that you referenced a head or tail anywhere in your code though.

if(toStartFrom.prev != null)
{
   toStartFrom.prev.next = b;
}
if(toStartFrom.next != b) // Equivalent to NextToEachOther
{
   toStartFrom.next.prev = b;
}
if(b.next != null)
{
   b.next.prev = toStartFrom;
}
if(b.prev != toStartFrom)  // Equivalent to NextToEachOther
{
   b.prev.next = toStartFrom
}

Swaping elements doubly linked list

1 Answers