Рубрика «структуры данных» - 4

Приветствую вас!
После изучения коллекций, а именно такие реализации List, как ArrayList и LinkedList, возникла идея, а почему бы не объединить эти структуры данных в одну и посмотреть, что из этого получится.

Зачем это нужно?

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

Решение

Что если создать такую структуру данных, при которой вставка и получение любого элемента будет за константное время. Буду использовать технологию ArrayList без пересоздания массива, что конечно же проигрывает по памяти, но выигрывает в скорости, т.к. память дешевая и её очень много, выигрыш в производительности считаю приоритетным.
Для того чтобы связать их между собой, буду использовать двусвязный список:

Читать полностью »