Я пытаюсь удалить определенные элементы из ArrayList<String>
for(int i=0; i<myList.size(); i++)
{
if(myList.get(i).contains("foo"))
{
myList.remove(i);
}
}
Однако это оставляет "пустые места" в моем списке. Я хотел бы, чтобы в списке оставались пустые элементы и после итерации через него сжимались до необходимого размера.
Есть ли разумный способ сделать это, не переключаясь на LinkedList?
Однако это оставляет "пустые места" в моем списке.
Нет, это не так. Он полностью удаляет записи из списка. Другие элементы перемещаются соответствующим образом. То, что он делает с тем, как вы написали, пропускает проверку для следующей записи... потому что это будет "перетасовано вниз", чтобы быть элементом i, но вы затем посмотрите на элемент i + 1.
Один простой способ избежать этого - вместо этого работать назад:
for (int i = myList.size() - 1; i >= 0; i--) {
if (myList.get(i).contains("foo")) {
myList.remove(i);
}
}
Или используйте итератор, как указано в других ответах, конечно. Оба будут работать - приведенный выше код может быть немного более эффективным, если вы удаляете несколько записей, тем не менее, поскольку к тому времени, когда вы дойдете до начала, будет меньше изменений. Маловероятно, что это будет значительным.
Несчастливо, что для использования решения итератора вам нужно явно использовать итератор - вы не можете удалить из коллекции, используя усиленный для цикла.
Используйте Iterator и вызовите Iterator.remove().
Iterator it = myList.iterator();
while(it.hasNext()) {
if (it.next().contains("foo")) {
it.remove();
}
}
Таким образом вы также избегаете проблем для уменьшения размера списка, полагаясь на него как условие выхода на ваш цикл, и обращаетесь к нему с использованием индексов, которые могут быть разными.
Конечно, итерация через список назад также будет работать.
Разумным способом, который вы ищете, является интерфейс Iterator. Например:
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String nextItem = it.next();
if (nextItem.contains("foo")) {
it.remove();
}
}
Под влиянием Scala и функционального программирования я бы рекомендовал вам просто скопировать ваши значения в новый список для неизменяемости.
List<String> filtered = new ArrayList<String>();
for (String s : myList) {
if (!s.contains("foo")) {
filtered.add(s);
}
}
Я бы также рекомендовал 2 библиотеки для тестирования: Guava и lambdaj
ArrayList поддерживает массив за сценой. Я хочу глубоко в исходный код java.util.ArrayList и java.util.LinkedList.
Прежде всего, ArrayList поддерживает массив за кулисами. Когда вы создаете экземпляр ArrayList, он создает массив размером 10 и растет, пока вставлены элементы. Размер увеличивается до 3 (размер)/2 +1
Вот исходный код.
Размер по умолчанию для списка адресов. Посмотрите код конструктора.
public ArrayList() {
this(10);
}
его размер увеличивается до 3 (размер)/2 + 1. Вот исходный код . ArrayList # securityCapacity метод называется 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 одинаковый.
Вот исходный код
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 поддерживает дважды связанный список за кулисами. Каждая операция добавления и удаления изменяет пространство памяти, используемое LinkedList. Элемент удаляется, и ссылка на элемент из его предыдущего и последующих элементов обновляется.
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.
После удаления списка автоматически будет уменьшаться.
Предположим, что вы удаляете элемент в индексе 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--;
}
}
Нет, он не оставляет "пустых мест" в вашем списке, но вы пропустите удаление всех необходимых элементов из вашего списка.
Давайте попробуем пояснить ниже. У меня есть 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)+" ");
}
Результат: a c d
При перемещении списка в прямом направлении я попытался удалить элементы (c, b), но элемент c присутствует в моем списке.
Чтобы этого избежать, мы можем двигаться в обратном направлении, как показано ниже.
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) + " ");
}
Результат: b d