Удаление диапазона (хвоста) из списка

Есть ли эффективный метод для удаления диапазона - например, хвост - из X элементов из List, например. LinkedList в Java?

Очевидно, можно удалить последние элементы один за другим, что должно привести к производительности уровня O (X). По крайней мере, для экземпляров LinkedList должно быть возможно иметь производительность O (1) (путем установки ссылок вокруг первого элемента, который нужно удалить, и установки ссылок заголовка/хвоста). К сожалению, я не вижу никакого метода в пределах List или LinkedList, чтобы удалить последние элементы одновременно.

В настоящее время я думаю о замене списка с помощью List.subList(), но я не уверен, что он имеет равную производительность. По крайней мере, это было бы более ясно в коде, с другой стороны, я потерял бы дополнительные функции, которые предоставляет LinkedList.

В основном я использую List как стек, для которого LinkedList представляется лучшим вариантом, по крайней мере, относительно семантики.

Ответ 1

subList(list.size() - N, list.size()).clear() - рекомендуемый способ удаления последних элементов N. Действительно, Javadoc для subList специально рекомендует эту идиому:

Этот метод устраняет необходимость в явных операциях диапазона (такого типа, который обычно существует для массивов). Любая операция, которая ожидает список, может использоваться как операция диапазона, передавая представление сублиста вместо целого списка. Например, следующая идиома удаляет ряд элементов из списка:
 list.subList(from, to).clear();

В самом деле, я подозреваю, что эта идиома может быть более эффективной (хотя и постоянным фактором), чем вызов removeLast() N раз, только потому, что как только он найдет N th-to-last node, он необходимо обновить постоянное количество указателей в связанном списке, а не обновлять указатели каждого из последних узлов N по одному за раз.

Ответ 2

Помните, что subList() возвращает представление исходного списка, что означает:

Любая модификация, сделанная для представления, будет отражена в исходном списке
Возвращаемый список не является LinkedList - это внутренняя реализация List, которая не является сериализуемой

В любом случае использование removeFirst() или removeLast() должно быть достаточно эффективным, потому что посылка первого или последнего элемента связанного списка в Java является операцией O(1) - внутри, LinkedList содержит указатели на оба конца список и удаление одного из них так же просто, как перемещение указателя в одну позицию.

При удалении элементов m вы застряли в производительности O(m) с LinkedList, хотя, как ни странно, ArrayList может быть лучшим вариантом, поскольку удаление элементов в конце ArrayList так же просто, как перемещение указателя указателя (обозначая конец массива) одной позицией слева, и никакие мусорные узлы не висят, как в случае с LinkedList. Лучший выбор? попробуйте оба подхода, профилируйте их и позвольте номерам говорить сами за себя.