В Java ArrayList и LinkedList оба являются членами фреймворка Collection. Они реализуют интерфейс java.util.List и предоставляют возможность хранить и получать объекты в упорядоченных коллекциях. Оба являются несинхронизированными классами. Тем не менее, они различаются во многих аспектах, и нам нужно подробно изучить оба класса, чтобы принять мудрое решение о том, когда какой класс использовать.
1. Внутренняя реализация LinkedList и ArrayList
LinkedList — это реализация двусвязного списка в Java. Каждый объект в связанном списке обернут в экземпляр Node:
transient Node<E> first;transient Node<E> last;private static class Node<E> {E item;Node<E> next;Node<E> prev;}ArrayList был реализован как динамически изменяемый массив. Это приведет к дальнейшим различиям в производительности.
transient Object[] elementData;
Обратите внимание, что оба списка допускают дублирование элементов и сохраняют порядок вставки элементов. В LinkedList элементы имеют ссылку на следующий и предыдущий элементы.
2. Разница в производительности
2.1. Добавить элемент
Добавление элемента в ArrayList — это операция O(1), если она не требует изменения размера резервного массива. Если размер массива изменяется, то она становится O(log(n)).
Добавление элемента в LinkedList является операцией O(1), поскольку не требует изменения размера.
2.2 Удалить элемент
Когда мы удаляем элемент из ArrayList(в резервном массиве), он перемещает все элементы, которые находятся после удаленной позиции индекса. Это делает его близким к O(n) в худшем случае, когда мы удаляем первый элемент. Производительность составляет O(1) в лучшем случае, когда мы удаляем последний элемент.
Операция LinkedList remove() дает производительность O(1), поскольку ей нужно просто сбросить указатели предыдущего и следующего узлов. Копирование или перемещение не требуется.
2.3 Итерация
Итерация представляет собой операцию O(n) как для LinkedList, так и для ArrayList, где список содержит «n» элементов.
2.4. Получить элемент
ArrayList предоставляет get(int index), который напрямую находит элемент в указанном месте индекса. Он имеет порядок O(1).
LinkedList также предоставляет метод get(), НО он сначала обходит все узлы, чтобы достичь нужного узла. Это делает производительность переменной. В лучшем случае это O(1), а в худшем случае это O(n).
3. Заключение
Пока мы не имеем дело с очень большим объемом данных, оба класса дадут нам одинаковый уровень производительности. Оба являются упорядоченными списками, и оба несинхронизированы.
LinkedList также реализует интерфейс Deque, поэтому он обеспечивает функциональность FIFO, подобную очереди, с помощью таких методов, как peek() и poll(). Как видно из сравнения производительности, ArrayList лучше подходит для хранения и доступа к данным. LinkedList лучше подходит для манипулирования данными.
Вот и все о arraylist и linkedlist в Java.
Подробнее: Документация по ArrayList Java и Документация по LinkedList Java