一、List 去重方式汇总

1、使用两个 for 循环

1
2
3
4
5
6
7
8
9
10
public static List removeDuplicate(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        for (int j = i+1; j < list.size(); j++) {
            if(list.get(i).equals(list.get(j))) {
                list.remove(j);
            }
        }
    }
    return list;
}

2、使用 contains 方法

1
2
3
4
5
6
7
8
9
10
public static List removeDuplicate(List<Integer> list) {
	List<Integer> newList = new ArrayList<>();
	for (int i = 0; i < list.size(); i++) {
		if(!newList.contains(list.get(i))) {
			newList.add(list.get(i));
		}
	}
	list = newList;
	return list;
}

contains 方法中也是使用的 for 循环。

3、使用 Set 去重

1
2
3
4
5
6
public static List removeDuplicate(List<Integer> list) {
	Set<Integer> set = new HashSet<>(list);
	list.clear();
	list.addAll(set);
	return list;
}

使用 HashSet 去重时，可能会打乱列表中元素的顺序。可以选择使用 LinkedHashSet。

1
2
3
4
5
6
public static List removeDuplicate(List<Integer> list) {
	Set<Integer> set = new LinkedHashSet<>(list);
	list.clear();
	list.addAll(set);
	return list;
}

4、使用 steam API

1
2
3
4
public static List removeDuplicate(List<Integer> list) {
	List newList = list.stream().distinct().collect(Collectors.toList());
	return newList;
}

二、List 循环过程中调用 remove 分析

在循环遍历列表的同时 remove 其中的元素，在一定的情况下会报错。

1、当需要 remove 的元素有两个相邻，后一个不能被 remove

1
2
3
4
5
6
7
8
9
10
11
List<String> list = new ArrayList<>(
	Arrays.asList("aa", "bb", "bb", "aa", "bb", "c", "s", "bb", "c")
);

for(int i = 0; i < list.size(); i++) {
	if (list.get(i).equals("bb")) {
		list.remove(i);
	}
}

System.out.println(list);

输出结果：

1
[aa, bb, aa, c, s, c]

索引 2 和 3 处的 bb 为指定删除元素，两者相邻，循环遍历 remove 后，无法将两个元素都删除。JDK8 中 ArrayList 的 remove 方法源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; // clear to let GC do its work

	return oldValue;
}

remove 方法中删除指定元素，做法是将要删除元素索引位置之后的元素向前移动一位，然后将 list 末尾元素置为空。

该方法与 for 循环一起使用时，如果不做特殊处理，无法删除两个相邻的都需要删除的元素。因为删除掉当前索引位置的元素之后，后面的元素向前移动了一位移动到了当前遍历位置，在 i++ 之后就把相邻元素中的第二个跳过了。

可以改写成如下代码来结局：

1
2
3
4
5
6
7
8
9
10
11
12
List<String> list = new ArrayList<>(
	Arrays.asList("aa", "bb", "bb", "aa", "bb", "c", "s", "bb", "c")
);

int idx = 0;
while (idx < list.size()) {
	if (list.get(idx).equals("bb")) {
		list.remove(idx);
	} else {
		idx++;
	}
}

1.1 倒序遍历来解决

如果还是想要使用 for 循环进行遍历，可以采用倒序遍历的方法来解决上述问题，因为删除元素之后，删除元素后面的元素是向前（索引值更小的方向）移动的，倒序不会跳过没有遍历的元素。

1
2
3
4
5
for(int i = list.size() - 1; i >= 0; i--) {
	if (list.get(i).equals("bb")) {
		list.remove(i);
	}
}

1.2 迭代器来解决

1
2
3
4
5
6
Iterator<T> iterator = list.iterator();
while (iterator.hasNext()) {
	if (iterator.next().equals("bb")) {
		iterator.remove();
	}
}

使用迭代器来进行 list 的遍历不会跳过没有遍历的元素，JDK8 的 ArrayList 内部类 Itr 的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

迭代器使用 next 方法来返回下一个元素，在每一次执行 next 方法之后，cursor 的值为下一个元素的索引，lastRet 的值为 next 方法刚返回的元素的索引。

之后调用迭代器的的 remove 方法，在移除了 lastRet 位置的元素之后，cursor 赋值为 lastRet，索引还在刚删除元素的位置上，接下来再次执行 next 方法时，还会返回此位置的元素，也就不会漏掉没有遍历过的元素。

使用迭代器时有一个基本法则：如果对正在被迭代的集合进行结构上的改变（即对该集合使用 add、remove 或 clear 方法），那么迭代器就不再合法（并且在其后使用该迭代器将会有 ConcurrentModificationException 异常被抛出），但如果迭代器调用了它自己的 remove 方法，那么这个迭代器就仍然是合法的。

像下面的例子一样，都会产生上述异常：

1
2
3
4
5
6
7
8
9
10
11
12
13
Iterator<String> iterator = list.iterator();  
while(iterator.hasNext()) {  
    if(iterator.next().equals("bb")) {  
        iterator.remove();  
        list.add("exception");  
    }  
}

for (String string : list) {
	if(string.equals("bb")) {
        list.remove(string);
	}
}

相关链接

迭代器 Iterator | z2huo

迭代器 ListIterator | z2huo

Java 集合框架中的 List 接口 | z2huo

Java 集合框架中的 ArrayList 类 | z2huo

Java 集合框架中的 LinkedList 类 | z2huo

[[迭代器 Iterator]]

[[迭代器 ListIterator]]

[[List]]

[[ArrayList]]

[[LinkedList]]

OB tags

#Java