C# LinkedList vs List for Run Length Encoding?

Question

Which one of these would be more suitable for RLE on bytes? I need to be able to insert data in the list reasonably quickly, but I also need to be able to find out where say uncompressed byte 3987 quickly (this is probably more important, I'd assume the best way is to go through all the counts until I get the closest one under 3987?).

Answer 1

Do you expect you'll be inserting more than you'll be searching? Because each approach is better for one rather than the other.

I assume your LinkedList node would look something like this:

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

If you need quick insertions then you'll want to go with a linked-list structure regardless.

To speed up lookups by calculated positions I'd encapsulate the linked-list structure in a new class that combines it with a map index. The index would have to be rebuilt on every insertion.

EDIT:

I wonder if a tree might be faster still. You would rebuild a linear RLE stream with a DFS traversal of the tree. With a tree, each parent node could store the total RLE length of its children, so insertions can be done without having to recalculate the RLE length of the total structure, and retreival would be just as fast.

I suggest you re-tag this question as computer science than C#.