List <> elements are sequentially arranged in an array with a bunch?

Question

I am learning C # and basically know the difference between arrays and List , that the latter is generic and can grow dynamically, but I wonder:

• are List elements sequentially located in an array with a bunch, or is each element "randomly" in different places?
• and if so, does it affect the speed of access and retrieval of data from memory?
• and if so, is that what makes arrays a little faster than List s?

Answer 1

First, consider the second and third questions:

and if it really affects the speed of access and retrieval of data from memory?

and if true, what makes the array a little faster than the list?

In .NET, there is only one type of "native" collection (with .NET, I mean CLR, so the runtime): an array (technically, if you consider the string type to be a collection type, then there are two types of collection types :-)) ( technically part 2: not all arrays, which, in your opinion, are arrays, are “native” arrays ... Only arrays based on monomeric 0 are “native” arrays. There are no arrays of type T[,] , but arrays where the first element has no index 0, are not). Another collection is built on it (except LinkedList<> ). If you look at List<T> using IlSpy , you will see that there is T[] in the database with an added int for Count ( T[].Length is Capacity ). Obviously, the array is a little faster than List<T> , because to use it you have one less indirectness (you are accessing the array directly, not accessing the array that accesses the list).

Let's look at the first question:

Does it contain elements sequentially located in an array with a bunch, or each element is randomly located in different places?

Based on the array inside, it is clear that List<> remembers its elements, such as an array, therefore in an adjacent memory block (but keep in mind that with List<SomeObject> , where SomeObject is a reference type, the list is a list of links , not objects , so links are placed in a continuous memory block (we will ignore this using advanced computer memory management, the word "continuous memory block" is not exact ", it would be better to say" adjacent address block "))

(yes, even Dictionary<> and HashSet<> built on top of arrays. Conversely, a tree-like collection can be built without using an array, since it looks more like a LinkedList )

Additional information: in CIL there are four groups of instructions (an intermediate language used in compiled .NET programs) that are used with native arrays:

• Newarr

• Ldelem and the Ldelem_* family

• Stelem and the Stelem_* family Stelem_*

• ReadOnly (don't ask me about usage, I don't know, and the documentation is not clear)

if you look at OpCodes.Newarr , you will 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. 

Answer 2

Yes, the items in the list are stored contiguously, like an array. The list actually uses arrays inside, but these are implementation details that you really don't need to worry about.

Of course, to get the right impression of this statement, you also need to understand a bit about memory management in .NET. Namely, the difference between value types and reference types and how objects of these types are stored. Value types will be stored in continuous memory. With reference types, references will be stored in contiguous memory, but not the instances themselves.

The advantage of using a list is that the logic inside the class handles the selection and management of elements for you. You can add items anywhere, delete items from anywhere, and increase the entire size of the collection without having to do any extra work. This, of course, is also what makes the list a bit slower than the array. If any redistribution has to happen in order to fulfill your request, success will be achieved, since a new array of a larger size will be allocated and the elements will be copied to it. But it will not be slower than if you wrote the code to do it manually using an raw array.

If your length requirement is fixed (i.e. you never need to increase / expand the total capacity of the array), you can go ahead and use a raw array. It can even be a little faster than a list, as it avoids the extra overhead and indirectness (although it can be optimized by the JIT compiler).

If you need to dynamically resize the collection or if you need any other functions provided by the List class, just use List. The difference in performance will be almost imperceptible.