双链表节点就地重新排序以确保内存连续性

Question

我正在开发一个程序，该程序处理在有界内存区域内分配的双向链表：

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

我想编写一个

swap(Node* block, std::size_t i, std::size_t j)

函数，交换两个节点在内存中的位置，但确保链表本身的遍历顺序保持不变。

例如，

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

关于如何正确实施这一点有什么想法吗？

我有一个初步的实现，但这似乎并没有考虑到所有可能的边缘情况。例如，当索引 i 处的节点是索引 j 处节点的后继或前驱（即它们在链表中相邻，不一定是内存本身）时，它会失败。

这是实现：

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];
  }
}

Answer 1

当要交换的节点在列表顺序中相邻时，即

array[i].next == &array[j]

或反之亦然，那么在内存交换之后，我们将有

array[j].next == &array[j]

或类似的自引用。在处理这种情况时，您的代码显然会带来严重破坏。

您必须检测这种边界情况并进行相应处理。例如，如果可以这样做：

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

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

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

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

请注意，当列表中的头/尾节点参与这样的交换时，您将需要管理指向它们的指针。此外，如果您具有插入/删除节点的功能，则需要管理未使用的节点列表，并在从逻辑列表中逻辑插入或删除节点时从该列表中获取并返回给该列表。