How to swap two non-consecutive nodes in a double-chained list?

Question

How to swap two non-consecutive nodes in a double-chained list?

Navigation

#1 by (3 votes)

3

I needed to swap two consecutive nodes or not in a double-chained list, but I can not. Can someone help me? I already did it on paper but it does not execute. What is the problem with the code?

void swap(no_teste* A, no_teste* B) {

    no_teste* proximoA = A->prox;
    no_teste* anteriorB = B->ant;

    A->prox = B->prox;
    B->ant = A->ant;

    A->ant = anteriorB;
    anteriorB->prox = A;
    B->prox = proximoA;
    proximoA->ant = B;

}

I get lost with this exchange of pointers, if it was simply chained list I would get it. Can anyone help me?

The last ones I tried on paper but could not even use them:

void init(no_teste* aA, no_teste* A, no_teste* bA, no_teste* aB, no_teste* B, no_teste* bB) {
    aA = A->ant;
    bA = A->prox;
    aB = B->ant;
    bB = B->prox;
}

void Disconect_Geral_Node(no_teste* aA, no_teste* A, no_teste* bA) {

    aA->prox = NULL;
    A->ant = NULL;
    A->prox = NULL;
    bA->ant = NULL;

}

void Geral_Conect(no_teste* aA, no_teste* B, no_teste* bA) {
    aA->prox = B;
    B->ant = aA;
    B->prox = bA;
    bA->ant = B;
}

c

asked by anonymous 14.12.2017 / 00:17

1 answer

What is the logic behind the trunc function? Visual Studio has shortcut to navigate to an equal file in Sublime Text, when we press CTRL + P?

score 3 · Accepted Answer

In your code the changes to B->prox and A->ant are not correct:

A->ant = anteriorB;
B->prox = proximoA;

Since the previous one of A will become B , and the next of B will become A . Also you do not need the temporary variables if you make the changes in the correct order.

As a first approach you can do this:

void swap(no_teste* A, no_teste* B) {
    A->ant->prox = B;
    B->prox->ant = A;
    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

In this version of swap I changed first before A and then next to B and therefore it was not necessary to save values in temporary variables.

This solution will not work if the exchange is at the end of the list or at the beginning of the list since A->ant or B->prox will be NULL , which will result in a segmentation fault . To solve we have to test NULL before changing:

void swap(no_teste* A, no_teste* B) {
    if (A->ant != NULL){
        A->ant->prox = B;
    }

    if (B->prox != NULL){
        B->prox->ant = A;
    }

    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

Now, even though it does not make a mistake at the beginning of the list, it will not be correct as it would be necessary to change the head of the list, something not included in the function header itself:

void swap(no_teste** lista, no_teste* A, no_teste* B) {
    if (A->ant != NULL){
        A->ant->prox = B;
    }
    else {
        *lista = B; //se A->ant é NULL, A é a cabeça e B passa agora a ser a cabeça
    }

    if (B->prox != NULL){
        B->prox->ant = A;
    }

    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

Ideone swap example

In the ideone examples I used two display functions to be easy to see that both the ant and the prox pointers are correct.

I also considered it to be a doubly linked non-circular list.