5

In my mind, List is basically implemented using LinkedList, while a normal Array is implemented as contiguous blocks. I always used List because it is in the Generic namespace and because I thought it used dynamic memory allocation - but I was wrong.

Yesterday I saw the implementation of List using Reflector and found it is actually an array of T(T[]). There are lots of Array.Copy around while manipulating each element in the List. For instance, when you use Insert, it will create a new memory and copy all the elements before/after the inserted elements. So it seem to me the use of List is very expensive.

I saw the SortedList as well. I am not sure why a SortedList also implements an array inside it. Don't you think SortedList would be horrible to use an array as you need to sort the list every time a minor manipulation to the List occurs?

I also wonder why List is so popular as most people use it rather than going for LinkedList. Is it only because of the flexibility of the indexer?

Improve this question
3
  • 6
    Look closer: List<> does not create a new array and copy all items on each call. The array is only resized when it's full, and it's resized to twice it's original size. The resizing occurs only at exponentially increasing intervals when continuously adding items. Commented Sep 13, 2010 at 19:36
  • 2
    There's not correct answer to this question. Think about either be more specific or mark as wiki Commented Sep 13, 2010 at 19:36
  • @dtb yes it uses this._items[this._size++] = item; Yes it exponentially increasing intervals, but how does it always ensure that size++ does have an empty space ? Commented Sep 13, 2010 at 19:42

4 Answers 4

Reset to default
16

The biggest reason is modern computer design. The CPU cache is very important because RAM is so slow. The memory bus design just couldn't keep up with the rapid advances in CPU clock speeds. Making a high frequency digital signal travel more than an inch is very difficult.

An array has unbeatable cache performance, it very likely that the next element is already in the cache when you iterate it. A linked list gives low odds that this is the case, the next item is essentially at a random address when items are added at a low rate. That's expensive, it stalls the processor, waiting for the RAM to catch up. Can be hundreds of cycles.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes, SortedList really looked to me expensive. I think I got my answer from you. So the point is : Array => Good because very next element is available instantly, giving away less workload to CPU. LinkedList => Good when insert in middle, Not often required for me too. SortedList => Very expensive, should be avioided.
+1 very good point/explanation. And don't forget that you're even more slow if you have to access to previous element address when you need the next :)
@abhishek: SortedList has a different purpose. It is an associative collection (Key-Value), it is sorted by key and it has a quite fast O(log n ) key lookup.
3

Because most collections don't need insertions into the middle often. But they do need directly access via an indexer.

Improve this answer

1 Comment

nailed it :) The best reason. Also, a List<T> is much simpler to use and understand.
2

If you want an in-memory collection of a single-type for which:

  1. The collection must be growable.
  2. The most common mutation operation is appending an item to the end of the collection.
  3. Fast retrieval by index is essential.

then List<T>is probably your best choice. LinkedList<T>may be a better choice when (2) and (3) do not apply.

Improve this answer

Comments

1

In real life List doesn't call Array.Copy often, usually you just append items to array, not insert. It's a purpose of List, in contrast to a linked list. You just should to choose a proper collection class.

If you insert items often use linked list. If you mostly add items and need to iterate them effectively, use List.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.