Что находится внутри List под капотом в C#
Что проверяют
Понимаете ли вы, что за удобной коллекцией стоит обычный массив, и умеете ли считать стоимость операций. Следующий вопрос почти всегда про то, когда этот тип брать не надо.
Как отвечать
Внутри лежит массив элементов, счётчик реально занятых ячеек и счётчик изменений. Отсюда первое различие: Count это число элементов, Capacity это длина массива, и они обычно не равны.
Конструктор без аргументов память не выделяет, он подставляет общий пустой массив. Первый Add выделяет небольшой блок, дальше при исчерпании ёмкости создаётся массив вдвое больше и содержимое копируется. Из этого выводится вся стоимость:
- добавление в конец: в среднем константа, но отдельные вставки платят за копирование всего содержимого;
- обращение по индексу: константа;
- вставка и удаление в середине: линейно, потому что хвост сдвигается;
Contains,IndexOf,Remove: линейный перебор.
Если размер известен заранее, ёмкость задают в конструкторе или через EnsureCapacity, и серия перевыделений исчезает. Счётчик изменений нужен, чтобы правка коллекции прямо внутри foreach бросала исключение, а не портила обход молча.
Плюсом скажите, что тип не потокобезопасен: для параллельной работы берут коллекции из пространства конкурентных или внешнюю блокировку. И что для структур индексатор возвращает копию, поэтому изменить поле элемента прямо в списке нельзя, для этого есть доступ к внутреннему буферу через span.
Где спотыкаются
Называют это связным списком. Связный список здесь отдельный тип, и на практике он проигрывает почти всегда: непрерывный массив дружит с кэшем процессора, а список из узлов гоняет память впустую.
Второе: объясняют просадку при росте фрагментацией памяти. Цена в другом: старые массивы становятся мусором и нагружают сборщик, а массив крупнее восьмидесяти пяти килобайт попадает сразу в кучу больших объектов, которая почти не уплотняется.
Третье: считают, что удаление стоит константу, а Clear освобождает память. Удаление сначала ищет элемент перебором, потом сдвигает хвост, а очистка только обнуляет счётчик, оставляя выделенный массив на месте. Ёмкость возвращает TrimExcess.