Ich habe ein Array von Objekten des folgenden Typs:

struct Node {
    Node *_pPrev, *_pNext;
    double *_pData;
};

Einige der Knoten nehmen an einer doppelt verknüpften Liste teil, mit_pData!=nullptr für solche Knoten. Es gibt auch einen Dummy-Kopfknoten mit_pNext auf den Anfang der Liste zeigen und_pPrev zeigt zum Ende. Die Liste beginnt mit dem Enthalten nur dieses Kopfknotens und sollte niemals aus der Liste entfernt werden.

Die doppelt verknüpfte Liste wird von einem Array unterstützt, dessen Anfangsgröße der maximalen Anzahl von Knoten in der Liste entspricht.

struct Example {
    Node _nodes[MAXN];
    Node _head;
};

Nun möchte ich die folgende Operation für diese Datenstruktur ausführen: gegeben 2 Indizesi undj zum_nodes Array, vertauschen Sie die Knoten im Array, behalten Sie jedoch ihre Position in der doppelt verknüpften Liste bei. Diese Operation muss aktualisiert werden_nodes[i]._pPrev->_pNext, _nodes[i]._pNext->_pPrev und das gleiche für Knotenj.

Ein Problem ist die Ecke Fälle, wenn Knoteni undj stehen nebeneinander. Ein weiteres Problem ist, dass der naive Code eine Menge von @ beinhaltifs (um nach @ zu such_pData==nullptr für jeden Knoten und behandeln Sie die 3 Fälle unterschiedlich und prüfen Sie, ob die Knoten nebeneinander liegen.

Wie mache ich es effizient?

Hier ist, was ich bisher in C ++ habe:

assert(i!=j);
Node &chI = _nodes[i];
Node &chJ = _nodes[j];
switch (((chI._pData == nullptr) ? 0 : 1) | ((chJ._pData == nullptr) ? 0 : 2)) {
case 3:
    if (chI._pNext == &chJ) {
        chI._pPrev->_pNext = &chJ;
        chJ._pNext->_pPrev = &chI;
        chI._pNext = &chI;
        chJ._pPrev = &chJ;
    }
    else if (chJ._pNext == &chI) {
        chJ._pPrev->_pNext = &chI;
        chI._pNext->_pPrev = &chJ;
        chJ._pNext = &chJ;
        chI._pPrev = &chI;
    } else {
        chI._pNext->_pPrev = &chJ;
        chJ._pNext->_pPrev = &chI;
        chI._pPrev->_pNext = &chJ;
        chJ._pPrev->_pNext = &chI;
    }
    break;
case 2:
    chJ._pNext->_pPrev = &chI;
    chJ._pPrev->_pNext = &chI;
    break;
case 1:
    chI._pNext->_pPrev = &chJ;
    chI._pPrev->_pNext = &chJ;
    break;
default:
    return; // no need to swap because both are not in the doubly-linked list
}
std::swap(chI, chJ);