Speed of C# lists

Question

Are C# lists fast? What are the good and bad sides of using lists to handle objects?

Extensive use of lists will make software slower? What are the alternatives to lists in C#?

How many objects is "too many objects" for lists?

Answer 1

List<T> uses a backing array to hold items:

• Indexer access (i.e. fetch/update) is O(1)
• Remove from tail is O(1)
• Remove from elsewhere requires existing items to be shifted up, so O(n) effectively
• Add to end is O(1) unless it requires resizing, in which case it's O(n). (This doubles the size of the buffer, so the amortized cost is O(1).)
• Add to elsewhere requires existing items to be shifted down, so O(n) effectively
• Finding an item is O(n) unless it's sorted, in which case a binary search gives O(log n)

It's generally fine to use lists fairly extensively. If you know the final size when you start populating a list, it's a good idea to use the constructor which lets you specify the capacity, to avoid resizing. Beyond that: if you're concerned, break out the profiler...

Answer 2

Compared to what?

• If you mean List<T>, then that is essentially a wrapper around an array; so fast to read/write by index, relatively fast to append (since it allows extra space at the end, doubling in size when necessary) and remove from the end, but more expensive to do other operations (insert/delete other than the end)
• An array is again fast by index, but fixed size (no append/delete)
• Dictionary<,> etc offer better access by key

A list isn't intrinsically slow; especially if you know you always need to look at all the data, or can access it by index. But for large lists it may be better (and more convenient) to search via a key. There are various dictionary implementations in .NET, each with different costs re size / performance.