Maintaining a sorted list
<p>I need to store a collection of nodes:</p>

<pre><code>class Node
{
   int Value;
   //other info
}
</code></pre>

<p>I have three requirements:</p>

<ol>
<li>Need to be able to efficiently retrieve the node with the lowest Value in the collection </li>
<li>Need to be able to efficiently insert a node into the collection</li>
<li>Two nodes can have the same Value</li>
</ol>

<p>I thought the best collection to use for this would be some sort of sorted list. That way requirement #1 is satisfied efficiently by just taking the first element from the sorted list. Requirement #2 is satisfied efficiently by inserting a new node in the right place in the list.</p>

<p>But the <code>SortedList</code> collection in .Net is like <code>SortedDictionary</code> and requires the key being sorted on to be unique, which violates requirement #3.</p>

<p>There appears to be no collection in .Net that satisfies these requirements, mainly because the self-sorting collections that do exist require keys being sorted on to be unique. What is the reason for this? I assume it cannot be an oversight. What am I not grasping here? I can find similar questions about this but they usually involve someone suggesting <code>SortList</code>, followed by realizing this doesn't work, and then the conversation fades out without a standard solution. At least if someone would say "There is no collection in C# for this task, you need to hack something together" that would be an answer.</p>

<p>Is it acceptable to use a regular <code>List&lt;Node&gt;</code> and re-sort the list whenever a new node is added? Seems like that wouldn't be as efficient as inserting the node in the right place to begin with. Perhaps that is what I should do? Manually iterate over the list until I find the place to insert a new node myself?</p>
