arrays - 哪种数据结构最适合交换操作？

Question

哪种数据结构最适合存储应该经常交换的元素？链表和数组都被命名为这种操作的最爱，但我想知道其中的原因......

Answer 1

我认为正确的答案是'好吧，这取决于，但通常一个数组（向量）是要走的路；如果我们谈论链表，它至少应该是一个双向链表。

假设我们有一些单链表：

...->$el1->$el2->$el3->$el4->$el5...

...并且我们引用了 $el2 和 $el4 元素（应该交换）。从技术上讲，我们需要做的是...

1) assign the address of `$el4` (or `$el3->next`) to the `$el1->next` pointer
2) assign the address of `$el2` (or cached `$el1->next`) to the `$el3->next` pointer
3) assign the value of `$el4->next` to the `$el2->next` pointer
4) assign the value of `$el2->next` to the (previously cached) `$el4->next` pointer

...就是这样，基本上是 0(1) 效率。容易吧？

这里要注意的是，没有简单的方法 (=0(1)) 可以在此处获取“先前”元素 ($el1和$el3)。两者$el4和仅$el2存储它们nexts（$el5和$el3分别）的地址。

当然，您可以改用双向链表：

...$el1<->$el2<->$el3<->$el4<->$el5...

在这里引用prev元素将和那些元素一样简单next，所以我们需要...

1-2) swap values of `$el2->prev->next` and `$el4->prev->next`,
3-4) swap values of `$el4->next`       and `$el2->next`

但是等等，还有更多！我们prev现在也必须更新指针：

5-6) swap values of `$el4->prev`       and `$el2->prev`

正如您可能已经看到的，这里有 3 个“价值交换”操作。

使用向量，它是一个单一的交换：

[$el1][$el2][$el3][$el4][$el5]

1) assign data-value of $el2 to some temp variable;
2) assign data-value of $el4 to $el2;
3) assign data-value of this temp variable to $el4;

当然，理论上这可能比以前的方法慢（如果这个“数据值”太大以至于复制它比复制指向它的指针三次需要更多时间）。但实际上它是指向存储在数组和链表中的如此庞大数据的指针。