28

I was wondering which type would have better performance and which you think should be used.

For example I have a List of strings not knowing how many items I will need so having the .Add(String) function is really convenient. I can Add new strings to the list at any time easily.

What are the advantages/disadvantages of using each?

Are lists the new arrays?

Gage
  • 7,365
  • 9
  • 47
  • 77
  • 1
    @Evan: The second part of your comment is highly misleading. You can initialize a `List` with a specific capacity the same way you do with an array. If you know the size in advance, it doesn't matter which one you use, and if you don't know the size in advance **as the question clearly states**, then you really *can't* use an array. If you have evidence that arrays offer "much" better read performance, please post an answer with that evidence. – Aaronaught Feb 28 '11 at 15:13

8 Answers8

44

More context is really required to answer the question properly:

In a public API, you should try to use abstract collection types, so that you can change the internal implementation later if you need to.

  • If the collection should not be changed by the outside world, use IEnumerable<T>.
  • If the collection will be changed by the outside world, use ICollection<T>.
  • If indexed access is required, use IList<T>.

In a private implementation, it's not as important to use the abstract types:

  • If you need indexed access and know the final size, use T[] or List<T>.
  • If you need indexed access and don't know the final size, use List<T>.
  • If you plan to access elements in a LIFO pattern, use Stack<T>.
  • If you plan to access elements in a FIFO pattern, use Queue<T>.
  • If you need to access elements at the beginning and end of the list, but not in the middle, use LinkedList<T>.
  • If you don't want duplicates, use HashSet<T>.

In .NET 4.0 you have a few more choices, but those are the basics.

Aaronaught
  • 120,909
  • 25
  • 266
  • 342
  • "If the collection should not be changed by the outside world use IEnumerable" - I disagree with this characterisation. Returning IEnumerable won't help if the object referenced by the return value is a mutable list - the caller can always cast. You should return IEnumerable if the caller should only be able to enumerate, ICollection if he also needs a Count, and IList if he will need indexed access. In **all** of the above cases, if the collection should not be changed by the outside world, wrap it in a readonly collection (e.g. using List.AsReadOnly). – Joe Jun 04 '10 at 16:01
  • 1
    @Joe: I'm not a fan of that argument. The caller can always try to cast **anything** you give it to *anything* else - it's simply poor design to do so. You can wrap all results in a `ReadOnlyCollection` if you want, but that won't protect you against *hostile* callers; they can just use Reflection to get at the internal mutable list. If this is ultra-secure code then the only way to guarantee this particular invariant is return a *new*, generated `IEnumerable` instance, i.e. by returning `originalEnumerable.Select(x => x).ToArray()`. – Aaronaught Jun 04 '10 at 16:49
  • But in any event, the recommendations are from a discoverability and code-maintenance perspective (writing self-documenting code), not a security perspective; if you're in the latter camp then you have *many* other things to worry about. It's also the reason why I used the phrase "should not" as opposed to "must not" - it's not a guarantee, just a very strong hint. `ReadOnlyCollection` will give a *runtime* error if a modification is attempted; you want to catch such errors at *compile-time* whenever possible. – Aaronaught Jun 04 '10 at 16:56
  • @Evan: There **are no** relevant performance characteristics because, as brickner's answer correctly states, the `List` class is implemented *using* an array. As for giving bad advice - at what point did you even read the first half of the answer where I unambiguously state that it's better to use abstract types and specifically the type with the least functionality necessary to do the job? Finally, as for "placing it within a property", nowhere does this answer or any of my answers on this site ever state that direct access should be given to a field, nor can I guess why you'd infer that. – Aaronaught Feb 28 '11 at 15:11
  • My bad... Not sure what I was thinking either. Should stay off StackOverflow when I'm sleep deprived. For some reason I attributed List to be equivalent to LinkedList and missed the part about using interfaces on the publicly accessible parts in place of classes. After the face (and out of curiosity) I googled performance of List vs T[] and apparently the trade off is <3% on read access. I wish I still had the article link to share. BTW, I reversed my vote to +1. – Evan Plaice Mar 17 '11 at 11:38
  • @Aaronaught - I completed support your argument indicating that you cannot really protect against hostile clients and am always surprised to see List.AsReadOnly() being returned by an IEnumerable property. It is just silly to me. If they want to jump in and change the type, they are going to so that this wrapping seems like unnecessary overhead. – MPavlak Aug 30 '12 at 15:41
24

List<String> is implemented using an array String[].

If you don't know how many elements you'll have, use List<String>

You can give the estimated (or maximum) number of elements you expect in the capacity constructor parameter (new List<String>(10)), this will be the initial size of the underlying array.

When you Add() an item and there is no room for this item, the underlying array is copied to a new array of double the size.

What I do: when I know the exact size of the collection and I know I won't change the size of the collection, I use an array (String[]). Otherwise I use a List<String>.

By the way, this goes for any type and not just String.

brickner
  • 6,595
  • 3
  • 41
  • 54
  • +1. for mentioning List initial capacity. – Mitch Wheat Jun 04 '10 at 15:17
  • ditto. Good 'real world' rationale – KP. Jun 04 '10 at 15:44
  • +1 for being the best answer but it only goes half-way to comparing the differences. [Reading Performance] For arrays the value if an index can be immediately retrieved because the offset is static whereas with lists, the items need to be crawled to get the value of an index. For large collections this may have a drastic impact on performance. [Write Performance] On the contrary, lists can grow indefinitely without having to move data. With an array, you need to allocate a new array and copy the memory into it (really inefficient). Memory streams are the answer to growing arrays. – Evan Plaice Feb 28 '11 at 12:05
  • 1
    @Evan: You seem to think that the `List` is implemented as a linked list. Maybe you should do your research, or even just read the answers you vote on, as the first line in this one clearly states (accurately) that `List` is implemented using arrays, which are copied into new arrays when the list needs to grow. If you want a linked list, you use the `LinkedList` class. – Aaronaught Feb 28 '11 at 15:16
7

It depends on usage scenario, BUT it's also a micro-optimisation until you have identified a bottleneck by profiling. Use whatever fits the usage best.

Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
4

Use List<> in most all cases, and don't worry about performance. There is a good chance you will go through your entire career and never need to performance tune by converting a List<> into an array.

Brent Arias
  • 29,277
  • 40
  • 133
  • 234
3

In most scenarios the performance difference is not appreciable so I would use List<string> since it provides much more functionality that could be useful in different situations.

Claudio Redi
  • 67,454
  • 15
  • 130
  • 155
2

If you don't know the size of items to be added, always go for List<string> than string array.

Srinivas Reddy Thatiparthy
  • 10,985
  • 4
  • 45
  • 68
2

If you need dynamic sizing, then go with List<string>.

If you're worried about performance, then I would suggest starting with List<string> and see if there's really an issue. It uses arrays internally so I would think, for the most part, there should be no performance issues.

If you have a staticly sized collection, you could still use string[].

Justin Niessner
  • 242,243
  • 40
  • 408
  • 536
2

Of course it depends on your application, but in circumstances List<string> (or even just IEnumerable<string> is preferable.

Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794