Список <T>или LinkedList <T>

Question

Мне нужна структура данных, которая содержит список элементов одного типа. Необходимые функции

• Добавить
• GetEnumerator
• (может быть) Очистить

Индексированный доступ, сортировка, поиск, удаление элементов не обязательны . Какой класс коллекции лучше для него? Следующие аспекты должны быть приняты во внимание: производительность, использование памяти, поведение сборщика мусора.

Мои нынешние кандидаты List<T> и LinkedList<T>

Answer 1

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

(Серьезно, это не так. Неважно. В любом случае. Каждая минута, которую вы тратите на поиск ответа на этот вопрос, на минуту ближе к тому, что вы могли бы иметь рабочий код).

Если кто-то дошел до того, что ему нужно , чтобы узнать разницу, LinkedList работает быстрее, чем List, и его можно использовать, если вам нужны только функции случайного чтения и добавления только для пересылки.

Answer 2

Краткий ответ
по умолчанию используется List<T> почти во всех случаях.

чуть более длинный ответ
LinkedList<T> будет лучше, если вы будете много добавлять и удалять значения по сравнению с перечислением этих значений, а размер списка велик. Это должно быть фактором вашего выбора, только если после профилирования вы обнаружите, что использование List<T> является проблемой.

Более длинный ответ

Предполагается, что вы определили использование одного или другого как проблему для производительности.

Если вы делаете много произвольного доступа, тогда List<T> почти всегда будет значительно быстрее, несмотря ни на что. Если вы много перечисляете и редко вставляете (или почти всегда вставляете около / в конце), List<T> почти всегда будет быстрее. Если вы постоянно вставляете / удаляете в случайных местах, но во время итерации по списку уже находитесь в соответствующем узле или рядом с ним и в нем будет как минимум несколько тысяч элементов, вы можете попробовать LinkedList<T>

Определение того, какие значения / использование приводят к повышению производительности, очень сильно зависит от вашего профиля использования. Микробенчмарки могут быть здесь очень вводящими в заблуждение, поскольку они скрывают такие аспекты поведения связанных списков, как узлы при распределении в памяти, а не прилегающие друг к другу, если они оказываются распределенными сразу в ваших тестах. Аналогично, предварительное создание List<T> с правильным размером может иметь большое значение.

Что касается рассуждений в стиле информатики и больших обозначений O (которым действительно нужны большие N, чтобы иметь смысл в этом случае)

• работа
  • стоимость List<T>
  • стоимость LinkedList<T>
• вставить в конце
  • O (1) (амортизированная стоимость, при необходимости удвоение размера)
  • O (1) распределение каждый раз
• вставить при запуске
  • O (N) (хотя это и происходит при быстром перемещении памяти, что несколько усложняет поведение во время работы)
  • O (1)
• вставить в место x (и удалить тоже)
  • O (N-x) (см. Комментарий для вставки в конце)
  • O (1)
• прямое перечисление
  • O (N) (хотя количество пропущенных кэшей сведено к минимуму)
  • O (N) (хотя сильно зависит от локальности кэша)
• обратное перечисление
  • O (N)
  • O (N) (реализация LinkedList<T> связана дважды)
• произвольный доступ
  • O (1)
  • O (N)

Использование памяти является сложным, поскольку List может иметь не более Count - 1 избыточных ячеек в любой точке, но LinkedList<T> будет потреблять LinkedListNode<T> для каждой ячейки, что является дополнительными 3 ссылками (4/8 байт на ячейку) плюс обычный объект над головой. При нормальном использовании список, вероятно, выиграет, но опять же, это должно вызывать беспокойство только в том случае, если вы обнаружите, что потребление памяти действительно является проблемой.

Answer 3

Если вы не имеете дело с сотнями тысяч или миллионами записей, и вы профилировали свою программу, чтобы увидеть, что есть серьезная проблема, вы, вероятно, не заметите разницу между ними.

Кроме этого:

LinkedList<T> предоставляет отдельные узлы типа LinkedListNode<T>, поэтому вставка и удаление являются операциями O (1).

из здесь .

Answer 4

Я бы использовал List<T>, потому что все ваши данные будут храниться последовательно, если они являются типами значений и все еще преуспевают со ссылочными типами (внутренне, List<T> управляет массивом, который увеличивается в два раза каждый раз вам не хватает места).

LinkedList<T> имел обыкновение иметь намного больше смысла, когда вещи не были связаны с IO. Люди часто будут цитировать его кажущуюся природу «О (1)». Тем не менее, это снижает реальную стоимость, связанную с повышением вероятности сбоя страниц при получении узлов.

Если вы можете получить смежные области памяти с массивом или List<T> и избежать вероятности сбоя страницы, вам гораздо лучше с современными линиями кэширования процессора и основной памяти.

Если вы заранее знаете, сколько элементов у вас будет, используйте массив. Если вы хорошо представляете, сколько элементов, используйте List<T> (и в конструкторе передайте вероятную верхнюю границу, чтобы потенциально избежать перераспределения).

Единственный раз, когда я бы использовал LinkedList<T>, это если вам нужно постоянно увеличивать элементы в списке на одно значение. Например, если вы реализуете алгоритм кэширования , который использовался в последнее время, и вам нужно что-то добавить в начало и взять что-то с конца.

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

Я бы выбрал List<T> и работал с ним, если вы не заметили проблем (через профилирование)

Answer 5

Если индексированный доступ не требуется, вам, вероятно, лучше использовать LinkedList<T>. Разницы не так много, но LinkedList может быть быстрее для добавления.

Answer 6

Учитывая ваши требования к интерфейсу, вы должны использовать ICollection<T> везде в своем коде, а не ссылаться на конкретный конкретный класс.

Причина в том, что если вы используете List, вы можете написать набор кода, который использует l[0] для получения первого элемента. С другой стороны, если вы используете LinkedList, вы можете распространять вызовы на AddLast по всему коду. Чтобы сохранить возможность переключения, вам нужно избегать случайной зависимости от функций, которые вам не нужны. Вам необходимо использовать интерфейс, который могут поддерживать оба контейнера.

Итак, напишите такой класс:

public static class Collections
{
    public static ICollection<T> Make<T>()
    {
        return new List<T>();
    }
}

Затем, когда вам понадобится коллекция, сделайте следующее:

ICollection<int> c = Collections.Make<int>();

Изолировать выбранный вами контейнер от остальной части вашей программы. Теперь, когда вы профилируете и передумаете, вам просто нужно отредактировать метод Make<T>.

Answer 7

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

Answer 8

LinkedList будет нести больше накладных расходов памяти (для узлов), но лучше, если вы вставляете много элементов в середину. Связанный список также потребует большего выделения памяти, поскольку LinkedListNode является классом и выделяется динамически. Если вы не вставляете элементы (просто добавляете), я бы использовал список. Список должен быть быстрым или быстрым для добавления, хотя иногда его придется расширять.