c++ - 更改链表中元素的顺序

Question

我正在尝试使用简单的链表:

struct index
{
   struct index* next_element;
   int data;
   struct index* previous_element;
} 

在性能方面更改元素顺序的最佳方法是什么？ 例如，我有 1 2 3 4 5 6 7 8，我需要 1 4 2 3 5 6 7 8。

Answer 1

一般情况下很难说。似乎您想将元素 4 移动到元素 1 之后。您是否有两者的 index*？或者你只知道第四个元素必须移动两个位置？这显然会影响您必须执行的列表遍历的数量。

通常，为了获得最大效率，您需要一个函数

void list_remove_unsafe_(index* i) {
  // These two have to change (minimum needed)
  i->previous_element->next_element = i->next_element;
  i->next_element->previous_element-> = i->previous_element;
  // We leave i itself unchanged (dangling)
}

和后续行动

void list_insert_unsafe_(index* after, index* i) {
  // These four have to change (minimum needed)
  index* before = after->next_element;
  i->previous_element = after;
  i->next_element = before;
  before->previous_element = i;
  after->next_element = i;
}

这些操作是不安全的，因为它们暂时使列表处于损坏状态并做出很多假设(例如，不检查列表的开始/结束)。那些需要特殊处理。对于基本操作，这 6 次指针写入是最低限度。