如何高效地从ArrayList或String数组中删除所有空元素？

Question

我尝试使用如下循环：

// ArrayList tourists

for (Tourist t : tourists) {
    if (t != null) {     
        t.setId(idForm); 
    }   
}

但这不是一个好的解决方案。有没有人可以提供更好的建议？

---

一些有用的基准测试，以做出更好的决策：

While 循环，For 循环和迭代器性能测试

- Juan de Dios

---

要使用Iterator吗？查看java-doc。http://download.oracle.com/javase/6/docs/api/java/util/Iterator.html＃remove（＆#8203;） - Nishant

由于您的基准参考，似乎您将“好”/“更好”定义为基准化的“效率”。而您的参考本身似乎得出了答案：“迭代器循环最慢，for循环和while循环之间的差异并不那么显著。” - cellepo

Answer 1

尝试：

tourists.removeAll(Collections.singleton(null));

阅读Java API。对于不可变列表（例如使用Arrays.asList创建的列表），代码将抛出java.lang.UnsupportedOperationException；有关更多详细信息，请参见此答案。

- Lithium

---

List.removeAll() 的时间复杂度为 n^2。就是这样。 - Hemanth

对于Java 8或更高版本，请参见下面@MarcG的答案。 - Andy Thomas

你能详细说明一下你是如何得出这个时间复杂度的吗？因为对我来说，对于ArrayList和LinkedList来说，它看起来都是 O(n)。 - Helder Pereira

这里的N^2并没有意义，因为两个集合的大小并不相关。最终复杂度应该是N*M，但并非总是如此。ArrayList覆盖了您链接的方法定义，以减少进行多次删除的开销，从而将其转换为N*T(c.contains)；因此，如果参数c中的集合是HashSet，则它将是O(N)；如果是TreeSet，则它将是O(N*log M)。同样的时间复杂度适用于LinkedList，在那里他们不必付出太多努力，因为按定义删除很便宜（如果您有节点的引用）。 - Helder Pereira

这句话的意思是：“不，它不是n，而是n*m，其中m是元素数量，在这种情况下是一个空的单例，即1。时间复杂度为O(n)。您可以在此处查看源代码，并且可以看到它只读取和写入列表一次，移动元素以适应被删除的元素。” - Tatarize

Answer 2

截至2015年，这是最佳方式（Java 8）：

tourists.removeIf(Objects::isNull);

注意： 这段代码将会对固定大小的列表（如使用 Arrays.asList 创建的不可变列表）抛出 java.lang.UnsupportedOperationException 异常。

- MarcG

---

“最好”的定义是什么？它比其他方法更快吗？还是因为简洁而更易读？ - Andy Thomas

这种写法不仅因为简洁而更富表现力。你几乎可以读出它的意思：“如果对象为空，则从游客中移除”。另外，旧的方法是创建一个只含有单个空对象的新集合，然后要求从另一个集合中删除集合的内容。这似乎有点像一个技巧，你觉得呢？至于速度，你说得对，如果列表确实很大并且性能是个问题，我建议测试两种方式。我的猜测是removeIf会更快，但这只是我的猜测。 - MarcG

Arrays.asList 不是不可变的，它是固定大小的。 - turbanoff

@turbanoff 是的，你说得对。它只支持固定大小，我会更新答案的。 - MarcG

Answer 3

list.removeAll(Collections.singleton(null));

如果你在 Arrays.asList 上使用它，它会抛出 UnsupportedException 异常，因为它给你一个不可修改的 Immutable 副本。看下面的代码。它创建一个 Mutable 副本，并且不会抛出任何异常。

public static String[] clean(final String[] v) {
    List<String> list = new ArrayList<String>(Arrays.asList(v));
    list.removeAll(Collections.singleton(null));
    return list.toArray(new String[list.size()]);
}

- AZ_

Answer 4

如果您喜欢不可变的数据对象，或者您不想破坏输入列表，那么您可以使用Guava的谓词。

ImmutableList.copyOf(Iterables.filter(tourists, Predicates.notNull()))

- user1563987

Answer 5

虽不高效，但简短

while(tourists.remove(null));

- Peter Lawrey

---

相反的意思是慢，实际上非常缓慢，如果你有一个很长的列表。 - Gewure

Answer 6

 for (Iterator<Tourist> itr = tourists.iterator(); itr.hasNext();) {
      if (itr.next() == null) { itr.remove(); }
 }

- Mat Mannion

---

当您需要在遍历时删除元素时，这可能会更有用。巧合的是，我正在将元素置空，而不是尝试使用 removeAll(..null..)。谢谢！ - Mustafa

你最好将值设置为null，然后在最后删除。removeAll中的batchRemove遍历列表，并具有读取和写入位置，在迭代列表时仅迭代一次，当其遇到null时，移动读取位置但不移动写入位置。.remove()可能必须每次调用时将整个数组复制。 - Tatarize

Answer 7

Objects类有一个nonNull Predicate，可以与filter一起使用。

例如：

tourists.stream().filter(Objects::nonNull).collect(Collectors.toList());

- JeffF

---

欢迎来到 Stack Overflow。回答问题时，请尽量添加代码解释。请返回并编辑您的答案以包含更多信息。 - Tyler

Answer 8

在Java 8之前，您应该使用：

tourists.removeAll(Collections.singleton(null));

Java 8之后的使用：

tourists.removeIf(Objects::isNull);

这里的问题在于时间复杂度。数组的问题在于删除操作可能需要花费O(n)的时间来完成。在Java中，这实际上是将剩余元素的数组复制移动到替换空位的过程。这里提供的许多其他解决方案都会引发此问题。前者在技术上是O(n*m)，其中m为1，因为它是一个单例null：所以是O(n)。

您应该使用removeAll来删除单例，它内部执行batchRemove()，其中有读取位置和写入位置。并迭代列表。当它遇到null时，它只是将读取位置迭代1次。当它们相同时，它通过；当它们不同时，它继续沿着复制值移动。然后在最后修剪大小。

它实际上在内部执行以下操作：

public static <E> void removeNulls(ArrayList<E> list) {
    int size = list.size();
    int read = 0;
    int write = 0;
    for (; read < size; read++) {
        E element = list.get(read);
        if (element == null) continue;
        if (read != write) list.set(write, element);
        write++;
    }
    if (write != size) {
        list.subList(write, size).clear();
    }
}

从显式的角度来看，这是一个O(n)操作。

唯一可能更快的方法是从列表的两端迭代，并且当你发现一个空值时，将它的值设置为你在末尾找到的值，并将该值递减。然后迭代直到两个值匹配。你会混乱顺序，但相比于留下的值，你设置的值会大大减少。这是一个值得了解的好方法，但对于这里的情况并没有太大帮助，因为 .set() 基本上是免费的，然而，那种形式的删除是你工具箱中有用的工具。

---

for (Iterator<Tourist> itr = tourists.iterator(); itr.hasNext();) {
      if (itr.next() == null) { itr.remove(); }
 }

虽然这看起来足够合理，但迭代器上的 .remove() 在内部调用了：

ArrayList.this.remove(lastRet);

在remove操作中，其中再次出现O(n)的操作。它执行了System.arraycopy()，如果你关心速度，这不是你想要的。这使得它变成了n^2。

还有：

while(tourists.remove(null));

这个算法复杂度是O(m*n^2)。我们不仅仅是遍历列表，而是每次匹配到null时都要重新遍历整个列表。接下来我们需要进行n/2（平均）次System.arraycopy()操作来执行删除动作。

实际上，你可以在更短的时间内对所有有问题的项进行排序，将具有值的项与具有空值的项分开并在末尾进行修剪。至少在理论上来说，System.arraycopy()实际上并不是一个N操作。但理论和实践总是有差距的。

- Tatarize

Answer 9

主要我在使用这个：

list.removeAll(Collections.singleton(null));

但是在学了Java 8之后，我转向使用以下语言：

List.removeIf(Objects::isNull);

- Maged Almaweri

Answer 10

使用Java 8，您可以使用stream()和filter()来实现此操作。

tourists = tourists.stream().filter(t -> t != null).collect(Collectors.toList())

或者

tourists = tourists.stream().filter(Objects::nonNull).collect(Collectors.toList())

更多信息请参考：Java 8 - Streams。

- Jad Chahine

---

这个解决方案使用不可变副本，即--> List<String> listOfString = Arrays.asList("test1",null,"test"); ......也可以！谢谢。 - Anurag_BEHS