oop - 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...