SortedList - VS - List - VS - LinkedList

Question

In my mind it was always there that List is basically implemented using LinkedList, while normal Array is implemented as Contiguous blocks. I always tried to use List because of it is made using Generic and also might have the power of Dynamic Memory Allocation. But I was wrong.

Yesterday I saw the implementation of List using Reflector and found it is actually a 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 Insert 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 of the people use it rather than going for LinkedList as most of the times we neeed to manipulate a List and Bind the list for only once. Is it only because of the flexibility of Indexer ?

What do you think ?

Answer 1

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

Answer 2

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.

Answer 3

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 4

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.