43

We use List whenever we need a list. I notice now that there is a LinkedList.

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

Shiraz Bhaiji
  • 62,289
  • 31
  • 137
  • 240

3 Answers3

95

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.

Jon Skeet
  • 1,335,956
  • 823
  • 8,931
  • 9,049
  • is it true LinkedList holds more values than List – Shrivallabh Apr 02 '13 at 11:37
  • @Shrivallabh: What do you mean by "holds more values"? That will depend on the context, version of the CLR you're using etc. Unless you're planning on storing a *huge* number of elements, it's very unlikely to be relevant. – Jon Skeet Apr 02 '13 at 11:57
  • I have application where i need to read huge text files and the ID in each line i have to store so asking LinkedList is better or List – Shrivallabh Apr 03 '13 at 03:57
  • @Shrivallabh: How big is "huge"? How many lines? Bear in mind that `List` may be more *efficient* in memory use - especially if you know the eventual number of entries ahead of time. – Jon Skeet Apr 03 '13 at 05:49
  • I don't know the count, the file is around 20 to 40 GB and every line has ID. – Shrivallabh Apr 03 '13 at 08:53
11

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).

Gabe
  • 82,547
  • 12
  • 135
  • 231
  • 4
    Not sure where you get Add being O(log n) - I'd expect it to be amortized constant time. – Jon Skeet Nov 25 '10 at 16:24
  • Jon: You're probably right. I guess I was trying to do some averaging between O(1) at the end and O(n) at the beginning. – Gabe Nov 25 '10 at 17:17
2

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

MattE
  • 954
  • 1
  • 11
  • 25
  • Why did this get downvoted? It's true. Look at this post https://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist. I've found many other people on different sites that obtain the same results as the one in this post. In almost NO case is a linked list better than a generic list in practice. – MattE Mar 20 '19 at 13:13