How to insert item into list in order?

Question

I have a List of DateTimeOffset objects, and I want to insert new ones into the list in order.

List<DateTimeOffset> TimeList = ...
// determine the order before insert or add the new item

Sorry, need to update my question.

List<customizedClass> ItemList = ...
//customizedClass contains DateTimeOffset object and other strings, int, etc.

ItemList.Sort();    // this won't work until set data comparison with DateTimeOffset
ItemList.OrderBy(); // this won't work until set data comparison with DateTimeOffset

Also, how to put DateTimeOffset as the parameter of .OrderBy()?

I have also tried:

ItemList = from s in ItemList
           orderby s.PublishDate descending    // .PublishDate is type DateTime
           select s;

However, it returns this error message,

Cannot implicitly convert type 'System.Linq.IOrderedEnumerable' to 'System.Collections.Gerneric.List'. An explicit conversion exist (are you missing a cast?)

Or use a different collection type, like a `SortedBag`: [is-there-a-sorted-collection-type-in-net](http://stackoverflow.com/questions/196512/is-there-a-sorted-collection-type-in-net) — nawfal, Jun 12 '14 at 17:44

score 82 · Answer 1 · answered Aug 29 '12 at 06:59

82

Assuming your list is already sorted in ascending order

var index = TimeList.BinarySearch(dateTimeOffset);
if (index < 0) index = ~index;
TimeList.Insert(index, dateTimeOffset);

answered Aug 29 '12 at 06:59

L.B

114,136
19
178
224

10

Can you explain your code? If they don't know how to insert into a list I doubt they will know what `~index` does. – Ash Burlaczenko Aug 29 '12 at 18:27
1

@AshBurlaczenko, you are right but the question's context seems to have been changed after ~1hr I answered and I am too lazy for it. – L.B Aug 29 '12 at 18:41
21

**From MSDN** : Return Value The zero-based index of item in the sorted List, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count. – Black Horus Dec 23 '12 at 18:45

score 51 · Answer 2 · edited May 23 '17 at 12:25

51

A slightly improved version of @L.B.'s answer for edge cases:

public static class ListExt
{
    public static void AddSorted<T>(this List<T> @this, T item) where T: IComparable<T>
    {
        if (@this.Count == 0)
        {
            @this.Add(item);
            return;
        }
        if (@this[@this.Count-1].CompareTo(item) <= 0)
        {
            @this.Add(item);
            return;
        }
        if (@this[0].CompareTo(item) >= 0)
        {
            @this.Insert(0, item);
            return;
        }
        int index = @this.BinarySearch(item);
        if (index < 0) 
            index = ~index;
        @this.Insert(index, item);
    }
}

edited May 23 '17 at 12:25

Community

1
1

answered Apr 02 '14 at 04:04

noseratio

59,932
34
208
486

4

This snippet just got me a 1000% performance improvement in a case where I couldn't use SortedSet<> and had to repeatedly .Sort() a List. – Nebu Nov 14 '14 at 20:24
1

What is `@this`? – Baruch Sep 19 '19 at 06:44
3

@Baruch `@this` is a purely conventional variable name, commonly used to refer the object being extended by a C# extension method. While `@this` is a valid C# variable name, you can use anything else instead, e.g. `list` might make sense here. – noseratio Sep 19 '19 at 06:55
5

The @ in front of `this` allows you to use a reserved word as a parameter/variable for those who haven't encountered this before. – Glenn Watson Sep 21 '20 at 03:33

Tim Schmelter · Answer 3 · 2012-08-29T07:06:25.180

With .NET 4 you can use the new SortedSet<T> otherwise you're stuck with the key-value collection SortedList.

SortedSet<DateTimeOffset> TimeList = new SortedSet<DateTimeOffset>();
// add DateTimeOffsets here, they will be sorted initially

Note: The SortedSet<T> class does not accept duplicate elements. If item is already in the set, this method returns false and does not throw an exception.

If duplicates are allowed you can use a List<DateTimeOffset> and use it's Sort method.

score 4 · Accepted Answer · answered Aug 29 '12 at 08:00

4

Modify your LINQ, add ToList() at the end:

ItemList = (from s in ItemList
            orderby s.PublishDate descending   
            select s).ToList();

Alternatively assign the sorted list to another variable

var sortedList = from s in ....

answered Aug 29 '12 at 08:00

Tommy Grovnes

4,126
2
25
40

Slate · Answer 5 · 2020-02-20T19:39:28.090

I took @Noseratio's answer and reworked and combined it with @Jeppe's answer from here to get a function that works for Collections that implement IList (I needed it for an ObservableCollection of Paths) and type that does not implement IComparable.

    /// <summary>
    /// Inserts a new value into a sorted collection.
    /// </summary>
    /// <typeparam name="T">The type of collection values, where the type implements IComparable of itself</typeparam>
    /// <param name="collection">The source collection</param>
    /// <param name="item">The item being inserted</param>
    public static void InsertSorted<T>(this IList<T> collection, T item)
        where T : IComparable<T>
    {
        InsertSorted(collection, item, Comparer<T>.Create((x, y) => x.CompareTo(y)));
    }

    /// <summary>
    /// Inserts a new value into a sorted collection.
    /// </summary>
    /// <typeparam name="T">The type of collection values</typeparam>
    /// <param name="collection">The source collection</param>
    /// <param name="item">The item being inserted</param>
    /// <param name="comparerFunction">An IComparer to comparer T values, e.g. Comparer&lt;T&gt;.Create((x, y) =&gt; (x.Property &lt; y.Property) ? -1 : (x.Property &gt; y.Property) ? 1 : 0)</param>
    public static void InsertSorted<T>(this IList<T> collection, T item, IComparer<T> comparerFunction)
    {
        if (collection.Count == 0)
        {
            // Simple add
            collection.Add(item);
        }
        else if (comparerFunction.Compare(item, collection[collection.Count - 1]) >= 0)
        {
            // Add to the end as the item being added is greater than the last item by comparison.
            collection.Add(item);
        }
        else if (comparerFunction.Compare(item, collection[0]) <= 0)
        {
            // Add to the front as the item being added is less than the first item by comparison.
            collection.Insert(0, item);
        }
        else
        {
            // Otherwise, search for the place to insert.
            int index = 0;
            if (collection is List<T> list)
            {
                index = list.BinarySearch(item, comparerFunction);
            }
            else if (collection is T[] arr)
            {
                index = Array.BinarySearch(arr, item, comparerFunction);
            }
            else
            {
                for (int i = 0; i < collection.Count; i++)
                {
                    if (comparerFunction.Compare(collection[i], item) <= 0)
                    {
                        // If the item is the same or before, then the insertion point is here.
                        index = i;
                        break;
                    }

                    // Otherwise loop. We're already tested the last element for greater than count.
                }
            }

            if (index < 0)
            {
                // The zero-based index of item if item is found,
                // otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
                index = ~index;
            }

            collection.Insert(index, item);
        }
    }

`collection.ToArray()` will create another collection which is more costlier than the linear search i.e. `collection.IndexOf()` — zafar, Nov 30 '17 at 18:29
I've edited with a new handling at the end -- Collection sadly doesn't have a binary search but... eh. — Slate, Feb 20 '20 at 19:40

score 3 · Answer 6 · answered Jul 20 '20 at 16:51

I was curious to benchmark two of the suggestions here, using the SortedSet class vs the List-based binary search insert. From my (non-scientific) result on .NET Core 3.1, it seems the List may use less memory for small (low hundreds) sets, but SortedSet starts winning on both time and memory the larger the set becomes.

(Items were instances of small class with two fields, Guid id and string name)

50 items:

|        Method |     Mean |     Error |    StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|----------:|----------:|-------:|------:|------:|----------:|
|     SortedSet | 5.617 μs | 0.0183 μs | 0.0153 μs | 0.3052 |     - |     - |    1.9 KB |
| SortedAddList | 5.634 μs | 0.0144 μs | 0.0135 μs | 0.1755 |     - |     - |   1.12 KB |

200 items:

|        Method |     Mean |    Error |   StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|---------:|---------:|-------:|------:|------:|----------:|
|     SortedSet | 24.15 μs | 0.066 μs | 0.055 μs | 0.6409 |     - |     - |   4.11 KB |
| SortedAddList | 28.14 μs | 0.060 μs | 0.053 μs | 0.6714 |     - |     - |   4.16 KB |

1000 items:

|        Method |     Mean |   Error |  StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|--------:|--------:|-------:|------:|------:|----------:|
|     SortedSet | 107.5 μs | 0.34 μs | 0.30 μs | 0.7324 |     - |     - |   4.73 KB |
| SortedAddList | 169.1 μs | 0.41 μs | 0.39 μs | 2.4414 |     - |     - |  16.21 KB |

techfun · Answer 7 · 2012-08-29T07:09:38.670

1

To insert item to a specific index

you can use:

DateTimeOffset dto;

 // Current time
 dto = DateTimeOffset.Now;

//This will insert the item at first position
TimeList.Insert(0,dto);

//This will insert the item at last position
TimeList.Add(dto);

To sort the collection you can use linq:

//This will sort the collection in ascending order
List<DateTimeOffset> SortedCollection=from dt in TimeList select dt order by dt;

edited Aug 29 '12 at 07:09

answered Aug 29 '12 at 06:44

techfun

913
2
13
25

2

Why not sort using the extension `.OrderBy()` – Ash Burlaczenko Aug 29 '12 at 06:50
Yes, Ash Burlaczenko that is also we can do. I am used write big queries in linq. That's why I wrote the above query which was the first thought came into my mind. But I agree with you. Thanks. – techfun Aug 29 '12 at 06:57
There is no overload of `List.Add` that takes an index. I think you mean [`List.Insert`](http://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.100).aspx). – Daniel Hilgarth Aug 29 '12 at 07:01
Yes, Daniel hilgarth, I meant Insert(Index,object) method. Thanks – techfun Aug 29 '12 at 07:09
is that the best way to insert or add item first to the list then sort the list? or it's better to insert item into the right position at the first time? – Jerry Aug 29 '12 at 07:20
1

Good question, Jerry. I am not sure about the best way. I think it would be dependent on data we have in collection. And the date we are inserting. But yes BinarySearch is quite efficient, you can go ahead with that or SortedSet collection. – techfun Aug 29 '12 at 07:29

score 0 · Answer 8 · edited Jun 07 '17 at 12:17

0

very simple, after adding data into list

list.OrderBy(a => a.ColumnName).ToList();

edited Jun 07 '17 at 12:17

hardkoded

18,915
3
52
64

answered Jun 07 '17 at 12:05

peeyush singh

33
4

score -2 · Answer 9 · answered Aug 29 '12 at 06:45

-2

You can use Insert(index,object) after finding index you want.

answered Aug 29 '12 at 06:45

levi

3,451
6
50
86

tell me sort order to write more – levi Aug 29 '12 at 06:47

How to insert item into list in order?

9 Answers9

Linked