Почему в .NET список реализован через массив, а не через связанный список?

#c_sharp #net

Почему в .NET список реализован через массив?

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


При достижении границы массива, происходить копирование элементов в новый массив.

Разве это не менее производительно, чем традиционные списки, где новый элементы добавляются
в конец, а последний предпоследний элемент начинает указывать на новый элемент?
    

Ответы

Ответ 1

Работа с массивами происходит быстрее, чем со связанными списками, в частности, за
счёт того, что большинство обращений к элементам идёт последовательно, к одним и тем
же или соседним страницам памяти, а скорость доступа к памяти играет большую роль.

Кроме того, хранение данных одним куском удобно для многих операций, например - копирования
всего или части.

Связанные списки расходуют больше памяти.

Насчёт скорости при реаллокации памяти - память выделяется с запасом, и пока размер
списка не превысит текущую ёмкость, перевыделения не происходит. А за счёт того, что
память выделяется с запасом в кратное число раз, амортизированная сложность в расчёте
на один элемент остаётся O(1).

Например, при росте ёмкости в 2 раза и расширении списка до 16 элементов:

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


Ответ 2

Потому что "список" не подразумевает "связный список". Используйте LinkedList, он
действительно использует связный список и обеспечивает сложность O(1) на операциях
вставки элементов.