Перейти на PRO

Когда применять List, а когда LinkedList в C#?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C# Разработчик

Ответ

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

List<T> (Динамический массив)

  • Используйте, когда:
    1. Частый доступ по индексу (list[i]) – операция O(1).
    2. Частые операции добавления/удаления в конце коллекции (Add, RemoveAt(count-1)) – в среднем O(1).
    3. Вы выполняете много итераций (foreach), что очень быстро.
  • Избегайте, когда: Нужны частые вставки или удаления в начале или середине списка. Это требует сдвига всех последующих элементов (O(n)).

LinkedList<T> (Двусвязный список)

  • Используйте, когда:
    1. Частые вставки или удаления в произвольном месте списка, если у вас уже есть ссылка на узел (LinkedListNode<T>). Сама операция AddAfter(node, value) или Remove(node) — O(1).
    2. Реализация структур типа очереди (FIFO) или стека (LIFO) с операциями на обоих концах (AddFirst/RemoveFirst, AddLast/RemoveLast), которые также O(1).
  • Избегайте, когда: Необходим частый доступ по индексу. Для получения элемента по индексу N требуется последовательный проход (O(n)).

Практический пример и сравнение:

// Сценарий 1: Частые обращения по индексу и добавление в конец -> List<T>
var scores = new List<int>(1000); // Указание емкости улучшает производительность.
for (int i = 0; i < 1000; i++) {
    scores.Add(i * 10); // Быстро.
}
int medianScore = scores[scores.Count / 2]; // Мгновенный доступ.

// Сценарий 2: Частые вставки в начало/середину при известной позиции -> LinkedList<T>
var historyLog = new LinkedList<string>();
LinkedListNode<string> current = historyLog.AddFirst("First entry");
// ... позже, быстрое добавление до/после известного узла.
historyLog.AddAfter(current, "Second entry");

// Сценарий 3: Реализация простой очереди (можно использовать Queue<T>, но для примера):
var queue = new LinkedList<int>();
queue.AddLast(1); // Enqueue
queue.AddLast(2);
int firstItem = queue.First.Value; // Peek
queue.RemoveFirst(); // Dequeue (O(1))

Итог: В 95% случаев в C# List<T> является оптимальным выбором благодаря скорости доступа по индексу и эффективности кэша процессора (данные расположены в памяти непрерывно). LinkedList<T> — специализированная структура для специфичных сценариев частой вставки/удаления в середине, когда поиск позиции уже выполнен.

Ответ 18+ 🔞

Так, слушай, вот тебе на пальцах, чтобы до любого дебила дошло. Выбор между List<T> и LinkedList<T> — это не про то, что круче звучит, а про то, какие операции ты будешь делать чаще всего. Смотри, как есть.

List<T> (Это типа динамический массив, понял?)

  • Бери его, когда:
    1. Тебе часто нужно лезть к элементу по номеру, типа list[i]. Это делается мгновенно, O(1), потому что он знает, где всё лежит.
    2. Ты часто пихаешь или выкидываешь что-то в самый конец списка (Add, RemoveAt(count-1)). В среднем тоже быстро, O(1), ёпта.
    3. Ты просто гоняешь по всему списку в цикле (foreach). Это летает, потому что всё в памяти подряд лежит, как солдаты на плацу.
  • НЕ бери его, когда: Тебе надо часто впихивать или выдёргивать что-то из начала или середины. Это пиздец какой медленный, O(n), потому что ему придётся всю эту очередь после твоего элемента сдвигать, как дурак тачку с кирпичами.

LinkedList<T> (Это типа цепочка, где каждый элемент знает про соседей)

  • Бери его, когда:
    1. Тебе часто нужно вставить или удалить что-то в любом месте, но у тебя уже есть ссылка на этот самый узел (LinkedListNode<T>). Тогда сам акт вставки рядом или удаления — это O(1), раз плюнуть.
    2. Ты делаешь очередь или стек, где работаешь с обоими концами (AddFirst/RemoveFirst, AddLast/RemoveLast). Это тоже O(1), красиво и быстро.
  • НЕ бери его, когда: Тебе постоянно нужен доступ по индексу, типа «дай мне 257-й элемент». Это пиздец, O(n), потому что бедному процессору придётся идти от самого начала и отсчитывать каждый раз, как будто он по цепочке из бумажек идёт. И память он жрёт, как не в себя, потому что на каждый элемент свой служебный хлам.

Ну, и примеры, чтобы вообще всё стало ясно:

// Пример 1: Часто лезем по индексу, добавляем в конец -> List<T> наш выбор, блядь.
var scores = new List<int>(1000); // Сразу говорим размер, чтобы не копался потом.
for (int i = 0; i < 1000; i++) {
    scores.Add(i * 10); // Быстро, как шмель.
}
int medianScore = scores[scores.Count / 2]; // Взял и всё, мгновенно.

// Пример 2: Часто вставляем в середину, зная место -> LinkedList<T>, вот где он царь.
var historyLog = new LinkedList<string>();
LinkedListNode<string> current = historyLog.AddFirst("Первая запись");
// ... а потом, блядь, быстро цепляем следующую за известной.
historyLog.AddAfter(current, "Вторая запись");

// Пример 3: Делаем очередь (хотя есть Queue<T>, но для понятности):
var queue = new LinkedList<int>();
queue.AddLast(1); // Поставил в хвост
queue.AddLast(2);
int firstItem = queue.First.Value; // Глянул, кто первый
queue.RemoveFirst(); // Выкинул первого (O(1), быстро!)

Короче, вывод простой, как три копейки: В 95 случаях из 100 тебе нужен List<T>. Он для большинства задач — отличный выбор, быстрый и удобный. LinkedList<T> — это такая узкоспециальная хуйня, для особых случаев, когда ты точно знаешь, что будешь постоянно ковыряться в середине списка. А так — не морочь себе голову, бери List и живи спокойно.

© ХакСобесов, 2026
support@hacksobesov.com