Logarithmic time C# list

Does there exist an implementation for .NET of a list collection such that both insert and lookup are worst-case O(log(n)) operations? The default System.开发者_如何学PythonCollections.Generic.List 'Insert' method is an O(n) operation.

By a list collection, I mean an array-like expandable data structure. By 'lookup' I mean access by index.

I suspect this can be done with balanced trees, but would be non-trivial to implement.

I do not know of a .NET implementation, but a data structure that might work for you is an Indexible Skiplist. It has similar O(lg n) performance like a balanced binary tree but is conceptually more like a linked list.

http://en.wikipedia.org/wiki/Skip_list

I don't think it would be too hard to write one in C#.

The C5 TreeSet should give you a red/black implementation with those characteristics, including index access.

Don't know if there exist in the .net framework, but you can implement aa tree insert and search is both O(log n).

There is no possible solution for this if you need to access fields using their index. You can use a SortedList, but then you get O(n), or you can use SortedDictionary, but then you lose the array-like access (by index).