How to swap two nodes next to each other in a circular doubly linked list?

Question

I am currently trying to swap two nodes in a circular doubly linked list. By current code:

private void swap(Card Card1, Card Card2) {

    if (Card1 == head) {
        head = Card2;
    } else if (Card2 == head) {
        head = Card1;
    } if (Card1 == tail) {
        tail = Card2;
    } else if (Card2 == tail) {
        tail = Card1;
    }

    // Swapping Card1 and Card2
    Card temp = Card1.next;
    Card1.next = Card2.next;
    Card2.next = temp;

    if (Card1.next != null) {
        Card1.next.prev = Card1;
    } if (Card2.next != null) {
        Card2.next.prev = Card2;
    }

    temp = Card1.prev;
    Card1.prev = Card2.prev;
    Card2.prev = temp;

    if (Card1.prev != null) {
        Card1.prev.next = Card1;
    } if (Card2.prev != null) {
        Card2.prev.next = Card2;
    }

    head.prev = tail;
    tail.next = head;
}

This code should swap between any two nodes in the linked list but for my application. I am just using it to swap with the next node.

public void moveCard(Card c, int p) {
       for (int i = 0; i < p; i++) {
          swap(c, c.next);
       }
}

Here I am using it to move a card across the list by p positions. Is this correct logic?

I Have been trying to debug this for so long and I cant find where it goes wrong. Any Ideas?

Answer 1

When Card2 is Card1.next then the assignment Card2.next = temp will make Card2 reference itself. This surely breaks the correct continuation of the swap.

The check for null references could be removed, as in a circular list these should never be null. I didn't see your Node class, but if you initialise those members to null there, then change it: make them self references instead, so you can guarantee that prev and next are never assigned null.

I would take a step back and extract both nodes via a separate extract function, and insert them again with a separate insertBefore function.

To avoid havoc, make sure that Card2.next is not Card1 (so in opposite order). If this is the case repeat the call with the arguments switched, so that Card1.next is Card2. But there is still a special case to deal with: if these two cards are the only members of the list, there is no way to prevent that Card2.next is Card1, so that case should be dealt with separately: it is an easy case where only head and tail should reference the other node than they currently do.

There shouldn't be much code to set tail, as there is an invariant: tail is always head.prev in a non-empty list. So you can just make that assignment at the end.

And I would also use camelCase for your variables, so card1 instead of Card1.

Here is the suggested code:

private void insertBefore(Card card, Card next) { // card is assumed not to be in list yet
    card.next = next;
    card.prev = next.prev;
    card.prev.next = card;
    card.next.prev = card;
}

private void extract(Card card) { // Does not modify its prev/next members
    card.next.prev = card.prev;
    card.prev.next = card.next;
}

private void swap(Card card1, Card card2) {
    // Deal with boundary cases:
    if (card1 == card2) return; // Nothing to do
    if (card2.next == card1) {
        if (card2.prev == card1) { // List has only 2 elements
            tail = head;
            head = head.next;
            return;
        }
        return swap(card2, card1);
    }
    // Here we are sure card2.next is not card1
    Card next2 = card2.next;
    extract(card2);
    extract(card1);
    insertBefore(card2, card1.next);
    insertBefore(card1, next2);
    // Fix head/tail references
    if (head == card1) head = card2;
    else if (head == card2) head = card1;
    tail = head.prev;
}