List<T> or LinkedList<T>

Question

I need a data structure that holds a list of elements of the same type. Needed features are

• Add
• GetEnumerator
• (may be) Clear

An indexed access, sorting, searching, removing of elements are not required. What is the best collection class for it? The following aspects should be taken in consideration: performance, memory usage, behavior of the garbage collector.

My current candidates are List<T> and LinkedList<T>

Answer 1

Unless you are dealing with a massive structure or you plan on iterating over this thing a trillion times, it doesn't matter. Just pick one and start coding. If your app slows to a crawl later, figure out why then and change as necessary.

(Seriously, it does. not. matter. In the slightest. Every minute you spend on finding the answer to this question is a minute closer you could've been to having working code).

If anyone has gotten to the point where they need to know the difference, LinkedList is faster than List and could be used if you only need non-random, forward-only reading and appending functionality.

Answer 2

Short answer
default to using List<T> in almost all cases.

Slightly longer answer
LinkedList<T> is only going to be better if you are doing a lot of adding and removing values in comparison to enumerating over those values and the size of the list is large. This should only be a factor in your choice if, subsequent to profiling you find using List<T> is a problem.

Longer answer

Assumption, you have identified the usage of one or the other as being a problem for performance.

It you do a lot of random access then List<T> will almost always be vastly faster no matter what. If you enumerate a lot and rarely insert (or almost always insert near/at the end) the List<T> will almost always be faster. If you are constantly inserting/removing in random locations but while iterating over the list so are already at or near the relevant node and will have at least several thousand elements you may want to try LinkedList<T>

Working out what values/usage translate to better performance are very much dependent on your usage profile. Microbenchmarks can be very misleading here since they brush under the carpet aspects of the linked lists behaviour like the nodes in in being distributed about in memory rather than nicely adjacent if they happen to get allocated all at once in your tests. Likewise pre-creating the List<T> with the right size can make a big difference.

As to computer science style reasoning and big O notation (which really need big N's to be meaningful in this case)

• operation
  • cost List<T>
  • cost LinkedList<T>
• insert at end
  • O(1) (amortized cost, allocation to double size as needed)
  • O(1) allocation each time
• insert at start
  • O(N) (though done as fast memory move so somewhat complex running time behaviour)
  • O(1)
• insert in location x (and remove as well)
  • O(N-x) (see comment for insert at end)
  • O(1)
• forward enumeration
  • O(N) (though cache misses minimized)
  • O(N) (though heavily dependent on cache locality)
• reverse enumeration
  • O(N)
  • O(N) (the LinkedList<T> implementation is doubly linked)
• random access
  • O(1)
  • O(N)

Memory usage is complex since List can have at most Count - 1 excess cells at any point but LinkedList<T> will consume a LinkedListNode<T> for each cell which is an additional 3 references (4/8 bytes a pop) plus the usual object overhead. In normal usage the List is likely to win but again this should only be something you worry about if you find the memory consumption is actually a problem.