Сколько времени займет получение элемента из связного списка? Из бинарного дерева поиска? Или из хэш-таблицы? А если в этих структурах будет миллион записей?

Из хэш-таблицы можно получить элемент за константное время, из бинарного дерева — за логарифмическое, из связного списка — за линейное. Количество элементов не влияет на асимптотику структуры данных, если всё идет как надо: в хэш-таблице либо нет, либо очень мало коллизий, а бинарное дерево сбалансировано. Иначе с ростом количества элементов производительность будет только уменьшаться.