Swap nodes (with pointers) on doubly circular linked list

Question

I am trying to write a doubly circular linked list, but I got somewhat stuck in swapping nodes. It's working fine for any node except the head node. I tried adding a check if node1 is the head without a luck. Where am I doing wrong ?

Well, I stated earlier but for any other node except head the swap is working just fine, I'm sure this is the key to the problem here, but I cannot see it so far. Appreciate any help.

updateNode(*node) simply rearrange prev->next and next->prev accordingly.

Update: Currently if node1 is the head node, it swaps node2 with head->next. 1 2 3 4 5 6 becomes 1 6 2 3 4 5.

template<class T>
void LinkedList<T>::updateNode(Node<T> *node) {
    node->prev->next = node;
    node->next->prev = node;
}


template<class T>
void LinkedList<T>::swap(Node<T> *node1, Node<T> *node2) {
    if (!contains(node1) or !contains(node2)) 
        return;

    if (node1 == node2)
        return;
    else if (node2->next == node1 && node1->prev == node2) {
        Node<T> *temp = node1;
        node1 = node2;
        node2 = temp;
    }

    Node<T> *n1_prev = node1->prev;
    Node<T> *n2_prev = node2->prev;
    Node<T> *n1_next = node1->next;
    Node<T> *n2_next = node2->next;

    if (node1 == head && node2 == head->prev) {
        head->prev = node1;
        head = node2;
        head->next = n1_next;
        head->prev->prev = n2_prev;
    }
    else if (( node1->next == node2 && node2->prev == node1 ) || ( node1->prev == node2 && node2->next == node1 )) {
        node1->prev = n1_next;
        node2->prev = n1_prev;
        node1->next = n2_next;
        node2->next = n2_prev;
    }
    else {
        node1->prev = n2_prev;
        node2->prev = n1_prev;
        node1->next = n2_next;
        node2->next = n1_next;
    }

    updateNode(node1);
    updateNode(node2);
}

Answer 1

Some of the problems include:

• With head->prev = node1 the node reference node1 is made to refer to itself, as at that moment head and node1 reference the same node.

• head should be changed also in other cases: it should change when it is equal to either node1 or node2 without any other condition. And then it should just reference the other of the two.

• The swap logic should not be any different when one of the nodes is the head node. The rewiring for the swap should be exactly the same. It is just (like mentioned above) that if one of them is the head, the head reference should be updated to refer to the other node of the two.

• In case the list consists only of two nodes (the ones to be swapped) then nothing needs to be rewired. Only the head reference should change.

Some conditions could be simplified, as we may assume that the list is consistent. So when node2->next == node1 we may silently assume that node1->prev == node2, ...etc.

So here is an update of your code:

template<class T>
void LinkedList<T>::swap(Node<T> *node1, Node<T> *node2) {
    if (!contains(node1) or !contains(node2)) 
        return;

    if (node1 == node2)
        return;
    
    if (node2->next == node1) {
        Node<T> *temp = node1;
        node1 = node2;
        node2 = temp;
    }

    if (node2->next != node1) { // More than 2 nodes in the list
        Node<T> *n1_prev = node1->prev;
        Node<T> *n2_next = node2->next;

        if (node1->next == node2) {
            node1->prev = node1->next;
            node2->next = node2->prev;
        } else {
            node1->prev = node2->prev;
            node2->next = node1->next;
        }
        node2->prev = n1_prev;
        node1->next = n2_next;

        updateNode(node1);
        updateNode(node2);
    }
    // If head was swapped, it should reference the other one now
    if (head == node1)
        head = node2;
    else if (head == node2)
        head = node1;
}