What is the difference between List (of T) and Collection(of T)?

I've seen them used in a lot of the same ways, and I am worried I'm about to go down a path in design that is irreversible if I don't understand this better. Also, I am using .NET.

In C#, there are three concepts for representing a bag of objects. In order of increasing features, they are:

• Enumerable - unordered, unmodifiable
• Collection - can add/remove items
• List - allows items to have an order (accessing and removing by index)

Enumerable has no order. You cannot add or remove items from the set. You cannot even get a count of items in the set. It strictly lets you access each item in the set, one after the other.

Collection is a modifiable set. You can add and remove objects from the set, you can also get the count of items in the set. But there still is no order, and because there is no order: no way to access an item by index, nor is there any way to sort.

List is an ordered set of objects. You can sort the list, access items by index, remove items by index.

In fact, when looking at the interfaces for these, they build on one another:

• interface IEnumerable<T>

  • GetEnumeration<T>

• interface ICollection<T> : IEnumerable<T>

  • Add
  • Remove
  • Clear
  • Count

• interface IList<T> : ICollection<T>

  • Insert
  • IndexOf
  • RemoveAt

When declaring variables, or method parameters, you should choose to use

• IEnumerable
• ICollection
• IList

based on what conceptually you need to do with the set of objects.

If you just need to be able to do something to every object in a list, then you only need IEnumerable:

void SaveEveryUser(IEnumerable<User> users)
{
    for User u in users
      ...
}

You don't care if the Users are kept in a List<T>, Collection<T>, Array<T> or anything else. You only need the IEnumerable<T> interface.

If you need to be able to add, remove, or count the items in a set, then use a Collection:

ICollection<User> users = new Collection<User>();
users.Add(new User());

If you care about a sort order, and need the order to be correct, then use a List:

IList<User> users = FetchUsers(db);

In chart form:

| Feature                | IEnumerable<T> | ICollection<T> | IList<T> |
|------------------------|----------------|----------------|----------|
| Enumerating items      | X              | X              | X        |
|                        |                |                |          |
| Adding items           |                | X              | X        |
| Removing items         |                | X              | X        |
| Count of items         |                | X              | X        |
|                        |                |                |          |
| Accessing by index     |                |                | X        |
| Removing by index      |                |                | X        |
| Getting index of item  |                |                | X        |

The List<T> and Collection<T> in System.Collections.Generic are two classes that implement these interfaces; but they aren't the only classes:

• ConcurrentBag<T> is an ordered bag of objects (IEnumerable<T>)
• LinkedList<T> is a bag where you are not allowed to access items by index (ICollection); but you can arbitrarily add and remove items from the collection
• SynchronizedCollection<T> is an ordered collection, where you can add/remove items by index

So you can easily change:

IEnumerable<User> users = new SynchronizedCollection<User>();

SaveEveryUser(users);

tl;dr

• Enumerable - access items, unordered, unmodifiable
• Collection - can be modified (add,delete,count)
• List - can access by index

Choose the concept you need, then use the matching class.

Collection<T> is a customizable wrapper around IList<T>. While IList<T> is not sealed, it doesn't provide any customization points. Collection<T>'s methods are by default delegated to the standard IList<T> methods, but can be easily overridden to do what you want. It is also possible to wireup events inside a Collection<T> that I don't believe could be done with an IList.

In short, it's much easier to extend it after the fact, which could potentially mean a lot less refactoring.

List<T> is intended for internal use within the application code. You should avoid writing public APIs that accept or return List<T> (consider using a superclass or a collection interface instead).

Collection<T> serves a base class for custom collections (although it can be used directly).

Consider using Collection<T> in your code unless there are specific features of List<T> that you need.

The above are just recommendations.

[Adapted from: Framework Design Guidelines, Second Edition]

List<T> is a very commonly seen container, because it is so very versatile (with lots of handy methods like Sort, Find, etc) - but has no extension points if you want to override any of the behaviour (check items on insert, for example).

Collection<T> is a wrapper around any IList<T> (defaulting to List<T>) - it has the extension points (virtual methods), but not as many support methods like Find. Because of the indirection, it is slightly slower than List<T>, but not by much.

With LINQ, the extra methods in List<T> become less important, since LINQ-to-Objects tends to provide them anyway... for example First(pred), OrderBy(...), etc.

List is faster.

Do for example

private void button1_Click(object sender, EventArgs e)
{
  Collection<long> c = new Collection<long>();
  Stopwatch s = new Stopwatch();
  s.Start();
  for (long i = 0; i <= 10000000; i++)
  {
    c.Add(i);
  }
  s.Stop();
  MessageBox.Show("collect " + s.ElapsedMilliseconds.ToString());

  List<long> l = new List<long>();
  Stopwatch s2 = new Stopwatch();
  s2.Start();
  for (long i = 0; i <= 10000000; i++)
  {
    l.Add(i);
  }
  s2.Stop();
  MessageBox.Show("lis " + s2.ElapsedMilliseconds.ToString());


}

on my machine List<> is almost twice as fast.

Edit

I can't understand why people are downvoting this. Both on my work machine and my home machine the List<> code is 80% faster.

List represents a collection where the order of items is important. It also supports methods s.a. Sort and search. Collection is a more general data-structure which makes less assumptions about the data and also supports less methods to manipulate it. If you want to expose a custom data structure, you should probably extend the collection. If you need to manipulate data w/o exposing the data-structure, a list is probably the more convenient way to go.

All of these interfaces inherit from IEnumerable, which you should make sure you understand. That interface basically lets you use the class in a foreach statement (in C#).

• ICollection is the most basic of the interfaces you listed. It's an enumerable interface that supports a Count and that's about it.
• IList is everything that ICollection is, but it also supports adding and removing items, retrieving items by index, etc. It's the most commonly-used interface for "lists of objects", which is vague I know.
• IQueryable is an enumerable interface that supports LINQ. You can always create an IQueryable from an IList and use LINQ to Objects, but you also find IQueryable used for deferred execution of SQL statements in LINQ to SQL and LINQ to Entities.
• IDictionary is a different animal in the sense that it is a mapping of unique keys to values. It is also enumerable in that you can enumerate the key/value pairs, but otherwise it serves a different purpose than the others you listed

This is one of those grad school questions. A Collection of T is sort of abstract; there may be a default implementation (I'm not a .net/c# guy) but a collection will have basic operations like add, remove, iterate, and so on.

List of T implies some specifics about these operations: add should take constant time, remove should take time proportional to the number of elements, getfirst should be consant time. In general, a List is a kind of Collection, but a Collection isn't necessarily a kind of List.

Hanselman Speaks: "Collection<T> looks like a list, and it even has a List<T> internally. EVERY single method delegates to the internal List<T>. It includes a protected property that exposes the List<T>."

EDIT: Collection<T> doesn't exist in System.Generic.Collections .NET 3.5. If you migrate from .NET 2.0 to 3.5 you'll need to change some code if you're using a lot of Collection<T> objects, unless I'm missing something obvious...

EDIT 2: Collection<T> is now in the System.Collections.ObjectModel namespace in .NET 3.5. The help file says this:

"The System.Collections.ObjectModel namespace contains classes that can be used as collections in the object model of a reusable library. Use these classes when properties or methods return collections."

According to MSDN, List(Of T).Add is "an O(n) operation" (when "Capacity" is exceeded) while Collection(Of T).Add is always "an O(1) operation". That would understandable if List is implemented using an Array and Collection a Linked List. However, if that were the case, one would expect Collection(Of T).Item to be "an O(n) operation". But - it's - not!?! Collection(Of T).Item is "an O(1) operation" just like List(Of T).Item.

On top of that, "tuinstoel"'s "Dec 29 '08 at 22:31" post above claims speed tests show List(Of T).Add to be faster than Collection(Of T).Add which I've reproduced with Long's and String's. Although I only got ~33% faster vs. his claimed 80%, according MSDN, it should've been the opposite and by "n" times!?!

Both implement the same interfaces, so they'll behave the same way. Perhaps they are implemented differently internally, but this would have to be tested.

The only real differences I see are the namespaces and the fact that Collection<T> is marked with ComVisibleAttribute(false), so COM code can't use it.

In addition to other asnwers, I've compiled quick overview of generic list and collection capabilities. Collection is limited subset of the List:

= present
o = partially present

Property/Method   Collection<T>   List<T>
----------------------------------------------
Add()                *              *
AddRange()                          *
AsReadOnly()                        *
BinarySearch()                      *
Capacity                            *
Clear()              *              *
Contains()           *              *
ConvertAll()                        *
CopyTo()             o              *
Count                *              *
Equals()             *              *
Exists()                            *
Find()                              *
FindAll()                           *
FindIndex()                         *
FindLast()                          *
FindLastIndex()                     *
ForEach()                           *
GetEnumerator()      *              *
GetHashCode()        *              *
GetRange()                          *
GetType()            *              *
IndexOf()            o              *
Insert()             *              *
InsertRange()                       *
Item()               *              *
LastIndexOf()                       *
New()                o              *
ReferenceEquals()    *              *
Remove()             *              *
RemoveAll()                         *
RemoveAt()           *              *
RemoveRange()                       *
Reverse()                           *
Sort()                              *
ToArray()                           *
ToString()           *              *
TrimExcess()                        *
TrueForAll()                        *