List<T> vs Array

[Ubiquitous]

Hello everyone haven't posted in a while. Like the title says the topic I am wondering about is List<T> vs Arrays. From the information I've gathered List<T> seems to be a more versatile function than an array. From what I've read on the topic array's are faster. I would think the sort function and easy expandable list outweigh the speed of the array.

My question is would there be a time where array's are preferred over a List<T> or is it just in the programmers interest on which one to use?

Thanks in advanced as I am sure the question has been asked plenty of times.

[DataMiser]

Well if arrays are faster then it should be clear that there are cases where an array would be the ticket.

[Ubiquitous]

Well would it really make a difference in simple applications or would this be more useful in games and such?

[Mutant_Fruit]

The only difference really is that one is of fixed size and one is dynamically resized as you add more elements.

[TheGreatCthulhu]

Yes - with List<T> u can dynamically add/insert/remove elements, but an array will be faster in terms of access time. I don't know if you're familiar with C#'s reference types (basically classes): with them, your variables don't store the actual value of the object, but a reference to the object (whatever that internally might be), that is stored at some memory location managed by the runtime.

Now, the List<T> generic class has a ToArray() method that bassically takes these references and copies them to an array of the type T[] - so this operation is not terribly expensive even if you're dealing with large objects. Some algorithms will work better (faster) on arrays, especially if they involve a lot of object accesses, but only a few changes (if any) to the collection structure - a simple example would be a binary search. The bottom line is that you can adapt your data structure as suited - before you enter a computation-intensive section.

This would make a difference in real-time/interacive apps that require high performance, and in apps that process a lot (a looooooooooooooooooooooooooooooooot) of data.

P.S. There is also a SortedList<Key, Value> generic class, you might want to check it out - sorts automatically, using unique keys.

[Mutant_Fruit]

I'd nearly go as far as saying that performance is *never* the reason you'd choose an Array over a List regardless of your app. The performance difference is so small that it'd more than likely be hidden by the cost of comparing two elements in the list if you have a custom Equals or GetHashCode method. If you're optimising your application to use arrays directly instead of incurring the 'cost' of a List<T> access, you're optimising the wrong thing

a simple example would be a binary search

List<T> has a method called 'BinarySearch' which you can use which internally does a BinarySearch on a regular T array. Performance difference of using List<T>.BinarySearch versus Array.BinarySearch is ~zero.

[TheGreatCthulhu]

The performance difference is so small that it'd more than likely be hidden by the cost of comparing two elements in the list if you have a custom Equals or GetHashCode method. If you're optimising your application to use arrays directly instead of incurring the 'cost' of a List<T> access, you're optimising the wrong thing

You are probably right - but I was talking in general terms. Aaaaaand I had a slight misconception - up until now I was under the impression that List<T> is internally implemented as some kind of a linked list (and yes, I know there is a LinkedList<T> class), but after some decompiling I'm convinced otherwise - it's just arrays internally! Can't believe I'm only checking it out now... Took me long enough, .NET 4.5 on the way....

List<T> has a method called 'BinarySearch' which you can use which internally does a BinarySearch on a regular T array. Performance difference of using List<T>.BinarySearch versus Array.BinarySearch is ~zero.

Yeah, yeah - again: general terms / misconception...
Thanks for the heads up.

I'd nearly go as far as saying that performance is *never* the reason you'd choose an Array over a List regardless of your app.

I can almost agree now - especially because, aside from the fact that List<T> provides convenient add/remove/insert and other logic, Microsoft probably internally optimized it in ways not directly possible in the C# language itself. So, the other general idea in this new context is: don't reinvent the wheel if the one you have works, and works well.

[darwen]

Another consideration is memory.

List (unless you set its capacity) continually doubles the memory it uses when its internal buffer becomes full.

This can lead to large sections of unused memory internally.

Arrays are always the size as requested - so in many circumstances are preferable if you know how big the array is going to be beforehand, or can precompute its size quickly.

Darwen.

[Mutant_Fruit]

Another consideration is memory.

List (unless you set its capacity) continually doubles the memory it uses when its internal buffer becomes full.

This can lead to large sections of unused memory internally.

Arrays are always the size as requested - so in many circumstances are preferable if you know how big the array is going to be beforehand, or can precompute its size quickly.

Darwen.

If you do not know what capacity you actual require, a List<T> is by far the best choice, unless you want to implement resizing logic on raw arrays manually

If you know exactly what capacity you require, you can either create a plain array of the required length or you can create a List with initial capacity equal to the capacity you require. Thus this List would be exactly as efficient as an array, assuming you ignore the 20 byte (or so) memory cost of the List object itself. Which one you use still boils down to whether or not the semantics of a List make more sense in your situation or if a plain array does. If you're filling the thing up and never modifying it again, a plain array might be fine. Alternatively if there will be adding/removing of objects, a List would make more sense.

You can also call List.TrimExcess, or do: list.Capacity = list.Count. Both these methods will result in the internal array being resized to be the exact required size. TrimExcess will only actually do the copy if there is more than 10% wastage, which makes sense. There's no point in doing an expensive reallocation if you're only going to save 1% of the space.

Finally, a little known trick is that both arrays and lists implement IList, so you can do this:

IList<int> myList = new int[50];
or
IList<int> myList = new List<int> (50);

[Ubiquitous]

Thank you all for your input and help. I wanted to make sure that by using List<T> I wasn't picking up a bad habit since it feels more versatile and easier to work with most of the time.