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

Question

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?

Answer 1

Yes, SortedList is O(n) for inserts. Use carefully.

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 very small odds that this is the case, the next item is essentially at a random address. That's expensive, it stalls the processor, waiting for the RAM to catch up. Can be hundreds of cycles.

Answer 2

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

Answer 3

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.

Answer 4

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.