Выполнено в виде Rust-библиотеки. Для запуска тестового примера необходимо выполнить в терминале команду cargo run --example test_add --release

В примере измеряется время выполнения операции .push(i64) многократного добавления в массив 64-битного целого числа.

Сравнительная таблица производительности реализованных структур данных доступна по ссылке https://docs.google.com/spreadsheets/d/1pYJ43VkW3IqSRAfvH2X9TIlsTMHJGTMpyR_EeQJuY3U

Поскольку в безопасном Rust динамические массивы без стандартного std::alloc::Vec реализовать нельзя, была предложена реализация на базе туториала https://doc.rust-lang.org/nomicon/vec/vec-final.html

Как показывают тесты производительности, получившаяся реализация мало отличается от стандартной.

Однако надо помнить, что в динамический массив Array можно помещать далеко не любые типы, в отличие от стандартного std::alloc::Vec.

Так как это не требовалось по заданию, связный список не реализован. В Rust-community есть мнение, что применение связных списков не приносит никаких выгод. Все плюсы связных списков реализуются в Rust с помощью итераторов. Приоритетная очередь и неполный массив реализованы на базе динамического массива Array. Поиск в отсортированных массивах методом бисекции пока не реализован.