Что такое LinkedList в C# и когда его использовать?

Что проверяют

Понимаете ли вы, что асимптотика не равна скорости. В учебнике вставка в середину связного списка это константа, а в массиве линия, но на практике List обгоняет LinkedList почти везде. Вопрос показывает, читали ли вы документацию коллекций .NET и думаете ли про память, а не только про значок O.

Как отвечать

LinkedList это двусвязный список узлов: каждый узел хранит значение и ссылки на соседей. Класс не реализует IList, индексатора у него нет вовсе, доступны First, Last и перебор.

Константа получается, только когда узел уже на руках:

var node = list.AddLast("второй");
list.AddAfter(node, "третий");   // O(1)
list.Remove(node);               // O(1)
list.Remove("третий");           // O(n): сначала поиск

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

В остальных задачах берите List: он лежит в памяти сплошным куском, попадает в кэш процессора и обходится без отдельного объекта на элемент.

Где спотыкаются

Говорят «вставка в середину быстрее» и молчат про поиск места вставки. Пока позиция ищется перебором, преимущество исчезает: на вставке по значению связный список проигрывает.

Называют его экономным по памяти. Наоборот: на каждый элемент приходится отдельный объект с заголовком и двумя ссылками, а сами элементы разбросаны по куче, что означает промахи кэша на каждом шаге обхода.

Сравнивают с ArrayList, хотя это устаревшая необобщённая коллекция с упаковкой значимых типов. Сегодня ориентир для сравнения это List, а для очереди и стека есть готовые Queue и Stack.