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