I am working on a program that deals with doubly linked lists that are allocated within a bounded memory region:

constexpr std::size_t numNodes = 15;
Node* block = new Node[numNodes];

I would like to write a swap(Node* block, std::size_t i, std::size_t j) function that swaps two nodes’ locations in memory, but ensures the traversal order of the linked list itself remains the same.

For example,

Before swapping indices 1 and 3:
List:  [A] -> [B] -> [C] -> [D]
Memory: 10, 20, 30, 40

After swapping indices 1 and 3:
List:  [A] -> [B] -> [C] -> [D]
Memory: 10, 40, 30, 20

Any ideas on how to correctly implement this?

I have an initial implementation, but it seems like this does not account for all possible edge cases. For example, it fails when the node at index i is a successor or predecessor of the node at index j (i.e., they are adjacent within the linked list, not necessarily memory itself).

Here is the implementation:

void swap(Node* array, int i, int j) {
  if (i == j)
    return;

  // Swap the nodes
  Node temp = array[i];
  array[i] = array[j];
  array[j] = temp;

  // Update next and prev pointers for array[i]
  if (array[i].next) {
    array[i].next->prev = &array[i];
  }
  if (array[i].prev) {
    array[i].prev->next = &array[i];
  }

  // Update next and prev pointers for array[j]
  if (array[j].next) {
    array[j].next->prev = &array[j];
  }
  if (array[j].prev) {
    array[j].prev->next = &array[j];
  }
}