Ответ
Сложность — O(n) в худшем случае.
Почему? LinkedList — это двусвязный список, не поддерживающий произвольный доступ. Для получения элемента по индексу get(index) необходимо выполнить последовательный обход узлов от начала (или конца, если индекс ближе к нему) списка.
Пример:
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
String element = list.get(2); // O(n) - необходимо пройти через узлы с индексами 0 и 1.| Сравнение с ArrayList: | Операция | ArrayList |
LinkedList |
|---|---|---|---|
Доступ по индексу (get) |
O(1) | O(n) | |
| Вставка в начало | O(n) | O(1) | |
| Вставка в конец (аморт.) | O(1) | O(1) | |
| Удаление из начала | O(n) | O(1) |