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＃。