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).