Ответ
Сложность — 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) |
Ответ 18+ 🔞
Да ты посмотри на эту хуйню, блядь! Смотри, что тут происходит, ёпта!
Ну вот представь, у тебя есть LinkedList. Это ж не массив, сука, а цепочка, блядь, как вагоны в поезде, только каждый вагон знает про соседа спереди и сзади. И чтобы, например, найти пассажира в пятом вагоне, тебе надо, блядь, зайти в голову поезда и идти-идти, пока не дойдёшь, понимаешь? Нельзя просто взять и прыгнуть в середину, как в ArrayList — там ты по индексу сразу прискакал, и всё, блядь, O(1), красота!
А тут, сука, list.get(2) — это ж надо стартовать с первого узла, потом перепрыгнуть на второй, и только потом добраться до третьего. И если список длинный, как моя тоска в понедельник, то это будет O(n) в худшем случае, то есть обоссаться можно, пока ищешь.
Вот смотри на пример кода, тут всё честно:
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.Видишь? Чтобы взять "C", надо пролезть через "A" и "B". Пиздец, да?
А теперь гляди на эту табличку, она, блядь, как откровение свыше:
| Операция | ArrayList |
LinkedList |
|---|---|---|
Доступ по индексу (get) |
O(1) | O(n) |
| Вставка в начало | O(n) | O(1) |
| Вставка в конец (аморт.) | O(1) | O(1) |
| Удаление из начала | O(n) | O(1) |
Вот и думай теперь, э бошка, думай! Если тебе надо часто тыкать пальцем в случайные места и что-то оттуда выковыривать — бери ArrayList, там рай и благодать. А если ты, сука, любишь возиться с началом списка — вставлять или удалять — то LinkedList твой лучший друг, потому что он просто перещёлкнет пару ссылочек, и готово, O(1), в рот меня чих-пых!
Короче, выбирай с умом, а то накроешься медным тазом с производительностью.