鏈接列表的一致性檢查

Question

首先，鏈表中的列表不變是什麼？

如何使用在O（n）時間和O（1）附加內存中運行的算法檢查鏈表是否一致？

Answer 1

在一個雙向鏈表中，不變量是每個節點都是其後繼者的前身。

考慮一個實現，其中每個節點維護兩個指針，一個指向它的後繼節點的指針succ，以及一個指向它的前驅節點的指針。

在一個正確的列表，該指針奠定了這樣的：

注意，當您按照succ指針從一個節點到下一個，你可以隨時使用pred指針去回到你的原始節點。操縱列表的每個操作都必須確保此條件保持不變。

違反這個不變的可能看起來像這樣的列表：

例如，這可以發生，如果不正確地執行插入操作試圖在名單的中間插入一個節點n2，卻忘了更新指針n3。

檢查這個不變的是直截了當的：沿succ指針（O(n)）遍歷遍歷列表並保持上次訪問節點的內存緩衝區（O(1)）。然後檢查每個節點當前節點的pred指針是否指向上次訪問的節點。

如果您也知道列表的最後一個節點，請檢查您到達的最後一個節點（沒有後繼節點的節點）是否是預期的最終節點。

請注意，對於單個鏈表，不存在這樣的不變量。