34

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?

tereško
  • 58,060
  • 25
  • 98
  • 150
George Silva
  • 3,454
  • 10
  • 39
  • 64
  • 3
    It really depends on what you want to do with them. – LukeH Sep 16 '09 at 14:28
  • 10
    "Fast" and "slow" are irrelevant. Relevant are "fast enough for my customer" and "too slow for my customer". Your first question should be "are lists fast enough?" You are the only one who knows who your customer is and what their performance requirements are, so only *you* can answer that question. You'll answer it by trying out some meaningful benchmarks and comparing them to your carefully-stated real-world customer-focussed goals. – Eric Lippert Sep 16 '09 at 14:45

2 Answers2

88

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

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
13

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.

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900