computer-science - C# LinkedList vs List 用于运行长度编码？

Question

其中哪一个更适合字节上的 RLE？我需要能够相当快地在列表中插入数据，但我还需要能够快速找出未压缩字节 3987 的位置（这可能更重要，我认为最好的方法是通过所有直到我得到 3987 以下最接近的一个？）。

Answer 1

您是否希望插入的内容多于搜索的内容？因为每种方法都比另一种更好。

我假设您的 LinkedList 节点看起来像这样：

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

如果您需要快速插入，那么无论如何您都需要使用链表结构。

为了通过计算位置加快查找速度，我将链表结构封装在一个新类中，该类将它与地图索引相结合。每次插入时都必须重建索引。

编辑：

我想知道一棵树是否会更快。您将使用 DFS 遍历树来重建线性 RLE 流。对于树，每个父节点都可以存储其子节点的总 RLE 长度，因此无需重新计算整个结构的 RLE 长度即可完成插入，并且检索速度也一样快。

我建议您将这个问题重新标记为计算机科学而不是 C#。