C＃LinkedList vs列表的運行長度編碼？

Question

其中哪一個更適合於字節上的RLE？我需要能夠快速地在列表中插入數據，但我還需要能夠快速找到未壓縮字節3987的位置（這可能更重要，我認爲最好的方法是通過所有的直到我得到最接近的3987下）？）。

Answer 1

您是否期望您插入的內容比您要搜索的要多？因爲每種方法都比一種更好。

我假設你的LinkedList的節點會是這個樣子：

class RleNode { Byte Value; Int32 Length; RleNode Prev; RleNode Next; } 

如果您需要快速插入，那麼你會希望有一個鏈表結構去不管。

爲了加速計算位置的查找，我將鏈接列表結構封裝在一個新類中，該類將其與地圖索引組合在一起。索引必須在每次插入時重建。

編輯：

我不知道如果一棵樹可能會更快依然。您將通過DFS遍歷樹來重建線性RLE流。通過樹，每個父節點可以存儲其子節點的總RLE長度，因此可以在不必重新計算總體結構的RLE長度的情況下完成插入操作，並且復原速度也一樣快。

我建議你把這個問題重新標記爲計算機科學而不是C＃。