使用快速節點順序查詢的鏈接列表

Question

我們使用雙鏈表數據結構來存儲一些無序數據（數據本身是無序的，但是鏈接列表中的節點順序是相關的）。此數據結構上的一個常見操作是NodeBeforeNode（節點N1，節點N2），它在列表中給出兩個節點指針，並確定它們中的哪一個在另一個之前。

此操作需要線性時間，因爲它需要遍歷列表以查找其他元素，這非常緩慢。爲了加快速度，我們已經緩存了節點本身中每個節點的序號，並根據需要刷新了這個緩存。但是，刷新緩存是線性的，而修改列表並訪問緩存的操作往往非常緩慢。

我在尋找加快此行爲的建議。我基本上需要一個數據結構，其允許在恆定的或對數時間所有以下操作：

1. 插入（後或節點之前）
2. 刪除一個節點的
3. NodeBeforeNode

燦任何人都會提出一個像支持相同結構的鏈接列表？

謝謝！

Answer 1

實施經修改的二叉搜索樹，

struct node { 
    /*add your data*/ 
    node *parent; 
    node *left; 
    node *right; 
} 

中，你可以通過父指針和插入訪問前一個元素，搜索和刪除時間爲O（LOGN）

Answer 2

也許你應該考慮用某種索引更新節點？插入和刪除節點是肯定的線索，該列表應該是鏈表實現。我建議將新變量添加到表示其在列表中的位置的節點中。

所以基本上：

• 插入到底應該有索引每一個新項目= last_index + CONST
• 插入表應該有鄰居

該指數=算術平均值每一個新項目當然，只有當給定兩個節點在同一個列表上時纔有效。比較它們將是簡單的指數比較。

請注意，該索引應該是浮點數。這個簡單的方案假設，有無限可分的。如果你的程序運行很長時間，也許應該運行一些定期的工作人員乘以索引值？