Why is the .NET list implemented via an array?

ICollection<T> c = collection as ICollection<T>; if( c != null ) { // if collection is ICollection<T> int count = c.Count; if (count > 0) { EnsureCapacity(_size + count); if (index < _size) { Array.Copy(_items, index, _items, index + count, _size - index); }

Upon reaching the array boundary, the elements are copied to the new array.

Is it not less productive than traditional lists, where a new element is added to the end, and the last penultimate element begins to point to a new element?

  • Read articles about fragmentation of sheets, how do sheets in general work, and why. - ParanoidPanda
  • one
    Is it not less productive - it is important to clarify for which tasks, to access an element by index is much faster (constant versus linear dependence), for example. Each collection has its own scope, you need to understand how they are arranged and in what cases what to use - Andrey NOP
  • one
    Well, by the way, if you know in advance the upper estimate of the sizes of the list, you can create a list of the desired dimension immediately and avoid multiple copying (see constructor with capacity ) - Andrey NOP
  • Given the cache in the processors, array-based lists tear apart connected lists even during insert / delete operations to / from the middle / beginning in most scenarios. - Alexander Petrov

2 answers 2

Working with arrays is faster than with linked lists, in particular, due to the fact that most of the calls to the elements go sequentially to the same or neighboring pages of memory, and the speed of access to memory plays a big role.

In addition, storing data in one piece is convenient for many operations, for example, copying all or part of it.

Related lists consume more memory.

As for the speed with memory reallocation, memory is allocated with a margin, and until the size of the list exceeds the current capacity, no re-allocation occurs. And due to the fact that memory is allocated with a margin of a multiple of times, the amortized complexity per element remains O (1).

For example, with capacity increasing by 2 times and expanding the list to 16 elements:

 Capacity NumOfReallocs NumOfMemoryOperations на текущий момент 1 1 1 2 2 3 4 3 7 8 4 15 16 5 31

    Because the "list" does not imply a "linked list". Use LinkedList , it really uses a linked list and provides O (1) complexity on the insertion of elements.