雙鏈表

Question

解釋如何使用每個項目的一個指針值np [x]而不是通常的兩個（next和prev）來實現雙向鏈表。假設所有的指針值都可以被解釋爲k位整數，並且定義np [x]爲np [x] = next [x] XOR prev [x]，k位爲「exclusive-or」ofnext [x ]和prev [x]。 （值NIL由0表示。）一定要描述訪問列表頭部所需的信息。顯示如何在這樣的列表上實現SEARCH，INSERT和DELETE操作。同時顯示如何在O（1）時間內反轉這樣的列表。

來源：CLRS Cormen第三版

PS的10.2-8：這不是一門功課的問題。我在練習/修改數據結構。

Answer 1

將指針指定爲「常規」整數。所以，你可以對它進行任何整數運算，包括xor。

對於每個節點，存儲xorValue = next^previous。

爲什麼它有幫助？
如果您從頭到尾迭代 - 您知道previous是哪裏，並且您有它的價值，那麼您可以使用next = xorValue^previous獲得下一個。
從最後到第一個迭代時適用相同的想法：previous = xorValue^next。

這是不夠，因爲你不能沒有從去年迭代到第一個或第一個到最後到達鏈表的任何地方 - 這樣的previous或next值是已知的你們，因爲我們已經看到的 - 它是你需要爲了得到另一個。

在此基礎上，你可以創建（C類僞代碼）：

struct Node { 
    void* data; 
    int xorValue; 
} 
Node* next(Node* node, void* previous) { 
    return (Node*)(node->xorValue^(int)previous)); 
} 
Node* previous(Node* node, void* next) { 
    return (Node*)(node->xorValue^(int)next)); 
} 

對於頭/最後一個元素 - 把上一個/下一個值（相應的）簡單地NULL（0）並保存下一個元素。它起作用next^0 = next