В какой структуре данных удаление последнего элемента произойдет быстрее: ArrayList или LinkedList

Удаление последнего элемента: ArrayList vs LinkedList

Правильный ответ: ArrayList удаляет последний элемент БЫСТРЕЕ чем LinkedList. Это частая ошибка у разработчиков, которые думают, что LinkedList всегда лучше для удаления.

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

ArrayList - удаление последнего элемента

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

// Удаление последнего элемента
list.remove(list.size() - 1); // O(1) - очень быстро!

Почему быстро:

• Массив зарезервирован в памяти
• Удаление последнего элемента - просто сдвиг внутреннего pointer'а
• Нет перестановки элементов
• Просто уменьшает size на 1

Time Complexity: O(1)

LinkedList - удаление последнего элемента

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

// Удаление последнего элемента
list.removeLast(); // O(1) - если есть кэш tail pointer'а
// или
list.remove(list.size() - 1); // O(n) - траверсировка!

Почему может быть медленно:

• Если используется remove(list.size() - 1) - нужно найти последний элемент, пройдя список
• LinkedList не имеет индексного доступа
• Нужно пройти по всем n элементам

Time Complexity: O(n) если используется индекс, O(1) если removeLast()

Детальное сравнение

// ArrayList
ArrayList<Integer> arrayList = new ArrayList<>(1000000);
for (int i = 0; i < 1000000; i++) {
    arrayList.add(i);
}

long start = System.nanoTime();
arrayList.remove(arrayList.size() - 1); // ~100 нс
long end = System.nanoTime();
System.out.println("ArrayList: " + (end - start) + " ns");

// LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 1000000; i++) {
    linkedList.add(i);
}

start = System.nanoTime();
linkedList.removeLast(); // ~100 нс - быстро
end = System.nanoTime();
System.out.println("LinkedList.removeLast(): " + (end - start) + " ns");

// LinkedList с индексом - МЕДЛЕННО!
start = System.nanoTime();
linkedList.remove(linkedList.size() - 1); // миллионы нс!
end = System.nanoTime();
System.out.println("LinkedList.remove(index): " + (end - start) + " ns");

Примеры использования

ArrayList - O(1) для последнего элемента

ArrayList<String> stack = new ArrayList<>();
stack.add("item1");
stack.add("item2");
stack.add("item3");

// Удаление последнего - быстро!
String last = stack.remove(stack.size() - 1); // O(1)

LinkedList - O(1) с removeLast()

LinkedList<String> queue = new LinkedList<>();
queue.add("item1");
queue.add("item2");
queue.add("item3");

// Правильно - быстро!
String last = queue.removeLast(); // O(1)

// Неправильно - медленно!
String last = queue.remove(queue.size() - 1); // O(n) - траверсировка!

Когда какую структуру выбирать

Используй ArrayList когда:

// Нужен случайный доступ по индексу
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

String elem = list.get(5000); // O(1) - быстро

// Удаление с конца
list.remove(list.size() - 1); // O(1) - быстро

Используй LinkedList когда:

// Очередь FIFO
LinkedList<Task> queue = new LinkedList<>();
queue.add(task1); // addLast - O(1)
queue.removeFirst(); // O(1)

// Stack LIFO
LinkedList<String> stack = new LinkedList<>();
stack.push("a"); // O(1)
stack.pop(); // removeLast - O(1)

// Частые вставки/удаления в середину
for (int i = 0; i < 1000; i++) {
    list.add(500, new Item()); // LinkedList O(n), но с меньшей константой
}

Частая ошибка

// ❌ НЕПРАВИЛЬНО - медленно для LinkedList
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}
for (int i = list.size() - 1; i >= 0; i--) {
    list.remove(i); // O(n) * n = O(n²)!
}

// ✅ ПРАВИЛЬНО - быстро для LinkedList
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}
while (!list.isEmpty()) {
    list.removeLast(); // O(1)
}

// ✅ ПРАВИЛЬНО - быстро для ArrayList
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}
while (!list.isEmpty()) {
    list.remove(list.size() - 1); // O(1)
}

Таблица операций

Итоговый ответ

ArrayList удаляет последний элемент БЫСТРЕЕ:

• ArrayList: O(1) - просто сдвигает pointer
• LinkedList: O(n) если remove(size()-1), O(1) если removeLast()

Самая частая ошибка - думать, что LinkedList всегда лучше для удаления. На самом деле, это зависит от ПОЗИЦИИ удаления и метода, который вы используете.

Для стека (LIFO) или очереди (FIFO) операций - LinkedList с соответствующими методами (push/pop, add/removeFirst) работает оптимально. Но для произвольного доступа по индексу - ArrayList выигрывает.