Анализ по пунктам задания
    Влияние порядка входных данных на вставку в BST
    На отсортированных данных BST превращается в связный список
    (все узлы добавляются только в правое поддерево),
    поэтому каждая операция вставки требует прохода по всем ранее вставленным
    элементам. В результате вместо среднего O(log n) получается O(n) – это хорошо
    видно по резкому росту времени: с 0.02 с до ~2 с. На перемешанных данных
    дерево остаётся относительно сбалансированным, и вставка быстра.

    Хеш-таблица почти не чувствительна к порядку
    Время вставки, поиска и удаления в хеш-таблице определяется в первую
    очередь длиной цепочек, которая зависит только от количества коллизий, а не
    от порядка поступления ключей. Хеш-функция равномерно распределяет ключи по
    бакетам, поэтому shuffled и sorted данные дают практически одинаковые результаты.
    Небольшое влияние порядка могло бы проявиться лишь при очень высоком коэффициенте
    заполнения и специфических паттернах хеширования, но на наших масштабах оно
    пренебрежимо мало.

    Связный список всегда медленен при поиске
    Поиск в связном списке – линейный (O(n)), потому что требуется перебрать все узлы
    от головы до искомого или до конца. В нашем эксперименте поиск 110 имён занимал
    в среднем 0.03 с, что на два порядка медленнее хеш-таблицы и BST в нормальном
    режиме. Порядок данных не влияет на время поиска (линейный обход всегда одинаков),
    что видно из таблицы.

    Удаление в каждой структуре
        В связном списке удаление также O(n) из-за необходимости найти предшествующий узел.
        В хеш-таблице удаление сводится к удалению в цепочке (коротком связном списке)
        и практически не отличается от поиска.
        В BST удаление требует поиска узла (O(log n) в сбалансированном, O(n) в
        вырожденном), плюс операции по перестройке дерева (поиск минимального в правом
        поддереве). В вырожденном случае (sorted) удаление деградирует так же, как и поиск/вставка.

Вывод: какую структуру выбирать в реальной жизни

    Частые вставки/удаления + быстрый поиск → Хеш-таблица. Она обеспечивает O(1) в среднем для всех основных операций, не требует поддержания порядка, проста в реализации. Идеально для словарей, кэшей, индексов баз данных.

    Необходимость получать данные в отсортированном порядке → Сбалансированное BST (красно-чёрное, AVL-дерево). Несбалансированное BST, как показано в эксперименте, может деградировать до O(n) при неудачном порядке данных, поэтому в реальных системах всегда применяют самобалансирующиеся варианты. Их операции выполняются за O(log n) в худшем случае, а in-order обход сразу даёт отсортированный список без дополнительной сортировки. Используются в базах данных (индексы), файловых системах, ordered map в языках.

    Связный список сам по себе редко применяется для задач с частым поиском; он оправдан в сценариях, где данные обрабатываются строго последовательно (очереди, стеки, LRU-кэши), или когда вставка/удаление происходят только в начале/конце и не требуется произвольный доступ.

    Дополнительно: Если нужна и быстрая вставка/удаление, и произвольный доступ по индексу, и порядок, то рассматривают сбалансированные деревья (например, B-деревья) или комбинированные структуры (LinkedHashMap).

Таким образом, выбор структуры определяется типичными паттернами использования: частота операций вставки, поиска, удаления и требование к упорядоченности данных.