Страницы

Поиск по вопросам

пятница, 31 января 2020 г.

Удаление элементов в ArrayList

#java


Как известно, после удаления элемента из середины списка ArrayList, часть массива,
которая следовала после данного элемента, перезаписывается на позицию влево, чтоб перекрыть
пустую ячейку. Если стоит задача удалить несколько элементов из середины списка одной
операцией (т. е. чтоб избежать многоразовой перезаписи массива), как это можно сделать?    


Ответы

Ответ 1



Как обычно - наследованием: public class MyArrayList extends ArrayList { public void remove(int startIndex, int endIndex) { //здесь и придумывайте свой гениальный код } }

Ответ 2



Используйте методы removeAll и sublist. sublist - для создания коллекции (пула элементов), которую нужно удалить. А removeAll уже для удаления элементов. Пример кода: public static void main(String[] args){ List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.add(8); List sublist = list.subList(2,5); // Удаляем с 2 по 4й элемент включительно list.removeAll(sublist); System.out.println(list); //[1, 2, 6, 7, 8] } } //В одну строку public static void main(String[] args){ List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.add(8); list.removeAll(list.subList(2,5)); System.out.println(list); //[1, 2, 6, 7, 8] } }

Ответ 3



использовать removeAll(Collection c) наследовать и использовать removeRange(int fromIndex, int toIndex)

Ответ 4



Не нужно ничего наследовать, вреда от этого больше, чем пользы. Нефинальные классы контейнеров были ошибкой. Условимся, что из списка длины n нужно удалить m элементов. Формализую вопрос: m удалений, по O(n) каждое, стоит O(m×n); как можно ускорить процесс? Пользуясь тем, что ArrayList#set стоит O(1), нужно сначала отметить все элементы как удалённые: list.set(index, REMOVED); где REMOVED — это приватная константа, которая в обычных условиях в списке не окаженся: private static final Object REMOVED = new Object(); Дженерики будут мешать вставке произвольных Objectов, поэтому придётся воспользоваться стиранием и сделать unchecked cast. ((List) list).set(index, REMOVED); После этого в листе есть посторонние элементы. Осторожно: list.get(removedIndex) приведёт к ClassCastException, подробнее — см. heap pollution. Теперь нужно удалить все элементы, которые отмечены для удаления. Вызов list.remove(REMOVED) удалит только первое вхождение; нам нужен метод removeAll, который удалит все элементы переданной коллекции из данного списка: list.removeAll(COLLECTION_OF_REMOVED); где private static final Collection COLLECTION_OF_REMOVED = Collections.singleton(REMOVED); Это произойдёт за O(n), после чего объектов REMOVED в списке не будет и его снова можно будет безопасно читать. Gist с решением проблемы и комментариями См. также метод removeIf из Java 1.8.

Комментариев нет:

Отправить комментарий