A simple way to implement a sorted list is a doubly-linked list of items that contain the key (on which items are sorted) and the content (the item itself).
To insert an item, you traverse the list, starting at the head, until you find a key that is greater (or equal) to the key to be inserted.
Then you open the links and insert the item right before the found item.
To implement this, I have created a ListElement that contains the key, the item and references to the respective previous and next item. The first item will have no reference to a previous item, and the last item no reference to a next item.
The List itself stores a reference to the head and tail of the list. This is where traversal begins.
The IComparable restriction on the TKey parameter is necessary to be able to compare two keys.
/// <summary>
/// One Element of the sorted list
/// </summary>
/// <typeparam name="TKey">Type of key used</typeparam>
/// <typeparam name="TContent">Type of content used</typeparam>
class ListElement<TKey, TContent> where TKey : IComparable
{
// who is before me?
public ListElement<TKey, TContent> Next { get; set; }
// who comes after me?
public ListElement<TKey, TContent> Prev { get; set; }
// my sort key
public TKey Key { get; set; }
// my content
public TContent Content { get; set; }
/// <summary>
/// Constructor: create an element without references
/// </summary>
/// <param name="key">sort value</param>
/// <param name="content">content value</param>
public ListElement(TKey key, TContent content)
{
Key = key;
Content = content;
Next = null;
Prev = null;
}
}
To hide the implementation details from the user, I have embedded this class into my SortedList, so it is only visible inside the class.
The class itself has to handle (among others) insertion, deletion, and traversal of the list.
For the question only asks for the insert method, the others are omitted:
public class SortedList<TKey, TContent> where TKey : IComparable
{
class ListElement<TKey, TContent> where TKey : IComparable
{
// see code above
}
// anchors
ListElement<TKey, TContent> head;
ListElement<TKey, TContent> tail;
public SortedList()
{
head = null;
tail = null;
}
/// <summary>
/// Insert an element into the sorted list so the list is sorted again after insertion
/// </summary>
/// <param name="key">key value (for sort order)</param>
/// <param name="content">item value</param>
/// <returns>the list itself</returns>
public SortedList<TKey, TContent> Add(TKey key, TContent content)
{
ListElement<TKey, TContent> newElement = new ListElement<TKey, TContent>(key, content);
// if no element in the list, this is the first and last one
if (head == null)
{
head = newElement;
tail = newElement;
return this;
}
// if the new element is less than the head, it becomes the head
if (((IComparable)head.Key).CompareTo(key) >= 0)
{
newElement.Next = head;
head = newElement;
}
// find the preceding element
for (var element = head; element.Next != null; element = element.Next)
{
if (((IComparable)element.Next.Key).CompareTo(key) >= 0)
{
newElement.Prev = element;
newElement.Next = element.Next;
element.Next = newElement;
return this;
}
}
// all preceding elements are less than the new: insert at end
newElement.Prev = tail;
tail.Next = newElement;
tail = newElement;
return this;
}
}
The Add method returns the list reference, so multiple adds can be performed in 'fluent' code, like
public void AddSomeElements()
{
SortedList<int, string> list = new SortedList<int, string>();
list
.Add(2, "two")
.Add(4, "four")
.Add(1000, "M");
}
Discussion:
This algorithm is one of the simplest for sorted lists. It is suitable for small lists. Your could improve the insert method to double speed if you held the middle key at class level and decide first whether to traverse the list from head or tail.
For larger lists, a tree or hash storage for the items would be more appropriate, as you have to traverse the whole list if you want to insert an element at the end, which makes the algorithm O(n).