哪種數據結構最適合交換操作？

Question

哪個數據結構最適合存儲應該頻繁交換的元素？鏈接列表和數組被命名爲這種操作的最愛，但我想知道推理...

Answer 1

我認爲正確的答案是'好吧，這取決於，但通常一個數組（矢量）是要走的路;如果我們談論鏈接列表，至少應該是一個雙鏈表。

假設我們有一些Singly Linked List：

...->$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）地址。

你可以，當然，使用Doubly Linked List代替：

...$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; 

當然，在理論上這可以比以前的方法要慢（如果這個「數據值」是如此巨大，複製它需要更多的時間比將指針複製三次）。但在實踐中，它指向存儲在數組和鏈表中的這樣龐大的數據。