C# List vs LinkedList

Thinking of a linked list as a list can be a bit misleading. It's more like a chain. In fact, in .NET,LinkedList<T> does not even implement IList<T>. There is no real concept of index in a linked list, even though it may seem there is. Certainly none of the methods provided on the class accept indexes.

Linked lists may be singly linked, or doubly linked. This refers to whether each element in the chain has a link only to the next one (singly linked) or to both the prior/next elements (doubly linked).LinkedList<T> is doubly linked.

Internally, List<T> is backed by an array. This provides a very compact representation in memory. Conversely, LinkedList<T> involves additional memory to store the bidirectional links between successive elements. So the memory footprint of a LinkedList<T> will generally be larger than forList<T> (with the caveat that List<T> can have unused internal array elements to improve performance during append operations.)

They have different performance characteristics too:

Append

• LinkedList<T>.AddLast(item) constant time
• List<T>.Add(item) logarithmic time

Prepend

• LinkedList<T>.AddFirst(item) constant time
• List<T>.Insert(0, item) linear time

Insertion

• LinkedList<T>.AddBefore(node, item) constant time
• LinkedList<T>.AddAfter(node, item) constant time
• List<T>.Insert(index, item) linear time

Removal

• LinkedList<T>.Remove(item) linear time
• LinkedList<T>.Remove(node) constant time
• List<T>.Remove(item) linear time
• List<T>.RemoveAt(item) linear time

Count

• LinkedList<T>.Count constant time
• List<T>.Count constant time

Contains

• LinkedList<T>.Contains(item) linear time
• List<T>.Contains(item) linear time

As you can see, they're mostly equivalent. In practice, the API of LinkedList<T> is more cumbersome to use, and details of its internal needs spill out into your code.

However, if you need to do many insertions/removals from within a list, it offers constant time. List<T>offers linear time, as extra items in the list must be shuffled around after the insertion/removal.

Src: http://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist