Which is better to use array or List<>?

Question

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?

Solution 1

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.

Solution 2

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.

Solution 3

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.

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

Solution 5

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.

View more solutions

Comments

[Aaronaught]

@Evan: The second part of your comment is highly misleading. You can initialize a List<T> 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.

[Mitch Wheat]

+1. for mentioning List initial capacity.

[KP.]

ditto. Good 'real world' rationale

[Joe]

"If the collection should not be changed by the outside world use IEnumerable<T>" - I disagree with this characterisation. Returning IEnumerable<T> won't help if the object referenced by the return value is a mutable list - the caller can always cast. You should return IEnumerable<T> if the caller should only be able to enumerate, ICollection<T> if he also needs a Count, and IList<T> 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<T>.AsReadOnly).

[Aaronaught]

@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<T> 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<T> instance, i.e. by returning originalEnumerable.Select(x => x).ToArray().

[Aaronaught]

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<T> will give a runtime error if a modification is attempted; you want to catch such errors at compile-time whenever possible.

[Evan Plaice]

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

[Aaronaught]

@Evan: There are no relevant performance characteristics because, as brickner's answer correctly states, the List<T> 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]

@Evan: You seem to think that the List<T> 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<T> 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<T> class.

[Evan Plaice]

My bad... Not sure what I was thinking either. Should stay off StackOverflow when I'm sleep deprived. For some reason I attributed List<T> 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<T> 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.

[MPavlak]

@Aaronaught - I completed support your argument indicating that you cannot really protect against hostile clients and am always surprised to see List<T>.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.