Приветствую вас!
После изучения коллекций, а именно такие реализации List
, как ArrayList
и LinkedList
, возникла идея, а почему бы не объединить эти структуры данных в одну и посмотреть, что из этого получится.
Зачем это нужно?
- Проблема
ArrayList
— у него есть начальный размер по умолчаниюDEFAULT_CAPACITY
или заданный размерinitialCapacity
, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложностьO(n)
- Проблема
LinkedList
— здесь наоборот, добавить новый элемент, это всего лишь добавить новую связь (создать еще однуNode
и добавить ссылку на неё), но операция получения элемента по индексу очень затратна, т.к. нужно будет пройтись по всему списку от начала, что очень затратно и даетO(n)
Решение
Что если создать такую структуру данных, при которой вставка и получение любого элемента будет за константное время. Буду использовать технологию ArrayList
без пересоздания массива, что конечно же проигрывает по памяти, но выигрывает в скорости, т.к. память дешевая и её очень много, выигрыш в производительности считаю приоритетным.
Для того чтобы связать их между собой, буду использовать двусвязный список: