ArrayList:
- Доступ к произвольному элементу по индексу за константное время O(1);
- Доступ к элементам по значению за линейное время O(N);
- Вставка в конец в среднем производится за константное время O(1);
- Удаление произвольного элемента из списка занимает значительное время, т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется);
- Вставка элемента в произвольное место списка занимает значительное время, т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку вправо;
- Минимум накладных расходов при хранении.
LinkedList:
- На получение элемента по индексу или значению потребуется линейное время O(N);
- На добавление и удаление в начало или конец списка потребуется константное O(1);
- Вставка или удаление в/из произвольного места за константное O(N);
- Требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся ещё указатели на следующий и предыдущий элементы списка.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
- Доступ к произвольному элементу по индексу за константное время O(1);
- Доступ к элементам по значению за линейное время O(N);
- Вставка в конец в среднем производится за константное время O(1);
- Удаление произвольного элемента из списка занимает значительное время, т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется);
- Вставка элемента в произвольное место списка занимает значительное время, т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку вправо;
- Минимум накладных расходов при хранении.
LinkedList:
- На получение элемента по индексу или значению потребуется линейное время O(N);
- На добавление и удаление в начало или конец списка потребуется константное O(1);
- Вставка или удаление в/из произвольного места за константное O(N);
- Требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся ещё указатели на следующий и предыдущий элементы списка.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.