C# List vs LinkedList vs Array

262

15 марта 2017, 15:43

List vs LinkedList vs Array

В каких случаях что лучше использовать?

C#-FAQ вопрос полезный для прохождения собеседований, а так же весьма полезен с теоретической точки зрения. Не закрывать. По крайней мере до того, как дам более полноценный ответ (уж потерпите пару дней до правки ответа, если уже на столько хочется гдето поставить реквест на закрытие)

Answer 1

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

Короткие выводы:

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

Детальные выводы:

желтый фон -- важные пункты в практическом большинстве ситуаций.
красный фон -- плохой результат.
зеленый фон -- хороший результат.
светлозеленый -- удовлетворительный.

Детали тестов:

И немного информации, которую просто интересно узнать:

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

ВАЖНО Если кто нашел ошибки -- укажите пожалуста в коментариях. Независимо от того, ошибки в коде, или в моих тестах, или моих выводах. :)