Как работает метод get() в LinkedList?

Метод get() в LinkedList

Метод get() в LinkedList — это один из самых часто используемых методов при работе со списками. Понимание его работы критично для эффективного использования структуры данных.

Основное назначение

Метод get() возвращает элемент списка по указанному индексу:

LinkedList<String> list = new LinkedList<>();
list.add("first");
list.add("second");
list.add("third");

String element = list.get(1);  // Возвращает "second"
System.out.println(element);   // Выведет: second

Сигнатура метода

public E get(int index)

• index — индекс элемента (от 0)
• Возвращает — элемент на указанной позиции
• Выброс исключения — IndexOutOfBoundsException если индекс вне границ

Внутренняя реализация

LinkedList — это двусвязный список (каждый узел имеет ссылки на предыдущий и следующий элемент). Метод get() использует оптимизацию:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private Node<E> node(int index) {
    if (index < (size >> 1)) {
        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()

1. Проверка корректности индекса

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

2. Выбор стартовой позиции Оптимизация (size >> 1 это деление на 2):

• Если index < size/2 → начинаем с first (начало списка)
• Иначе → начинаем с last (конец списка)

3. Итерация к нужному узлу Проходим по ссылкам next или prev до достижения нужного индекса.

4. Возврат значения Возвращаем item из найденного узла.

Сложность операции

Временная сложность: O(n) В худшем случае нужно пройти половину списка. Несмотря на оптимизацию с обоих концов, это медленнее, чем get() в ArrayList (O(1)).

Пример:

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);
}

int val1 = list.get(5);      // ~5 итераций
int val2 = list.get(999);    // ~1 итерация
int val3 = list.get(500);    // ~500 итераций

Пространственная сложность: O(1)

Метод не использует дополнительную память, пропорциональную размеру списка.

Сравнение с ArrayList

ArrayList.get()

ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    array.add(i);
}
int value = array.get(500);  // O(1) — прямой доступ к индексу

ArrayList хранит элементы в массиве, поэтому доступ по индексу O(1).

Обработка ошибок

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");

try {
    String element = list.get(5);  // IndexOutOfBoundsException
} catch (IndexOutOfBoundsException e) {
    System.out.println("Индекс вне границ: " + e.getMessage());
}

Практические примеры

1. Итерирование по LinkedList

LinkedList<String> list = new LinkedList<>();
list.add("first");
list.add("second");
list.add("third");

// Плохо — O(n²) сложность
for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
}

// Хорошо — O(n) сложность
for (String element : list) {
    System.out.println(element);
}

// Хорошо — O(n) сложность
list.forEach(System.out::println);

2. Получение первого и последнего элемента

LinkedList<Integer> list = new LinkedList<>();

// Не эффективно
int first = list.get(0);
int last = list.get(list.size() - 1);

// Эффективно — O(1)
int first = list.getFirst();
int last = list.getLast();

3. Поиск элемента

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

if (list.size() > 1) {
    String second = list.get(1);
}

int index = list.indexOf("banana");
if (index != -1) {
    String found = list.get(index);
}

Когда использовать LinkedList

LinkedList оптимален для:

• Частые вставки/удаления в начале или конце — O(1)
• Небольшие списки — где O(n) get() не критичен
• Когда не нужен случайный доступ — используйте итератор

Использование get() в цикле на LinkedList — антипаттерн. Предпочитайте:

• Enhanced for loop
• Iterator
• forEach()
• Stream API

Резюме

Метод get() в LinkedList работает путем итерации от ближайшего конца списка, что дает оптимизацию но все равно имеет O(n) временную сложность. Для частого случайного доступа лучше использовать ArrayList, а LinkedList оптимален для операций с началом/концом списка.