Можно ли использовать метод get с индексом в LinkedList?

Можно ли использовать метод get с индексом в LinkedList?

Краткий ответ

Да, LinkedList имеет метод get(int index) и его можно использовать, но это крайне неэффективно. Временная сложность такой операции составляет O(n) вместо O(1) для обычного List.

Структура LinkedList

LinkedList — это двусвязный список, где каждый элемент содержит:

• Значение данных
• Ссылку на следующий узел
• Ссылку на предыдущий узел

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Метод get() в LinkedList

Да, метод существует:

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Spring");
list.add("Hibernate");

// Метод get работает!
String element = list.get(1);  // Вернёт "Spring"
System.out.println(element);   // Выведет: Spring

Почему это неэффективно

ArrayList: O(1) доступ

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("First");
arrayList.add("Second");

String element = arrayList.get(0);  // O(1) - прямой доступ по индексу
// Внутри просто: return elementData[index]

LinkedList: O(n) доступ

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("First");
linkedList.add("Second");
linkedList.add("Third");

String element = linkedList.get(2);  // O(n) - нужно пройти по всем узлам
// Внутри происходит:
// node = head
// while (index > 0) {
//     node = node.next;  // Переходим к следующему узлу
//     index--;
// }
// return node.item

Реальный код внутри LinkedList

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

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;
    }
}

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

Сравнение производительности

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

// Заполняем оба списка 100000 элементами
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// ArrayList: быстро
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    arrayList.get(i);  // O(1)
}
long arrayTime = System.nanoTime() - startTime;

// LinkedList: медленно
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    linkedList.get(i);  // O(n) для каждого get!
}
long linkedTime = System.nanoTime() - startTime;

System.out.println("ArrayList: " + arrayTime);
System.out.println("LinkedList: " + linkedTime);
// LinkedList обычно медленнее в 100+ раз!

Когда LinkedList эффективен

// 1. Добавление в начало/конец - O(1)
LinkedList<String> list = new LinkedList<>();
list.addFirst("First");    // O(1)
list.addLast("Last");      // O(1)

// 2. Удаление в начало/конце - O(1)
list.removeFirst();         // O(1)
list.removeLast();          // O(1)

// 3. Итерация - O(n)
for (String item : list) {  // Использует iterator (O(1) переходы)
    System.out.println(item);
}

// 4. Итератор с удалением - O(1)
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    it.remove();  // O(1)
}

Правильное использование LinkedList

// ❌ ПЛОХО - использование get() в цикле
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
    String item = list.get(i);  // O(n) для каждой итерации!
    // Полная сложность: O(n²)
}

// ✅ ХОРОШО - использование итератора
for (String item : list) {
    // O(n) для всего цикла
}

// ✅ ХОРОШО - прямой итератор
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String item = it.next();
    // O(n) для всего цикла
}

// ✅ ХОРОШО - операции в начале/конце
list.addFirst("Element");
list.removeLast();

Практический пример: правильный выбор структуры

// Случай 1: Нужен индексный доступ
List<String> data = new ArrayList<>();  // O(1) для get()
for (int i = 0; i < data.size(); i++) {
    System.out.println(data.get(i));
}

// Случай 2: Нужны операции в начале/конце + итерация
Queue<String> queue = new LinkedList<>();  // O(1) для add/remove
queue.offer("Task1");
queue.poll();
for (String task : queue) {
    process(task);
}

// Случай 3: Частые вставки/удаления в середину
List<String> list = new LinkedList<>();  // O(1) для add/remove в итератор
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // O(1)
    }
}

Заключение

Таблица: Сложность операций

*в худшем случае

Вывод: Хотя get(index) в LinkedList технически работает, его использование — это антипаттерн. LinkedList оптимален для операций в начале/конце и итерации, но не для индексного доступа. Используйте ArrayList если нужен индексный доступ, и LinkedList если нужны операции в начале/конце.