Link to home
Start Free TrialLog in
Avatar of Mr_Fulano
Mr_FulanoFlag for United States of America

asked on

Array vs. List, which is a better option?

Hi, I'm using C#.NET 2010. I have a project, where I'm going to have to use either an Array or a List to store values.

My question is, which is better and why? I understand that a List offers the advantage of not having to pre-declare the size, where a Non-Mutable Array has a fixed size. Barring that, why would one option be better than the other?

Is one more efficient than the other?

Thanks,
Fulano
SOLUTION
Avatar of Bob Learned
Bob Learned
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
I love a little course correction *BIG GRIN*.
Avatar of Mr_Fulano

ASKER

Hi Kaufmed, I'm a little confused about what you're saying...when you say:

"The algorithm for growing the internal storage (which is an array itself, IIRC) of a List is that it doubles its capacity whenever it reaches capacity."

What "capacity" are you referring to? In a List one doesn't specify the size, so how would it know it has reached capacity?

I'm also assuming this is what you're referring to when you speak about Array's having a smaller footprint.

Fulano
What "capacity" are you referring to?
A List has a Count--the number of items it is actually holding--and it has a capacity--the maximum number of items it can hold. It's like have a 5 gallon jug that's only filled with 3 gallons of water. The "Count" of the jug is 3; the "capacity" of the jug is 5. You don't see the capacity of the List because the internal storage is not accessible by your code.

In a List one doesn't specify the size, so how would it know it has reached capacity?
The List manages capacity itself so you don't have to. However, you can manually adjust the capacity if you prefer. In an array, you have to manage the capacity. If you fill the array, but you want to append more items, you have to allocate a new, larger array and copy the items from the existing array to the new array. A List does this internally, and it does so during the call to Add. If the List is at capacity, then internal to Add, the capacity is doubled by means of a new array, and the existing items are copied from the old array to the new array. You wouldn't be cognizant of when this was happening. [OK, you could probably calculate it, but if you were going to go to that much trouble, why not just use an array  ; )   ]

I'm also assuming this is what you're referring to when you speak about Array's having a smaller footprint.
Well since a List has an array internally, it automatically has at least the same amount of "stuff". But since you have additional ways (methods) to interact with the list, and additional properties and such, there is more stuff associated with a List than there is with an array.
P.S.

I'm not sure I am permitted to post decompiled Framework source code, but you can easily inspect the code for a List (and the Array class) using something like dotPeek or JustDecompile.
P.P.S.

I just realized I contradicted myself. You can see the capacity of the list via the Capacity property. As I mentioned, the List will adjust its capacity as needed whenever you add items and its internal storage is at capacity. It will do this within the Add method. AFAIK, the List will never shrink of its own accord. You would shrink the capacity of the List by assigning a smaller value to the Capacity property, and you could only do so if the Count of items was less than the new Capacity value (otherwise you'll receive an exception).
Kaufmed, very interesting explanation. Thank you! - So, in the end, my take away is that its really a matter of preference. I can either use an Array or a List, depending on which I like to use more. The performance difference is somewhat negligible.

I guess the only question that still haunts me is why would anyone want to use and Array if a List is so much more "user-friendly."

Thanks,
Fulano
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
My turn *GRIN*

A List however is stored as a linked list (binary tree), a series of elements that point one to the other. If you need to retrieve an element, the system has to navigate the whole list up to the 123th element. This takes longer.

You can post framework code, as it is not licensed code, and freely available to anyone with a decompiler.

List<T> stores elements in an array of T.  Here is the field definition from the List<T> class (using JustDecompile):

 private T[] _items;
Let's just say that the List<T> class is a wrapper around an array.  That is pretty cool, since it handles the memory allocation, searching, etc.  

There is a difference between length and capacity.  Length is the number of items stored, and capacity is the number of available "slots" for items storage.  If you know ahead of time that you are going to be adding a lot of items, then you can have the list allocate a larger array capacity.

There are a few constructors for the List<T> class, and one takes an integer for the initial capacity.  Another takes an array of items.  Going between an array and List<T> instance is pretty easy:

List<T> constructor takes an array of T
List<T>.AddRange method takes an array of T
List<T>.ToArray method returns an array of T
Advantages on List:
1. Item adding into the list<string> as per type.
2. While insertion of item between/or specific index dimension will extend and auto re-arrage
3.Delete item would same as point 2
4.we can add multiple items to list by array input(AddRange)
5.we could bind list as Datasource
6.we could iterate by for as well as for each
7.sorting is possible
8.we can use LINQ on list
9.List<CustomClass> possible
10.Strongly typed

On Array has limitations on above specified most of the features
@srinipro

1. Same for array
2. Agree, provided by "re-arrange" you mean elements are copied to new storage, and not moved around (sorted) in some way--this must be invoked manually by calling the Sort method.
3. Disagree (see my previous comment)
4. Agree.
5. Array can be used in this manner as well.
6. Same for array.
7. Same for array--you just have to write the logic to do so (external function). (I suppose you meant that List already provides a mechanism for sorting which you don't have to write.)
8. Same for array.
9. CustomClass[] is possible.
10. Same for array (see #9).
@Mr_Fulano,

I have to be honest:  I had to search for this. I've been using generics for so long, that I couldn't really think of any solid reason to use an array. (Perhaps for interoperability?) You can even find MS folks who prefer generics over "old-shool" arrays. Perhaps you could run into performance issues when using a generic, but I think you'd have to be doing some pretty intense computation for that. Even then, if you decide to work with an array you have to think:  MS put the code for generics through a good bit of testing (let's hope!) before they shipped the Framework. How much testing are you going to be able to do with an array implementation you write?

The only solid example I could think of for using arrays would be if you were going to write your own generic collection. As has been mentioned, a List uses an array for its internal storage. An array can also be used easily as a Heap (thank you Computer Science class!), so you could write your own Heap collection using an array for your internal storage. There's nothing to stop you from using one of the Framework generics for your internal storage, but you would be adding another layer (invisible to users of your creation) to the collection you are creating.
@TheLearnedOne

Array vs Linked List.

We are both right. I was a little short in my description.

According to sources at Microsoft, that explained a few years back durint a DevDays how most collections are implemented in .NET, the data is, as you say and as described in a few places in the documentation, saved in an array. This makes things easier for the garbage collector.

However, so as not to incur the penalty that inserts and removes involve, the thing is treaded internally as a linked list. When you access an element, it goes through a linked list that holds a pointer or the real index (I do not remember which).

In fact, it is the best of both worlds. You have the speed of an array on storage, but the advantages of a linked list as far as data manipulations are concerned. This is one of the reasons why collections need to provide GetEnumerator. If they were treated as arrays, the enumerator would not be needed.

The difference in performance can be felt however. I had to consult a couple of years ago with actuaries at the government who deal with statistics out of census data covering 100 years. That is a huge amount of data. They had some routines developped for them by a consultant that did everything in collections, although they do not manipulate the data, they only made calculations on it. The thing was taking hours. We moved the data into arrays and without changing anything else, we brought it down to about 10 minutes.
I love a little course correction (revisited) *BIG GRIN*.

Thanks, James!!
Gentlemen, very sorry for the delay. I was away and could not reply. However...WOW, what a great discussion. You've ALL been extremely helpful and have all contributed with such good advice. -- This is one of those times that I wish the point awards were unrestricted or at least far more than 500 points, but I'll so my best to award them in a just manner.

THANK YOU all for such good advice!!!

Fulano
One of the best discussions I've had here on EE in years. EXCELLENT!!!