C# List vs LinkedList vs Array

List vs LinkedList vs Array
В каких случаях что лучше использовать?
C#-FAQ вопрос полезный для прохождения собеседований, а так же весьма полезен с теоретической точки зрения.

Ответ

Я сделал некоторые тесты. Думаю, многим будет интересно посмотреть на результаты. Исходники тестов по линке: https://github.com/ukushu/DataStructuresTests.git

Короткие выводы:
Array нужно использовать:
Максимально часто, если это возможно (быстродействие и оптимальность памяти) Если не нужно добавлять ячейки Если ожидаемый вес < 85000b Если нужна Random Access Speed List нужно использовать:
Если нужно добавлять ячейки в конец списка (в большом/малом количестве) Если нужно добавлять ячейки в начало/середину списка (в малом количестве) Если ожидаемый вес < 85000b Если нужна Random Access Speed Предпочтительно инициализировать с уже набранным количеством элементов, если это возможно. LinkedList
Если нужно добавлять ячейки в начало/середину/конец листа в большом количестве Если нужен только последовательный доступ (не нужны индексы для random access) Хорошо подходит для хранения увесистых обьектов в относительно небольшом количестве т.к. под каждую ячейку так же нужно выделять память на 2 ссылки.

Детальные выводы:
светлокрасный фон -- плохой результат. желтый фон -- нормальный(средний) результат. светлозеленый фон -- хороший результат.


И немного информации, которую просто интересно узнать:
LinkedList внутри вообще не является List в языках .NET. LinkedList. Он даже не реализован на IList. Вот почему там нет индексов и методов, которые связаны с индексами. LinkedList - это node-pointer based collection. В .NET это реализовано в doubly linked implementation, то есть каждый элемент ссылается на предыдущий и последующий за ним. А так же то, что данные будут фрагментированы. Разные объекты в листе будут находится в разных местах оперативной памяти. Так же это значит, что будет использовано больше памяти под LinkedList чем под List или Array, как и видно из тестов. Array как и List (в .Net - это враппер вокруг Аrray с возможностью изменения размера) резервируют память оперативки как один продолжительный блок. Если общий размер элементов размер > 85000 bytes, он будет переразмещен в Large Object Heap. Что в свою очередь может привести к heap fragmentation -- что-то вроде легкой формы memory leak. List в памяти будет занимать значительно меньше памяти, если его создавать не пустым, а приблизительно наперед нужного размера. То есть, если вы ожидаете что в листе должно быть 1000 ячеек, то он будет занимать как массив данных с 1000 ячеек. Если же вы его создали пустым и заполнили до количества в 1000 ячеек, он будет занимать больше, как показано в тестах.
ВАЖНО Если кто нашел ошибки -- укажите пожалуста в коментариях. Независимо от того, ошибки в коде, или в моих тестах, или моих выводах. :)