Fast insert in Link-like object

Question

In a real-time Agent-based modelling project I have the following problem: Assume I have some class MyClass with a public proporty X (X is a double). I need a class (call it FancyList) that can contain my objects in a sorted manner. If I insert a new MyClass-object it should be inserted between an object with a lower X and one with a higher X.

FancyList _fancyList = new FancyList();

// Allocate MyClass objects. The X proporty is defined in the constructor
MyClass c1 = new MyClass(2.0)
MyClass c2 = new MyClass(3.0)
MyClass c3 = new MyClass(2.5)

_fancyList.Insert(c1);
_fancyList.Insert(c2);
_fancyList.Insert(c3);

// In the fancyList c3 is after c1 and before c2. Therefore c1 is the first
// element, and c2 is the last element

It is important that the insert is as fast as possible.

Answer 1

Use a SortedList<> or a SortedDictionary<>.

They both implement IDictionary. According to the MSDN docs the SortedDictionary has the faster Insert operation. Do read the rest of those specs.

FancyList _fancyList = new SortedDictionar<double, MyClass>();

// Allocate MyClass objects. The X proporty is defined in the constructor
...

_fancyList.Insert(c1.X, c1);
_fancyList.Insert(c2.X, c2);
_fancyList.Insert(c3.X, c3);