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

Question

Я пытаюсь удалить некоторые элементы из ArrayList<String>

for(int i=0; i<myList.size(); i++) 
{ 
    if(myList.get(i).contains("foo")) 
    { 
     myList.remove(i); 
    } 
} 

Это, однако, оставляет «пустые места» в моем списке. Я хотел бы, чтобы в списке оставались пустые элементы, и после итерации через него он уменьшался до необходимого размера.

Есть ли разумный способ сделать это без необходимости переключаться на LinkedList?

Answer 1

Это, однако, оставляет «пустые места» в моем списке.

Нет, это не так. Он полностью удаляет записи из списка. Другие элементы перемещаются соответствующим образом. То, что это делает, сделайте так, как вы написали, пропустите проверку для следующей записи ... потому что это будет «перетасовано», чтобы быть элементом i, но вы увидите следующий элемент: i + 1.

Один простой способ избежать этого, чтобы работать в обратном направлении вместо:

for (int i = myList.size() - 1; i >= 0; i--) { 
    if (myList.get(i).contains("foo")) { 
     myList.remove(i); 
    } 
} 

Или использовать итератор, как указано в других ответах, конечно. Оба будут работать - приведенный выше код может быть немного более эффективным, если вы удаляете несколько записей, тем не менее, поскольку к тому времени, когда вы дойдете до начала, будет меньше изменений. Маловероятно, что это будет значительным.

Очень жаль, что для того, чтобы использовать решение итератора вы должны использовать итератор явно - вы не можете удалить из коллекции во время использования enhanced for loop.

Answer 2

Используйте Iterator и позвоните по номеру Iterator.remove().

Iterator it = myList.iterator(); 
while(it.hasNext()) { 
    if (it.next().contains("foo")) { 
     it.remove(); 
    } 
} 

Таким образом, вы также избежать неприятностей для уменьшения размера списка, опираясь на него как условие выхода к вашей петле, и доступ к нему с помощью индексов, которые могут быть различными.

Конечно, итерация через список назад также будет работать.

Answer 3

Умный способ, которым вы ищите, является интерфейс Iterator. Например:

Iterator<String> it = list.iterator(); 
while (it.hasNext()) { 
    String nextItem = it.next(); 
    if (nextItem.contains("foo")) { 
     it.remove(); 
    } 
} 

Answer 4

После того, как вы удалите список, будет автоматически уменьшаться.

Предположим, вы удалите элемент по индексу 3, этот элемент будет удален, список будет сокращаться, а элемент, который был в индексе 4, будет иметь индекс 3 после удаления.

Вы должны сделать это:

for(int i=0; i<myList.size(); i++) 
{ 
    if(myList.get(i).contains("foo")) 
    { 
     myList.remove(i); 
     // as element is removed, next element will have decremented index 
     i--; 
    } 
} 

Answer 5

Под влиянием Scala и функционального программирования, я бы порекомендовал вам просто скопировать значения в новый список для неизменности.

List<String> filtered = new ArrayList<String>(); 
for (String s : myList) { 
    if (!s.contains("foo")) { 
     filtered.add(s); 
    } 
} 

Я бы также рекомендовал 2 LIBS попробовать: Guava и lambdaj

Answer 6

ArrayList поддерживает массив позади сцены. Я хочу углубиться в исходный код java.util.ArrayList и java.util.LinkedList.

Прежде всего, ArrayList поддерживает массив за кулисами. Когда вы создаете экземпляр ArrayList, он создает массив размером 10 и растет, пока вставлены элементы. Размер увеличивается до 3 (размер)/2 +1

Вот исходный код.

Размер по умолчанию для сортировки. Посмотрите на constructer code.

public ArrayList() { 
     this(10); 
    } 

его размер увеличивается до 3 (размер)/2 + 1 здесь является source code. ArrayList#ensureCapacity метод называется INSITE ArrayList#add

public void ensureCapacity(int minCapacity) { 
     modCount++; 
     int oldCapacity = elementData.length; 
     if (minCapacity > oldCapacity) { 
      Object oldData[] = elementData; 
      int newCapacity = (oldCapacity * 3)/2 + 1; 
      if (newCapacity < minCapacity) 
       newCapacity = minCapacity; 
      // minCapacity is usually close to size, so this is a win: 
      elementData = Arrays.copyOf(elementData, newCapacity); 
     } 
    } 

При удалении какой-либо элемент из ArrayList. Он удаляется из списка, а другие элементы списка перемещаются вниз до места удаленных объектов. Обратите особое внимание, ссылка на этот объект установлена ​​равной нулю, и объект становится доступным для GC, но для ArrayList все еще имеется ссылка. Размер массива за ArrayList такой же.

Вот source code

public E remove(int index) { 
     rangeCheck(index); 

     modCount++; 
     E oldValue = elementData(index); 

     int numMoved = size - index - 1; 
     if (numMoved > 0) 
      System.arraycopy(elementData, index+1, elementData, index, 
           numMoved); 
     elementData[--size] = null; // Let gc do its work 

     return oldValue; 
    } 

Как ответил Джон Скит, когда элемент удаляется следующий элемент для удаленного элемента будет находиться в удаленном месте пунктов.

Однако выделенное пространство памяти остается неизменным после удаления. java.util.LinkedList - эта проблема. Все элементы внутри LinkedList динамически распределяются и освобождаются (это, конечно же, работа GC)

java.util.LinkedList поддерживает doubly linked list за кулисами. Каждая операция добавления и удаления изменяет пространство памяти, используемое LinkedList. Элемент удален, а ссылка на элемент из предыдущего и последующих элементов обновляется.

Here is the source code :

private Entry<E> entry(int index) { 
     if (index < 0 || index >= size) 
      throw new IndexOutOfBoundsException("Index: "+index+ 
               ", Size: "+size); 
     Entry<E> e = header; 
     if (index < (size >> 1)) { 
      for (int i = 0; i <= index; i++) 
       e = e.next; 
     } else { 
      for (int i = size; i > index; i--) 
       e = e.previous; 
     } 
     return e; 
    } 

Я предполагаю, что GC собирает предметы, как только он удаляется, я знаю, он не уверен. Но удаленная ячейка памяти является кандидатом в GC. Будьте осторожны с ссылкой на объект и сам объект.

Как ArrayList, так и LinkedList удаляют элементы, в то время как ArrayList по-прежнему сохраняет ссылку на типы объектов и пространство памяти для примитивных типов, связанный список также удаляет ссылки и пространство памяти. По крайней мере, ссылки и память также будут иметь право на GC.

Answer 7

Нет, он не покинет «пустые места» в вашем списке, но вы пропустите удаление всех необходимых элементов из вашего списка.

Давайте попробуем пояснить ниже. У меня есть ArrayList с 4 элементами. (А, б, в, г).

for (int i = 0; i < list.size(); i++) { 
      if (((String) list.get(i)).contains("c")) { 
       list.remove(i); 
      } 
      if (((String) list.get(i)).contains("b")) { 
       list.remove(i); 
      } 
     } 

for (int i = 0; i < list.size(); i++) { 
     System.out.print(list.get(i)+" "); 
    } 

Результат: C D

При перемещении списка в прямом направлении, я попытался удалить элементы (с, б), но до сих пор элемент с присутствует в моем списке.

Чтобы избежать этого, мы можем перемещаться в обратном направлении, как показано ниже.

for (int i = list.size() - 1; i >= 0; i--) { 
      if (((String) list.get(i)).contains("a")) { 
       list.remove(i); 
      } 
      if (((String) list.get(i)).contains("c")) { 
       list.remove(i); 
      } 
     } 

     for (int i = 0; i < list.size(); i++) { 
      System.out.print(list.get(i) + " "); 
     } 

Результат: б d