Что такое LinkedList?

Что такое LinkedList?

LinkedList (связный список) — это фундаментальная структура данных, представляющая собой последовательность элементов, где каждый элемент (узел) хранит собственные данные и ссылку (или ссылки) на следующий и/или предыдущий элемент в последовательности. В отличие от массивов (Array) или списков (List), элементы LinkedList не хранятся в непрерывном блоке памяти.

Ключевые особенности и принцип работы

В основе LinkedList лежит концепция узлов (Node). Каждый узел содержит:

• Data (Данные) — само значение элемента.
• Next (Следующий) — ссылка на следующий узел в списке.
• Prev (Предыдущий) — ссылка на предыдущий узел (присутствует в двусвязном списке).

// Примерная структура узла двусвязного списка
public class LinkedListNode<T>
{
    public T Data { get; set; }
    public LinkedListNode<T> Next { get; set; }
    public LinkedListNode<T> Prev { get; set; }

    public LinkedListNode(T data)
    {
        Data = data;
    }
}

Основные типы связных списков

1. Односвязный список (Singly Linked List):

    *   Узел содержит данные и ссылку `Next` на следующий элемент.
    *   Обход возможен только в одном направлении — от головы к хвосту.
    *   Эффективен для операций вставки/удаления в начале списка.

1. Двусвязный список (Doubly Linked List):

    *   Узел содержит данные и две ссылки: `Next` и `Prev`.
    *   Позволяет обход в обоих направлениях.
    *   Класс `System.Collections.Generic.LinkedList<T>` в C# реализует именно двусвязный список.
    *   Операции вставки и удаления выполняются за O(1), если известен узел-модификатор.

1. Кольцевой связный список (Circular Linked List):

    *   "Хвост" списка ссылается на его "голову", образуя кольцо.
    *   Может быть как односвязным, так и двусвязным.

Преимущества и недостатки LinkedList по сравнению с List/Array

Преимущества (Сильные стороны):

• Быстрая вставка и удаление в любой позиции (O(1)) при условии, что известен узел, рядом с которым происходит операция. Не требует сдвига последующих элементов, как в массиве.
• Динамический размер: Список может расти и сокращаться без необходимости предварительного выделения памяти или реаллокации, в отличие от массивов.
• Эффективное использование памяти для фрагментированных операций: Не требуется резервировать непрерывный блок памяти.

Недостатки (Слабые стороны):

• Медленный доступ по индексу (O(n)): Для доступа к элементу с индексом n необходимо пройти все предыдущие n-1 элементов, начиная с головы списка. В List<T> доступ по индексу происходит за O(1).
• Больший расход памяти на хранение структуры: Каждый элемент требует дополнительной памяти для хранения одной или двух ссылок.
• Отсутствие встроенной кэш-локальности: Элементы разбросаны в памяти, что делает последовательный обход менее эффективным для процессора по сравнению с массивом, где данные лежат рядом.

LinkedList<T> в C# и Unity

В Unity, при работе на C#, вы можете использовать стандартную реализацию System.Collections.Generic.LinkedList<T>. Она предоставляет методы для эффективной работы с узлами.

using System.Collections.Generic;

// Пример использования в контексте Unity
public class UnitSpawner : MonoBehaviour
{
    private LinkedList<GameObject> _activeUnits = new LinkedList<GameObject>();

    void SpawnUnit(GameObject unitPrefab)
    {
        GameObject newUnit = Instantiate(unitPrefab);
        // Быстрое добавление в конец списка
        _activeUnits.AddLast(newUnit);
    }

    void RemoveUnit(LinkedListNode<GameObject> unitNode)
    {
        // СУПЕРБЫСТРОЕ удаление, если известен точный узел (O(1))
        _activeUnits.Remove(unitNode);
        Destroy(unitNode.Value);
    }

    // Медленный поиск по значению (O(n))
    void RemoveUnitByGameObject(GameObject unit)
    {
        _activeUnits.Remove(unit); // Этот метод внутренне выполняет поиск
    }
}

Практическое применение в разработке игр

• Система пула объектов, где требуется частое добавление и удаление объектов из середины контейнера.
• Список активных врагов или персонажей, порядок которых может динамически меняться.
• Реализация сложных структур данных: стеков, очередей (включая двустороннюю очередь - Deque), графов.
• Система отмены действий (Undo/Redo), где каждое действие — узел в списке.
• Управление порядком рендеринга или порядком обновления объектов.

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