Difference between List<T> and LinkedList<T>

We use List whenever we need a list. I notice now tha开发者_Python百科t there is a LinkedList.

I was wondering what was the difference between these 2, and when you should use one over the other.

Well, List<T> is basically backed by an array which is usually bigger than the current number of items. The elements are put in an array, and a new array is created when the old one runs out of space. This is fast for access by index, but slow at removing or inserting elements within the list or at the start. Adding/removing entries at the end of the list is reasonably cheap.

LinkedList<T> is a doubly-linked list - each node knows its previous entry and its next one. This is fast for inserting after/before a particular node (or the head/tail), but slow at access by index.

LinkedList<T> will usually take more memory than List<T> because it needs space for all those next/previous references - and the data will probably have less locality of reference, as each node is a separate object. On the other hand, a List<T> can have a backing array which is much larger than its current needs.

A List<T> is actually an array, meaning that its Add operation is O(1) at the end and O(n) at the front, but you can index into it in O(1). A LinkedList<T> is, as it says, a linked list. Since it's doubly-linked, you can add items to the front or back in O(1) but indexing into it is O(n).

In almost all scenarios a List is going to outperform a LinkedList. Real world results often differ with Big O Complexity Theory.