Что будет если объединить ArrayList и LinkedList?

Возможно корректность способа замера оставляет желать лучшего

JMH, конечно, не гарантирует вам корректности бенчмарка, но избавиться от самых типичных проблем поможет. Добавить его не трудно, посмотрите хоты бы вот этот пример.

Очень хотелось бы увидеть результаты, полученные с помощью него. Также было бы хорошо увидеть полученный бенчмарк в вашем репозитории, чтобы можно было легко его запустить у себя.

Если я правильно помню, подобным способом реализованы массивы в стандартной библиотеке scala.

1)На первый взгляд заменив связанный список на связанный список массивов вы получили ровно сложность доступа по индексу O(n) что и у списка, выиграли (?) только «коэффициент». Это понятно и без реализации и в целом подтверждается вашими графиками
2)Кроме того вы забыли об операции вставки (insert). Она может быть через увеличение размера конкретной «корзины» (а значит по «сложностям» мы возвращаемся к ArrayList), тогда надо переписать вашу реализацию get(idx) чтобы она учитывала переменный размер массивов в списке. Либо вставку можно реализовать через добавление-в-начале/удаление-в-конце для каждой из корзин после той в которую добавился элемент, что ясное дело сводит на нет всё возможное преимущество.

В сухом остатке: предвижу, что в «реальном софте» в зависимости от профиля нагрузки ваше преимущество будет чуть более чем никакое. Да и в конечном итоге — внутри ArrayList — массив указателей на объекты. Лежат в памяти хорошим таким цельным понятным куском байт. Если еще и хип маленький, то с compressedOOPs — в 2 раза меньше. И вот это вот всё хозяйство нативный arraycopy через DMA и всё такое прочее сделает ну очень быстро. Гораздо быстрее чем ваша «очень умная логика».
Да и + если где-то увеличение ArrayList станет узким местом — наверняка аккуратный выбор начального размера и инкремента по эффективности опять же сможет обойти ваше решение.

Вроде как примерно таким образом обычно устроен std::deque в C++. Джавовский ArrayDeque устроен иначе.

Проблема ArrayList — у него есть начальный размер по умолчанию DEFAULT_CAPACITY или заданный размер initialCapacity, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложность O(n)

проблема LinkedList это то что тратится память на обьекты в массив можно примитивных значений иметь.
однажды в качестве теста я для избавления от копирования сделал немного иначе — просто массив из массивов, при наполнении одного создаётся другй без перекопирования, так оно работало хуже ArrayListа даже при ЗАПОЛНЕНИИ почему-то, так что мораль — нечего выдумывать.

Trade off. За плоскую модель памяти приходится платить сложными алгоритмами. Ничего радикально нового тут особо не придумаешь.

Такая идея закономерно приходит многим в самом начале изучения Java и коллекций. Но Вы все равно молодец, что прикрыв фиговым листочком random delete вышли на публику. ) ну и по ULL уже написали

Поздравляю: вы изобрели внутреннюю структуру HashMap.

Было бы интересно посмотреть на «экзотические» структуры данных типа Rope или Finger Trees и сравнить с ними стандартные и Вашу реализации.