← Назад к вопросам
Какая временная сложность поиска по индексу в LinkedList?
1.2 Junior🔥 101 комментариев
#Коллекции
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Временная Сложность Поиска по Индексу в LinkedList
Это фундаментальный вопрос о внутреннем устройстве LinkedList и почему он подходит для одних операций, но не для других.
Краткий Ответ
Временная сложность поиска по индексу в LinkedList: O(n)
Это основной недостаток LinkedList по сравнению с ArrayList.
Почему O(n)?
LinkedList — это связный список, а не массив:
ArrayList (массив):
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
0 1 2 3 4
Доступ к get(2) = O(1)
Просто берём элемент по индексу 2 сразу.
LinkedList (связный список):
head → [A|next] → [B|next] → [C|next] → [D|next] → [E|null]
0 1 2 3 4
Доступ к get(2):
1. Начинаем с head (A)
2. Переходим к next (B)
3. Переходим к next (C) ← вот это нужно!
Нужно пройти через все узлы до индекса!
Сложность: O(n)
Пошаговый Анализ
LinkedList.get(index) реализация:
public E get(int index) {
checkElementIndex(index);
return node(index).item; // ← вызов node()
}
private Node<E> node(int index) {
// if (index < size >> 1) {
// Начинаем с head
Node<E> x = first;
for (int i = 0; i < index; i++) { // ← цикл до index
x = x.next; // ← шаг за шагом
}
return x;
}
Пример для LinkedList размером 1000:
get(0): 0 шагов → O(1) ✓ быстро
get(1): 1 шаг
get(10): 10 шагов
get(500): 500 шагов ← половина списка!
get(999): 999 шагов ← почти весь список
В худшем случае (get в конец): O(n)
В среднем случае: O(n/2) = O(n)
Оптимизация: Поиск с Обеих Сторон
Интересно, что Java LinkedList оптимизирована:
private Node<E> node(int index) {
// Если индекс ближе к началу
if (index < (size >> 1)) { // size >> 1 = size / 2
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// Если индекс ближе к концу — начинаем с конца!
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev; // Идём назад
}
return x;
}
}
Результат оптимизации:
get(0): 0 шагов → O(1) быстро
get(500): 250 шагов (вместо 500) → O(n) всё равно
get(999): 0 шагов (начинаем с end) → O(1) быстро!
Время сложности остаётся O(n), но коэффициент улучшен!
Сравнение ArrayList vs LinkedList
ArrayList LinkedList Сравнение
get(index) O(1) O(n) ArrayList в n раз быстрее!
add(конец) O(1) амортиз. O(1) Одинаково
add(начало) O(n) O(1) LinkedList в n раз быстрее!
add(середина) O(n) O(n) + O(n) ArrayList лучше
remove(конец) O(1) O(1) Одинаково
remove(начало) O(n) O(1) LinkedList в n раз быстрее!
remove(середина) O(n) O(n) + O(n) ArrayList лучше
iteration O(n) O(n) Одинаково
Практический Пример
public class LinkedListPerformanceTest {
public static void main(String[] args) {
int size = 100_000;
// Тест ArrayList
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) {
arrayList.add(i);
}
// Тест LinkedList
List<Integer> linkedList = new LinkedList<>(arrayList);
// Доступ к элементу в середине 1000 раз
int index = size / 2;
// ArrayList
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int value = arrayList.get(index);
}
long arrayTime = System.nanoTime() - start;
// LinkedList
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int value = linkedList.get(index);
}
long linkedTime = System.nanoTime() - start;
System.out.println("ArrayList: " + arrayTime / 1_000 + " us");
System.out.println("LinkedList: " + linkedTime / 1_000 + " us");
System.out.println("Разница: " + (linkedTime / arrayTime) + "x");
}
}
// Ожидаемый результат:
// ArrayList: 1-5 us
// LinkedList: 50,000-100,000 us
// Разница: 10,000-100,000x медленнее!!!
Почему Вообще Используют LinkedList?
LinkedList хорош для:
- Вставки/удаления в начале:
List<Integer> list = new LinkedList<>();
list.add(0, 100); // O(1) — просто вставить в начало
list.remove(0); // O(1) — просто удалить начало
- Частые итерации с удалением:
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String item = it.next();
if (shouldRemove(item)) {
it.remove(); // O(1) — просто обновить связи
}
}
- Очереди (Queue интерфейс):
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // add
queue.poll(); // remove from front - O(1)
LinkedList плохо для:
- Случайный доступ по индексу — O(n)
- Бинарный поиск — работает, но медленно O(n log n)
- Большие листы с частым доступом — деградация до неприемлемого времени
Реальная Проблема
// ❌ ПЛОХО — O(n²)
LinkedList<String> list = new LinkedList<>(/* 1000 элементов */);
for (int i = 0; i < list.size(); i++) { // 1000 итераций
String item = list.get(i); // O(n) каждая!
}
// Итого: 1000 * 500 = 500,000 операций!
// ✅ ХОРОШО — O(n)
for (String item : list) { // iterator
// O(n) всего
}
// ✅ ХОРОШО — O(n)
for (Iterator<String> it = list.iterator(); it.hasNext();) {
String item = it.next();
// O(n) всего
}
Как Итерировать LinkedList Правильно
❌ Неправильно — O(n²):
for (int i = 0; i < linkedList.size(); i++) {
Element e = linkedList.get(i); // O(n) каждый раз!
}
✅ Правильно — O(n):
for (Element e : linkedList) {
// Использует iterator
}
// Эквивалентно:
Iterator<Element> it = linkedList.iterator();
while (it.hasNext()) {
Element e = it.next(); // O(1) каждый раз
}
Временная Сложность LinkedList.get() В Деталях
Худший случай: O(n)
get(size - 1) на LinkedList из 1 млн элементов
→ нужно пройти через 1 млн узлов
Лучший случай: O(1)
get(0) или get(size - 1)
→ начинаем с first или last узла
Средний случай: O(n/2) = O(n)
get(size/2)
→ нужно пройти через половину (но это всё ещё O(n))
Заключение
LinkedList.get(index) = O(n)
Основные факты:
- ✓ Нужно пройти через узлы до нужного индекса
- ✓ Даже с оптимизацией (поиск с обеих сторон) это O(n)
- ✓ Не используйте LinkedList для частого random access
- ✓ Используйте Iterator для прохода — это O(1) за элемент
- ✓ Для random access используйте ArrayList — это O(1)
- ✓ LinkedList отличный для Queue/Deque операций
При разработке: Если вам нужен get(index), используйте ArrayList. LinkedList предназначен для операций начала/конца списка.