In an object of type List<T>, does accessing an object by index run through each item in the list, or does it use a much faster approach?

For example:

List<MyClass> myList = new List<MyClass>();
...
// add lots of members...
...
MyClass myClass = myList[25];

Will asking for index 25 take much longer than asking for index 1, or 开发者_如何学编程does it use some quick algorithm to jump straight to the 25th item?

Thanks!

Internally List<T> is implemented as array (which grows when you're adding new items) so accessing of n-th element will be O(1) operation. (Therefore there will be no difference in speed between getting myList[1] and myList[25].)

Excerpt from the List<T>.Item property documentation:

Retrieving the value of this property is an O(1) operation; setting the property is also an O(1) operation.

I can imagine how slow would be .NET applications if List<T> had to jump through all items before getting n-th...

From the Item property of List<T>

Retrieving the value of this property is an O(1) operation; setting the property is also an O(1) operation.

No, it's very fast. In fact it's not an algorithm at all*; the backing store for List<T> is just a T[] array; so all it has to do is jump to a known location in memory.

In abstract terms, think of it like this: since the elements of an array reside in a contiguous block of memory, you can imagine the array as a number line. Does it take you any longer to find "10" on a number line than "1"? No -- you know exactly how the numbers are laid out, so all you have to do is look straight at 10. You don't have to scroll your eyes through 1, 2, 3, etc., in other words.

Granted, that's a highly non-technical analogy; but it's pretty consistent with how accessing an element of an array works.

_{*A calculation is required, yes: the address of the first element in the array plus the product the element size with the index. But to call this an "algorithm" would be a stretch; and anyway, it is a constant-time operation regardless.}

No, removing and insertion on the other hand is dependent on where you remove an element, since it is a dynamic array.

http://en.wikipedia.org/wiki/Dynamic_array

List<T> uses T[] internally so indexing is supported directly by the underlying data structure.