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?
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;
}