Does List<T> Guarantee Insertion Order

Does ListT guarantee insertion order?

The List<> class does guarantee ordering - things will be retained in the list in the order you add them, including duplicates, unless you explicitly sort the list.

According to MSDN:

...List "Represents a strongly typed list of objects that can be
accessed by index."

The index values must remain reliable for this to be accurate. Therefore the order is guaranteed.

You might be getting odd results from your code if you're moving the item later in the list, as your Remove() will move all of the other items down one place before the call to Insert().

Can you boil your code down to something small enough to post?

Does a ListT guarantee that items will be returned in the order they were added?

The List is index based and new items will always be added to the end of the list. You can insert items at a certain index so the next items will move one position.

So yes, you can use it safely that way...

The List(T) class is the generic
equivalent of the ArrayList class. It
implements the IList(T) generic
interface using an array whose size is
dynamically increased as required.

Elements in this collection can be
accessed using an integer index.
Indexes in this collection are
zero-based.

The List(T) is not guaranteed to be
sorted. You must sort the List(T)
before performing operations (such as
BinarySearch) that require the List(T)
to be sorted.

A List(T) can support multiple readers
concurrently, as long as the
collection is not modified.
Enumerating through a collection is
intrinsically not a thread-safe
procedure. In the rare case where an
enumeration contends with one or more
write accesses, the only way to ensure
thread safety is to lock the
collection during the entire
enumeration. To allow the collection
to be accessed by multiple threads for
reading and writing, you must
implement your own synchronization.

You can read more about it on MSDN.

ListT items order

It looks like it's a safe assumption.

Although, for critical applications (defence/finance), it might be worth using a LinkedList or sub-classing the List to make it future-proof in case a new framework changes the implementation.

The GetEnumerator will always return the first element in the List, but there is no written guarantee that the next element must be the second in the List.

What does it mean by Insertion Order is preserved in Collections?

Insertion Order means the order in which we are inserting the data.

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("alpha");
    list.add("beta");
    list.add("gamma");

    for (String string : list) {
        System.out.println(string);
    }
}

Output :
alpha
beta
gamma

Insertion order is maintained.

If you want the original insertion order there are the LinkedXXX
classes, which maintain an additional linked list in insertion order.
Most of the time you don't care, so you use a HashXXX, or if you want a natural order, so you use TreeXXX.

Is a Python list guaranteed to have its elements stay in the order they are inserted in?

Yes, the order of elements in a python list is persistent.

Does HashSet preserve insertion order *if no items are deleted*

That being said, I am interested in whether insertion order is
maintained when no deletions occur in the current implementation.

Yes, it is maintained in 4.7.2. As of 18 Jan 2019.

I suspect part of the issue here is understanding the difference between contract and implementation.

The implementation of HashSet in 4.7.2 will maintain insertion order (if you don't remove items). But you didn't originally ask that. You asked whether:

insertion order is guaranteed

And for that question, the answer is unequivocally No. A method's guarantees are not defined by the implementation, but by the contract. And the contract states:

A set is a collection that contains no duplicate elements, and whose
elements are in no particular order.

There is simply no way to read that statement in any other way than that there are no guarantees as to order.

Now - you can choose to ignore the guarantees, and deploy an app relying on the current behaviour. And, as long as Microsoft doesn't release a Windows Update patch that changes the behaviour (or your code runs in a different implementation like Mono etc), you will probably be OK. But probably is not the same as definitely (or guaranteed).

Dictionary to List Insertion order

The only way to know this for sure is to look at the code, so let's do that...

The implementation of the constructor you are calling of List<T>, when decompiled, looks like

public List(IEnumerable<T> collection)
{
  if (collection == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  ICollection<T> collection1 = collection as ICollection<T>;
  if (collection1 != null)
  {
    int count = collection1.Count;
    if (count == 0)
    {
      this._items = List<T>._emptyArray;
    }
    else
    {
      this._items = new T[count];
      collection1.CopyTo(this._items, 0);
      this._size = count;
    }
  }
  else
  {
    this._size = 0;
    this._items = List<T>._emptyArray;
    foreach (T obj in collection)
      this.Add(obj);
  }
}

As you can see, the dictionary is cast to ICollection<T> and then CopyTo is called on it which leads us to Dictionary<TKey, TValue>

private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
{
  if (array == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  if (index < 0 || index > array.Length)
    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  if (array.Length - index < this.Count)
    ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
  int num = this.count;
  Dictionary<TKey, TValue>.Entry[] entryArray = this.entries;
  for (int index1 = 0; index1 < num; ++index1)
  {
    if (entryArray[index1].hashCode >= 0)
      array[index++] = new KeyValuePair<TKey, TValue>(entryArray[index1].key, entryArray[index1].value);
  }
}

From looking at the code, the internal items of the dictionary are indexed into.

Based on these findings, if what you are asking is "will the order of my dictionary be retained when it's converted to a generic list?" - then yes it will be (as per .NET 4.0 which is the version I am looking at). However, the problem is you can't actually guarantee the order of your items being added to the dictionary to start with. So my advice would be switch to using something like OrderedDictionary<T> or apply an OrderBy clause before you convert it e.g.

var list = new List<KeyValuePair<K, V>>(test.OrderBy(x => x.Value));

Can I guarantee insertion order of IEnumerables over WCF?

The serialiser will naturally serialise items in the order in which they are served up by the collection's enumerator. For a List or Array, this will always be the order in which they are added, but for anything based on a hashtable, the order is not guaranteed. To guarantee the order, use an array-based collection.

---

Related Topics