Замечание: все измерения сделаны с помощью класса Instant с небольшим количеством прогонов (4), а значит, не являются абсолютно точными. Присутствует погрешность.
- Вставка в начало
- Выполляется за o(1) в обоих случаях.
- Вставка в середину
- Выполняется пропорционально количеству элементов в обоих случаях.
- Выполняется в MyLinkedList незначительно быстрее.
- Вставка в конец
- Выполняется за o(1) в обоих случаях.
- Удаление из начала
- Выполняется за o(1) в обоих случаях.
- Удаление из середины
- Выполняется пропорционально количеству элементов в обоих случаях.
- Выполняется в MyLinkedList незначительно быстрее.
- Удаление из конца
- Выполняется за o(1) в LinkedList, так как это двусвязный список => можно получить last.prev и сделать его последним элементом за несколько операций.
- Выполняется пропорционально количеству элементов в MyLinkedList, так как это односвязный список => нужно пройтись по всем элементам, чтобы дойти до предпоследнего.
- Поиск по индексу
- Выполняется пропорционально количеству элементов в обоих случаях.
- Выполняется в LinkedList незначительно быстрее.
Собственная реализация связного списка оказалась по производительности сопоставима с LinkedList из java.util, за исключением удаления элементов из конца, где производительность собственной реализации значительно проигрывает стандартной.
- Вставка в начало
- Выполняется в ArrayList пропорционально количеству элементов.
- Выполняется за o(1) в LinkedList.
- Вставка в середину
- Выполняется пропорционально количеству элементов в обоих случаях.
- Выполняется в ArrayList значительно быстрее. Скорее всего, это достигается за счет выполнения нативного метода arraycopy для копирования массивов.
- Вставка в конец
- Выполняется за o(1) в обоих случаях.
- Поиск по индексу
- Выполняется за o(1) в ArrayList.
- Выполняется в LinkedList пропорционально количеству элементов.
В большинстве случаев ArrayList на практике оказывается эффективнее LinkedList, исключением является лишь вставка в начало. Соответственно, если нужен список, где постоянно происходит вставка в начало, лучше использовать LinkedList, в остальных случаях - ArrayList.
- Вставка, удаление, поиск
- Выполяется в HashSet и LinkedHashSet за o(1).
- Выполняетя в TreeSet пропорционально количеству элементов.
Перечисленные коллекции работают достаточно быстро. HashSet и LinkedHashSet имеют практически одинаковую производительность, в то время как TreeSet работает медленнее из-за необходимости выполнять сортировку при каждой вставке. Соответственно, если порядок элементов в множестве не важен - лучше использовать HashSet. Если требуется, чтобы элементы хранились в порядке вставки - LinkedHashSet. Если требуется, чтобы элементы множества были отсортированы - TreeSet.
- Вставка, удаление, поиск
- Выполяется в HashMap и LinkedHashMap за o(1).
- Выполняетя в TreeMap пропорционально количеству элементов.
Перечисленные коллекции работают достаточно быстро. HashMap и LinkedHashMap имеют практически одинаковую производительность, в то время как TreeMap работает медленнее из-за необходимости выполнять сортировку при каждой вставке. Соответственно, если порядок ключей в карте отображения не важен - лучше использовать HashMap. Если требуется, чтобы ключи в карте отображения хранились в порядке вставки - LinkedHashMap. Если требуется, чтобы ключи в карте отображения были отсортированы - TreeMap.