Why do SortedList and List use array and why is LinkedList not much used?

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 dynam开发者_JAVA技巧ic 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?

---

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.

---

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

---

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.

---

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.