ArrayList internal implementation

Question

Hopefully this is not a duplicate.

Before anything, I know ArrayList are not the best choice but this is just curiosity.

Simply, I was wondering about the implementation of ArrayList. I looked and figured out it uses an array for storage.

For array, when you have:

int [] arr;

arr points to the first element of the array and because it is typed as integer, the compiler knows where to jump:

arr[2] => arr value + 2 * typeof(int) = address of arr[2]

Now, since ArrayList are typeless, I was wondering how the compiler can figure out where is the next item. I would guess there is an overhead that tells what is the data so that the compiler can perform the pointer arithmetic.

As a result, ArrayList should be way slower than any other typed collection since it cannot just jump to the data as it needs to know what is before. This would be quite similar to LinkedList.

Answer 1

An ArrayList only contain references to the objects, not the objects themselves. All references are the same size, so the problem doesn't exist.

The internal type of the reference is surely object.

For generic arrays of value types, the actual value is stored in the array and the size of the element is used as you describe. If you put a value type in an ArrayList it will be boxed into an object and the reference to that object is stored in the ArrayList.

Answer 2

For arrays of struct, the size of each element is known.

For arrays of reference types, the array stores the references ( pointers ) to the actual objects, which live in the heap.

The size of a pointer is known as well: 4 bytes on x86 and 8 bytes on x64.

So, the pointer arithmetic is always easy and fast.

In the case of ArrayList, the internal storage is a object[], so the implementation is not optimal for storing value types as they will be boxed and stored in the heap too.

Answer 3

Okay, you asked what the implementation of an arrayList is, here it is : arraylist.cs

Straight from Microsoft no less. This is the Roslyn implementation.