3

I was asked in a .net interview the significance of linkedlist in .net. I answered that linkedlist is used where you have to do a lot of inserts, but I have never had to use linkedlist in any of the code I wrote. The interviewer then told me that all the lists in .net use linkedlist as its underlying type. When I came home, I couldn't find anything online to support his statement. Can anyone comment on the validity of his statement?

Foo
  • 4,206
  • 10
  • 39
  • 54
  • 5
    The interviewer was wrong, could have been bait. – H H Jul 15 '13 at 21:06
  • 5
    The interviewer is wrong - `List` uses an array (`T[]`) as the underlying storage type. – D Stanley Jul 15 '13 at 21:06
  • This is a pretty good comparison as well. http://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist – Dennis Rongo Jul 15 '13 at 21:11
  • This may be true in a very conceptual sense: when you're running on the metal and you need to increase or delete elements arbitrarily, a linked list would be practical. However, when you're talking about .Net, a List is not a LinkedList. – Reacher Gilt Jul 15 '13 at 21:12

3 Answers3

6

I think your interviewer simply wrong. LinkedList, by definiiton, is a list of entites connected with each other, so in order to get to some item X, you need traverse all the list, all along til that item. There is no way you can access that item via index(just an example). LinkedList is just a different datastructure, and for sure it wasn't used on all BCL list types.

It's very convenient choice when your going to have linked enitities and consume small memory (no additional data need other then pointer to neighbor), but you pay a cost of traversal/picking/removing/updating speed on it.

Tigran
  • 61,654
  • 8
  • 86
  • 123
  • _"There is no way you can access that item via index"_ except by traversing the linked list from the first element to the next `n` times. – Cédric Bignon Jul 24 '13 at 00:40
4

Sounds like BS to me. If you use reflection or check the .net / mono source code you can see they use an array as base type:

private T[] _items;
dsfgsho
  • 2,731
  • 2
  • 22
  • 39
2

MSDN says That the c# List<T> is like an ArrayList

The List class is the generic equivalent of the ArrayList class. It implements the IList generic interface using an array whose size is dynamically increased as required.

This implies that the plain List<T> is not a linked list.

Sam I am says Reinstate Monica
  • 30,851
  • 12
  • 72
  • 100