4

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

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);
            }

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

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

4
  • Почитай статьи про фрагментирование листов, как в целом работают листы в дотнете и почему именно так. Commented 8 окт. 2018 в 5:41
  • 1
    Разве это не менее производительно — тут важно уточнить для каких задач, для доступа к элементу по индексу сильно быстрее (константа против линейной зависимости), например. Каждая коллекция имеет свою область применения, надо понимать как они устроены и в каких случаях что применять Commented 8 окт. 2018 в 5:45
  • 1
    Ну и, кстати, если вы заранее знаете верхнюю оценку размеров списка, вы можете создать список нужной размерности сразу и избежать множественного копирования (см. конструктор с capacity) Commented 8 окт. 2018 в 5:47
  • С учетом кэша в процессорах, списки на основе массива рвут в клочья связные списки даже на операцих вставки/удаления в/из середины/начала в большинстве сценариев. Commented 8 окт. 2018 в 11:13

2 ответа 2

6

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

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

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

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

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

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.