Связанный список анализа Java-разработчики должны знать

Как LinkedList превосходит ArrayList и ArrayDeque

Кто-нибудь действительно использует LinkedList? Я написал это и никогда не использую . Джошуа Блох

Вы видели LinkedList. Выучил это в колледже или в своей кодовой базе. Я тоже подумал и задумался. Почему использовать LinkedList - плохо? В чем проблема производительности в ArrayList и LinkedList?

Вот что я узнал и делюсь с вами.

Преимущества LinkedList

LinkedList реализует интерфейсы Deque и List. Deque - это расширенная очередь, что означает, что поддерживаются FIFO и LIFO. Почему это важно? Добавление элементов в конец или начало LinkedList является постоянным или O (1).

Итак, это объясняет часть «Первый вошел, последний вошел». А как насчет Первым ушел и ушел последним? Удаление элементов с конца или начала LinkedList является постоянным или O (1).

Все реализованные интерфейсы: Сериализуемый, Клонируемый, Итерируемый ‹E›, Коллекция ‹E›, Deque ‹E›, Список ‹E›, Очередь ‹E› - Документы LinkedList

В чем преимущество LinkedList перед ArrayList?

LinkedList лучше работает с хвостиком и головой списков.

Добавление в хвост ArrayList может стоить O (1), если не изменять размер. Изменение размера ArrayList стоит O (N). Изменение размера можно уменьшить, выделите больше памяти при создании ArrayList. Добавление в заголовок списка занимает O (n) времени из-за копирования.

Итак, мы используем LinkedList при работе с этими элементами? При работе с меньшими наборами это не имеет значения. Для больших наборов это может иметь значение.

Вы могли бы проработать долгую карьеру инженера-программиста, никогда не оказавшись в такой ситуации².

Когда следует использовать LinkedList? Когда ваше приложение много добавляет элементов в начало и конец. Вот тогда и можно было увидеть улучшение по сравнению с ArrayList. Опять же, все зависит от установленного размера, как мы увидим в разделе тестов.

Недостатки LinkedList

ArrayList лучше, чем LinkedList в методах получения / установки. Почему? LinkedList необходимо пройти не менее половины набора или N / 2, чтобы получить или установить элемент. ArrayList индексирование является постоянным или O (1).

Что еще лучше ArrayList? ArrayList размещается в памяти в непрерывных блоках памяти. Это улучшает кеширование и упрощает управление. LinkedList с другой стороны, необязательно находиться в последовательных блоках памяти.

ArrayList занимает меньше памяти. LinkedList должен хранить два указателя (предыдущий, следующий) и указатель на полезную нагрузку. Когда все это рассредоточено по памяти, обход замедляется.

LinkedList плохо работает при произвольном доступе для чтения. Как улучшить случайное чтение? Одна из возможных структур - ArrayDeque. Хотя это приносит другие проблемы. Нажатие ArrayDeque может вызвать изменение размера или копирование всего массива. ArrayDeque имеет постоянное время доступа, поэтому лучше для фиксированных элементов.

Еще один недостаток ArrayDeque - в нем не реализован List интерфейс. Почему это важно? Удаление отдельных элементов может занять больше времени. Поскольку вам нужно перемещать элементы, и в связанной структуре вы должны изменить указатели.

LinkedList против теста ArrayList

Вот методы тестирования:

ArrayList - поиск и удаление
LinkedList - поиск и удаление
ArrayList - поиск
LinkedList - поиск

Поиск выполняется для элементов, близких к середине набора элементов.

LinkedList - добавить в конец списка
ArrayList - добавить в конец списка

Для добавления элементов в конец списка используем add метод. addAll вызовет изменение размера в списке.

LinkedList - добавить все - addAll
ArrayList - добавить все - addAll
LinkedList - добавить все с нуля - add
ArrayList - добавить все с нуля - add

Тест для LinkedList и ArrayList. На основе этого кода. Бенчмарк содержит время выполнения метода. Время выполнения сравнивается по размеру и JDK. Бенчмарк размером 5 и 500.000 элементов.

Что мы можем сделать из набора небольшого размера? Немного. Тем не менее, мы видим, что для небольших наборов выбор не имеет значения. Почему? Потому что на наборах небольшого размера оба работают довольно быстро. Несколько наносекунд, неважно.

Ярким примером является метод поиска и удаления. Все результаты меньше 100 нс, что противоречит обозначению большого O. Мы можем заключить, что для небольших наборов нотация большого O не дает нам никакой информации.

Посмотрите на метод поиска и удаления с этим набором размеров. Мы видим, что поиск ArrayList немного быстрее, чем поиск LinkedList. «Медленность» составляет порядка 0,5 мс. В заключение, разница в производительности невелика.

Вывод

После этого анализа мы можем сделать следующие выводы:

Избегайте LinkedList для приложений, чувствительных к памяти, например мобильные приложения
Используйте ArrayList, чтобы улучшить пространственную локальность, чтобы улучшить попадание в кеш
Медленность LinkedList по ArrayList незначительна, поскольку мои тесты показывают, что
ArrayDeque может улучшить произвольный доступ для чтения, но проигрывает LinkedList при удалении элементов
LinkedList хорош для удаления, вставки элементов, но плох при извлечении

Что вы думаете о LinkedList? У вас есть какие-нибудь интересные факты? Если да, оставьте это в комментариях. Спасибо за чтение!