Что такое LinkedList (связный список) в C#?

LinkedList<T> в .NET — это реализация структуры данных двусвязный список. В отличие от массивов (T[]) или списков (List<T>), где элементы хранятся в непрерывном блоке памяти и доступны по индексу, связный список состоит из отдельных узлов (LinkedListNode<T>), каждый из которых содержит:

• Value — само значение элемента.
• Next — ссылка на следующий узел в списке.
• Previous — ссылка на предыдущий узел (отсюда "двусвязный").

Сложность операций (Big O):

• Вставка/удаление в известной позиции (по ссылке на узел): O(1). Это главное преимущество.
• Доступ по индексу (поиск элемента): O(n). Необходимо перебирать список с начала или конца.
• Вставка в начало/конец: O(1).
• Поиск элемента по значению: O(n).

Когда использовать LinkedList<T> вместо List<T>? Используйте связный список, когда основная операция в вашем сценарии — это частая вставка или удаление элементов в середине коллекции, и у вас уже есть ссылка на узел, рядом с которым нужно выполнить операцию. Для List<T> вставка в середину требует сдвига всех последующих элементов (O(n)).

Практический пример: Реализация кэша LRU (Least Recently Used), где нужно быстро перемещать элемент из середины списка в начало при обращении к нему.

// Пример работы с LinkedList<T>
var linkedList = new LinkedList<string>();

// Добавление элементов в конец
linkedList.AddLast("first");
linkedList.AddLast("second");
LinkedListNode<string> thirdNode = linkedList.AddLast("third"); // Сохраняем ссылку на узел

// Быстрая вставка ПЕРЕД известным узлом (O(1))
linkedList.AddBefore(thirdNode, "inserted_before_third");

// Быстрое удаление известного узла (O(1))
linkedList.Remove(thirdNode);

// Обход списка (доступ только последовательный)
foreach (var item in linkedList)
{
    Console.WriteLine(item); // Вывод: first, second, inserted_before_third
}

// НЕЛЬЗЯ делать так (нет индексатора):
// var element = linkedList[0]; // Ошибка компиляции

Недостатки и предостережения:

• Высокие накладные расходы на память: Каждый элемент требует хранения двух дополнительных ссылок (Next, Previous).
• Плохая локальность данных: Узлы разбросаны по памяти, что приводит к промахам кэша процессора и может замедлить перебор по сравнению с List<T>.
• Нет прямого доступа по индексу.

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