В чём разница между List и LinkedList?

Разница между List<T> и LinkedList<T> в .NET / Unity

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

Внутренняя структура и организация памяти

List<T> хранит элементы в непрерывном блоке памяти (массиве):

// Пример List<T> - элементы хранятся последовательно в памяти
List<int> numbers = new List<int>() { 10, 20, 30, 40 };
// В памяти: [10][20][30][40][][][][] (последние слоты могут быть пустыми)

LinkedList<T> хранит элементы в отдельных объектах-узлах, каждый из которых содержит:

• Значение элемента
• Ссылку на предыдущий узел
• Ссылку на следующий узел

// Пример LinkedList<T> - элементы хранятся в отдельных узлах
LinkedList<int> linkedNumbers = new LinkedList<int>();
linkedNumbers.AddLast(10);
linkedNumbers.AddLast(20);
// В памяти: Узел1{Value=10, Next→Узел2, Prev→null} <-> Узел2{Value=20, Next→null, Prev→Узел1}

Ключевые различия в производительности

1. Доступ по индексу (индексатор)

• List<T>: O(1) — прямой доступ к элементу по индексу

List<string> list = new List<string>() { "A", "B", "C" };
string item = list[1]; // Мгновенный доступ к элементу "B"

• LinkedList<T>: O(n) — требуется последовательный перебор узлов от начала или конца

// Нет прямой индексации, нужно перебирать узлы
LinkedListNode<string> node = linkedList.First?.Next; // Только для соседних узлов

2. Вставка/удаление элементов

• List<T>:
  • В начало/середину: O(n) — требует сдвига последующих элементов
  • В конец: O(1) (амортизированно), кроме случаев увеличения Capacity

List<int> list = new List<int>() { 1, 2, 4, 5 };
list.Insert(2, 3); // При вставке "3" на позицию 2, элементы 4,5 сдвигаются

• LinkedList<T>:
  • В начало/конец: O(1) — только изменение ссылок
  • В середину (если есть ссылка на узел): O(1) — только изменение ссылок соседних узлов

LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(4);
linkedList.AddLast(5);

LinkedListNode<int> node = linkedList.Find(4); // Находим узел
linkedList.AddBefore(node, 3); // Вставка без сдвига других элементов

3. Использование памяти

• List<T>:

  • Более эффективное использование памяти для хранения данных
  • Может иметь неиспользуемую емкость (Capacity > Count)
  • Меньшие накладные расходы на один элемент

• LinkedList<T>:

  • Дополнительные накладные расходы на хранение двух ссылок (Next/Prev) в каждом узле
  • Элементы распределены в куче фрагментарно, что может ухудшать локальность данных
  • Больше аллокаций памяти (каждый узел — отдельный объект)

Практические рекомендации для Unity разработки

Когда использовать List<T>:

• Частый доступ по индексу или случайный доступ к элементам
• Итерация по всем элементам (foreach работает эффективно)
• Предсказуемый размер коллекции или редкие вставки/удаления в середину
• Приоритет производительности в играх (лучшая локальность кэша процессора)
• Работа с компонентами Unity или другими данными, где важен быстрый доступ

// Типичный случай использования List<T> в Unity
List<Transform> enemyTransforms = new List<Transform>();

void Update() {
    // Быстрый доступ ко всем врагам
    for (int i = 0; i < enemyTransforms.Count; i++) {
        enemyTransforms[i].Translate(Vector3.forward * speed * Time.deltaTime);
    }
}

Когда использовать LinkedList<T>:

• Частые вставки/удаления в начале или середине коллекции
• Реализация очередей (FIFO) или стеков (LIFO) с операциями AddFirst/AddLast
• Алгоритмы, требующие частого объединения/разделения списков
• Ситуации, где важна стабильность ссылок на элементы (узлы остаются валидными)

// Пример использования LinkedList<T> для истории действий с возможностью отмены
public class ActionHistory {
    private LinkedList<IAction> actions = new LinkedList<IAction>();
    
    public void AddAction(IAction action) {
        actions.AddLast(action);
        // Ограничиваем историю 50 последними действиями
        if (actions.Count > 50) {
            actions.RemoveFirst();
        }
    }
    
    public void Undo() {
        if (actions.Last != null) {
            actions.Last.Value.Undo();
            actions.RemoveLast();
        }
    }
}

Особенности в контексте Unity

1. Производительность в Update-цикле: List<T> обычно предпочтительнее из-за лучшей кэш-локальности
2. Сборка мусора: LinkedList<T> создает больше объектов в управляемой куче, что может приводить к более частым GC
3. Сериализация: List<T> сериализуется Unity по умолчанию, LinkedList<T> — нет
4. LINQ операции: Для List<T> некоторые операции могут быть оптимизированы

Заключение

Выбор между List<T> и LinkedList<T> должен основываться на анализе операций, которые будут выполняться с коллекцией чаще всего. В игровой разработке на Unity List<T> используется в 90%+ случаев благодаря своей эффективности для типичных сценариев: хранения игровых объектов, компонентов, результатов физических запросов. LinkedList<T> остается специализированной структурой для специфических задач, где критически важны быстрые вставки/удаления в произвольных позициях при наличии ссылки на узел.