Swap nodes (with pointers) on doubly circular linked list

  c++, circular-list, doubly-linked-list, linked-list

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

Source: Windows Questions C++

LEAVE A COMMENT