У меня есть массив объектов следующего типа:

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

Некоторые из узлов участвуют в двусвязном списке с_pData!=nullptr для таких узлов. Также есть фиктивный головной узел с_pNext указывая на начало списка, и_pPrev указывая на конец. Список начинается с содержания только этого головного узла, и его никогда не следует удалять из списка.

Двусвязный список поддерживается массивом, начальный размер которого равен максимальному количеству узлов в списке.

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

Теперь я хочу выполнить следующую операцию над этой структурой данных: дано 2 индексаi а такжеj к_nodes массив, меняйте местами узлы в массиве, но сохраняйте их позиции в двусвязном списке. Эта операция требует обновления_nodes[i]._pPrev->_pNext, _nodes[i]._pNext->_pPrev и то же самое для узлаj.

Одна проблема - это угловые случаи, когда узлыi а такжеj рядом друг с другом. Другая проблема заключается в том, что наивный код включает в себя многоifs (чтобы проверить_pData==nullptr для каждого узла и обрабатывать 3 случая по-разному, а также проверять, находятся ли узлы рядом друг с другом), тем самым становясь неэффективными.

Как это сделать эффективно?

Вот что я имею в C ++:

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