Are List<> elements sequentially located in heap like array?

Question

I'm learning C# and basically know the difference between arrays and Lists that the last is a generic and can dynamically grow but I'm wondering:

• are List elements sequentially located in heap like array or is each element located "randomly" in a different locations?
• and if that is true, does that affect the speed of access & data retrieval from memory?
• and if that is true, is this what makes arrays a little faster than Lists?

Answer 1

Let's see the second and the third questions first:

and if that true does that affect the speed of access & data retrieval from memory ?

and if that true is this what makes array little faster than list ?

There is only a single type of "native" collection in .NET (with .NET I mean the CLR, so the runtime): the array (technically, if you consider a string a type of collection, then there are two native types of collections :-) ) (technically part 2: not all the arrays you think that are arrays are "native" arrays... Only the monodimensional 0 based arrays are "native" arrays. Arrays of type T[,] aren't, and arrays where the first element doesn't have an index of 0 aren't) . Every other collection (other than the LinkedList<>) is built atop it. If you look at the List<T> with IlSpy you'll see that at the base of it there is a T[] with an added int for the Count (the T[].Length is the Capacity). Clearly an array is a little faster than a List<T> because to use it, you have one less indirection (you access the array directly, instead of accessing the array that accesses the list).

Let's see the first question:

does List elements sequentially located in heap like array or each element is located randomly in different locations?

Being based on an array internally, clearly the List<> memorizes its elements like an array, so in a contiguous block of memory (but be aware that with a List<SomeObject> where SomeObject is a reference type, the list is a list of references, not of objects, so the references are put in a contiguous block of memory (we will ignore that with the advanced memory management of computers, the word "contiguous block of memory" isn't exact", it would be better to say "a contiguous block of addresses") )

(yes, even Dictionary<> and HashSet<> are built atop arrays. Conversely a tree-like collection could be built without using an array, because it's more similar to a LinkedList)

Some additional details: there are four groups of instructions in the CIL language (the intermediate language used in compiled .NET programs) that are used with "native" arrays:

• Newarr

• Ldelem and family Ldelem_*

• Stelem and family Stelem_*

• ReadOnly (don't ask me its use, I don't know, and the documentation isn't clear)

if you look at OpCodes.Newarr you'll see this comment in the XML documentation:

// Summary:
//     Pushes an object reference to a new zero-based, one-dimensional array whose
//     elements are of a specific type onto the evaluation stack.