algorithm - Swap items in doubly-linked list by their indices in the backing array

Question

I have an array of objects of the following type:

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

Some of the nodes participate in a doubly-linked list, with _pData!=nullptr for such nodes. There is also a dummy head node with _pNext pointing to the beginning of the list, and _pPrev pointing to the end. The list starts with containing only this head node, and it should be never removed from the list.

The doubly-linked list is backed by an array, with initial size equal to the maximum number of nodes in the list.

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

Now I want to perform the following operation on this data structure: given 2 indices i and j to the _nodes array, swap the nodes in the array, but preserve their positions in the doubly-linked list. This operation needs updating _nodes[i]._pPrev->_pNext, _nodes[i]._pNext->_pPrev and the same for node j.

One problem is the corner cases when nodes i and j are next to each other. Another problem is that the naive code involves a lot of ifs (to check for _pData==nullptr for each node and handle the 3 cases differently, and to check whether the nodes are next to each other), thus becoming inefficient.

How to do it efficiently?

Here is what I have so far in 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);

Answer 1

• The node contents of two nodes can be swapped, without changing their meaning; only their addresses will change
• since the addresses have changed, all references to the two nodes must change, too, including pointers inside the nodes that happen to point to one of the two nodes.

Here is an illustration of the swap first & fixup later (TM) method. Its major feat is that it avoids all the corner cases. It does assume a well-formed LL , and it ignores the "in_use" condition (which IMHO is orthogonal to the LL-swap-problem)

Note I did a bit of renaming, added test data, and converted to Pure C.

---

EDITED (now it actually works!)

---

#include <stdio.h>

struct Node {
    struct Node *prev, *next;
    // double *_pData;
    int val;
        };

#define MAXN 5
struct Example {
    struct Node head;
    struct Node nodes[MAXN];
        };

        /* sample data */
struct Example example = {
        { &example.nodes[4] , &example.nodes[0] , -1} // Head
        ,{ { &example.head , &example.nodes[1] , 0}
        , { &example.nodes[0] , &example.nodes[2] , 1}
        , { &example.nodes[1] , &example.nodes[3] , 2}
        , { &example.nodes[2] , &example.nodes[4] , 3}
        , { &example.nodes[3] , &example.head , 4}
        }
        };

void swapit( unsigned one, unsigned two)
{
struct Node tmp, *ptr1, *ptr2;
        /* *unique* array of pointers-to pointer
         * to fixup all the references to the two moved nodes
         */
struct Node **fixlist[8];
unsigned nfix = 0;
unsigned ifix;

        /* Ugly macro to add entries to the list of fixups */

#define add_fixup(pp) fixlist[nfix++] = (pp)

ptr1 = &example.nodes[one];
ptr2 = &example.nodes[two];

        /* Add pointers to some of the 8 possible pointers to the fixup-array.
        ** If the {prev,next} pointers do not point to {ptr1,ptr2}
        ** we do NOT need to fix them up.
        */
if (ptr1->next == ptr2) add_fixup(&ptr2->next); // need &ptr2->next here (instead of ptr1)
else    add_fixup(&ptr1->next->prev);
if (ptr1->prev == ptr2) add_fixup(&ptr2->prev); // , because pointer swap takes place AFTER the object swap
else    add_fixup(&ptr1->prev->next);
if (ptr2->next == ptr1) add_fixup(&ptr1->next);
else    add_fixup(&ptr2->next->prev);
if (ptr2->prev == ptr1) add_fixup(&ptr1->prev);
else    add_fixup(&ptr2->prev->next);

fprintf(stderr,"Nfix=%u
", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p
", fixlist[ifix], *fixlist[ifix]);
        }

        /* Perform the rough swap */
tmp = example.nodes[one];
example.nodes[one] = example.nodes[two];
example.nodes[two] = tmp;

        /* Fixup the pointers, but only if they happen to point at one of the two nodes */
for(ifix=0; ifix < nfix; ifix++) {
        if (*fixlist[ifix] == ptr1) *fixlist[ifix] = ptr2;
        else *fixlist[ifix] = ptr1;
        }
}

void dumpit(char *msg)
{
struct Node *ptr;
int i;

printf("%s
", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %d
", ptr, ptr->prev, ptr->next, ptr->val);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %d
", i, ptr, ptr->prev, ptr->next, ptr->val);
        }
}

int main(void)
{
dumpit("Original");

swapit(1,2);
dumpit("After swap(1,2)");

swapit(0,1);
dumpit("After swap(0,1)");

swapit(0,2);
dumpit("After swap(0,2)");

swapit(0,4);
dumpit("After swap(0,4)");

return 0;
}

---

To illustrate the fact that we can ignore the in_use condition, here is a new version, with two double linked lists present in the same array. This could be an in_use list and ad free list.

---

#include <stdio.h>

struct Node {
    struct Node *prev, *next;
    // double *_pData;
    // int val;
    char * payload;
        };

#define MAXN 8
struct Example {
    struct Node head;
    struct Node free; /* freelist */
    struct Node nodes[MAXN];
        };

        /* sample data */
struct Example example = {
        { &example.nodes[5] , &example.nodes[0] , ""} /* Head */
        , { &example.nodes[6] , &example.nodes[2] , ""} /* freelist */

/* 0 */ ,{ { &example.head , &example.nodes[1] , "zero"}
        , { &example.nodes[0] , &example.nodes[3] , "one"}
        , { &example.free , &example.nodes[6] , NULL }
        , { &example.nodes[1] , &example.nodes[4] , "two"}
/* 4 */ , { &example.nodes[3] , &example.nodes[5] , "three"}
        , { &example.nodes[4] , &example.head , "four"}
        , { &example.nodes[2] , &example.free , NULL}
        , { &example.nodes[7] , &example.nodes[7] , "OMG"} /* self referenced */
          }
        };

void swapit( unsigned one, unsigned two)
{
struct Node tmp, *ptr1, *ptr2;
        /* *unique* array of pointers-to pointer
         * to fixup all the references to the two moved nodes
         */
struct Node **fixlist[4];
unsigned nfix = 0;
unsigned ifix;

        /* Ugly macro to add entries to the list of fixups */

#define add_fixup(pp) fixlist[nfix++] = (pp)

ptr1 = &example.nodes[one];
ptr2 = &example.nodes[two];

        /* Add pointers to some of the 4 possible pointers to the fixup-array.
        ** If the {prev,next} pointers do not point to {ptr1,ptr2}
        ** we do NOT need to fix them up.
        ** Note: we do not need the tests (.payload == NULL) if the linked lists
        ** are disjunct (such as: a free list and an active list)
        */
if (1||ptr1->payload) { /* This is on purpose: always True */
        if (ptr1->next == ptr2) add_fixup(&ptr2->next); // need &ptr2->next here (instead of ptr1)
        else    add_fixup(&ptr1->next->prev);
        if (ptr1->prev == ptr2) add_fixup(&ptr2->prev); // , because pointer swap takes place AFTER the object swap
        else    add_fixup(&ptr1->prev->next);
        }
if (1||ptr2->payload) { /* Ditto */
        if (ptr2->next == ptr1) add_fixup(&ptr1->next);
        else    add_fixup(&ptr2->next->prev);
        if (ptr2->prev == ptr1) add_fixup(&ptr1->prev);
        else    add_fixup(&ptr2->prev->next);
        }

fprintf(stderr,"Nfix=%u
", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p
", fixlist[ifix], *fixlist[ifix]);
        }

        /* Perform the rough swap */
tmp = example.nodes[one];
example.nodes[one] = example.nodes[two];
example.nodes[two] = tmp;

        /* Fixup the pointers, but only if they happen to point at one of the two nodes */
for(ifix=0; ifix < nfix; ifix++) {
        if (*fixlist[ifix] == ptr1) *fixlist[ifix] = ptr2;
        else *fixlist[ifix] = ptr1;
        }
}

void dumpit(char *msg)
{
struct Node *ptr;
int i;

printf("%s
", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %s
", ptr, ptr->prev, ptr->next, ptr->payload);
ptr = &example.free;
printf("Free: %p {%p,%p} %s
", ptr, ptr->prev, ptr->next, ptr->payload);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %s
", i, ptr, ptr->prev, ptr->next, ptr->payload);
        }
}

int main(void)
{
dumpit("Original");

swapit(1,2); /* these are on different lists */
dumpit("After swap(1,2)");

swapit(0,1);
dumpit("After swap(0,1)");

swapit(0,2);
dumpit("After swap(0,2)");

swapit(0,4);
dumpit("After swap(0,4)");

swapit(2,5); /* these are on different lists */
dumpit("After swap(2,5)");

return 0;
}