本文整理了Java中List結構的不同實作,典型的清單操作及實作方式。
List常用實作
ArrayList
簡介
在這篇文章中,要學習的是Java集合架構中的ArrayList,下面會讨論其屬性、通用場景以及其優缺點。
ArrayList在Java的核心庫中,是以你不需要引入任何額外的庫,隻需要
import
語句就可以使用它:
import java.util.ArrayList
複制代碼
List表示有序的值序列,其中某些值可以出現多次。
ArrayList是在數組基礎上的一種List的實作,會随着添加/删除元素而動态伸縮,其中的元素可以通過索引(從0開始)容易地通路。該實作具有以下特性:
- 随機通路時間複雜度為O(1)
- 添加元素均攤時間複雜度為O(1)
- 插入/删除時間複雜度為O(n)
- 在無序數組上搜尋的時間複雜度為O(n),有序數組上耗時為O(log n)
建立
ArrayList具有多個構造器,我們會在本小節一一介紹。
首先,需要注意ArrayList是一個泛型類,是以你可以通過參數指定任何你需要的類型,編譯器會對其進行驗證。舉例來說,你無法将一個Integer對象插入String類的集合中。同樣,當你需要從集合中擷取對象時也無需做轉換。
使用通用接口List作為變量的類型是一種比較好的做法,這樣可以将變量與特定的實作進行解耦。
預設無參構造函數
List<String> list = new ArrayList<>();
assertTrue(list.isEmpty());
複制代碼
很容易就可以建立一個空的ArrayLis執行個體。
接受初始容量參數的構造函數
List<String> list = new ArrayList<>();
複制代碼
在該方法中,可以指定底層數組的初始化長度,有助于避免在增加新元素時出現不必要的擴容操作。
接受集合參數的構造函數
Collection<Integer> number
= IntStream.range(, ).boxed().collect(toSet());
List<Integer> list = new ArrayList<>(numbers);
assertEquals(, list.size());
assertTrue(numbers.containsAll(list));
複制代碼
注意,Collection執行個體中的元素會填充入底層數組中。
添加元素
在ArrayList中,可以在末尾或者指定位置插入元素:
List<Long> list = new ArrayList<>();
list.add();
list.add();
list.add(, );
assertThat(Arrays.asList(, , ), equalTo(list));
複制代碼
也可以同時插入集合或者多個元素:
List<Long> list = new ArrayList<>(Arrays.asList(, , ));
LongStream.range(, ).boxed()
.collect(collectingAndThen(toCollection(ArrayList::new), ys -> list.addAll(, ys)));
assertThat(Arrays.asList(, , , , , , , , ), equalTo(list));
複制代碼
清單疊代
ArrayList可以使用兩種類型的疊代器:Iterator和ListIterator,通過第一類疊代器可以按照一個方向周遊清單,第二類疊代器可以對清單進行雙向周遊。
下面是ListIterator的使用方式:
List<Integer> list = new ArrayList<>(
IntStream.range(, ).boxed().collect(toCollection(ArrayList::new))
);
ListIterator<Integer> it = list.listIterator(list.size());
List<Integer> result = new ArrayList<>(list.size());
while (it.hasPrevious()) {
result.add(it.previous());
}
Collections.reverse(list);
assertThat(result, equalTo(list));
複制代碼
也可以使用疊代器對元素進行查詢、添加或者删除操作。
清單搜尋
接下來示範如何在集合中進行搜尋操作:
List<String> list = LongStream.range(,)
.boxed()
.map(Long::toHexString)
.collect(toCollection(ArrayList::new));
List<String> stringsToSearch = new ArrayList<>(list);
stringsToSearch.addAll(list);
複制代碼
搜尋無序數組
如果需要在清單中查找某個元素,可以使用indexOf()或者lastIndexOf()方法,這兩個方法都接受一個對象為入參,并傳回int值。
assertEquals(, stringsToSearch.indexOf("a"));
assertEquals(, stringsToSearch.lastIndexOf("a"));
複制代碼
如果你想要找到滿足條件的所有元素,可以使用Java8中的Stream API(Predicate)來實作:
Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));
List<String> result = stringsToSearch
.stream()
.filter(matchingStrings::contains)
.collect(toCollection(ArrayList::new));
assertEquals(, result.size());
複制代碼
也可以使用for循環或者疊代器來實作:
Iterator<String> it = stringsToSearch.iterator();
Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));
List<String> result = new ArrayList<>();
while (it.hasNext()) {
String s = it.next();
if (matchingStrings.contains(s)) {
result.add(s);
}
}
複制代碼
搜尋有序數組
如果數組是有序的,則使用二分搜尋會比線性搜尋更快:
List<String> copy = new ArrayList<>(stringsToSearch);
Collections.sort(copy);
int index = Collections.binarySearch(copy, "f");
assertThat(index, not(equalTo(-)));
複制代碼
如果元素不存在則會傳回-1。
删除元素
如果你要删除一個元素,你首先需要找到該元素的索引,如何通過調用
remove()
方法删除該元素。
remove()
方法的一個重載方法會接受一個對象作為參數,在清單中搜尋并删除與其相等的第一個元素:
List<Integer> list = new ArrayList<>(
IntStream.range(, ).boxed().collect(toCollection(ArrayList::new))
);
Collections.reverse(list);
list.remove();
assertThat(list.get(), equalTo());
list.remove(Integer.valueOf());
assertFalse(list.contains());
複制代碼
但是在處理Integer之類的裝箱類型時需要注意,如果要删除某個元素,你需要首先将int值進行裝箱操作,否則删除的将是該索引對應的元素。
同樣,你也可以使用前面提到的
Stream API
來删除一些元素,這裡不做展示。下面是使用疊代器的操作方法:
Set<String> matchingStrings
= HashSet<>(Arrays.asList("a", "b", "c", "d", "e", "f"));
Iterator<String> it = stringsToSearch.iterator();
while (it.hasNext()) {
if (matchingStrings.contains(it.next())) {
it.remove();
}
}
複制代碼
LinkedList
簡介
LinkedList是List和Deque接口的雙向連結清單實作,它實作了所有的清單操作,并且可以容納所有的元素(包括null)。
特性
下面是LinkedList的主要特性:
- 需要索引到連結清單内的操作将從頭部或尾部對連結清單進行周遊,從離索引位置更近的一端開始;
- 不保證線程安全的,即非synchronized;
- 其中的Iterator和ListIterator疊代器都采用了快速失敗機制(也就是說,在疊代器建立之後,如果連結清單被修改則會抛出ConcurrentModificationException 異常)。
- 其中的每一個元素就是一個節點,每個節點中儲存着指向前驅節點與後繼節點的索引。
- 保持插入順序。
盡管LinkedList是非同步的,但是可以通過調用*Collections.synchronizedList*獲得同步版本,如下所示:
List list = Collections.synchronizedList(new LinkedList(...));
複制代碼
與ArrayList的比較
雖然這兩種都是List接口的實作,但是卻有着不同的語義,而這會影響我們對資料結構的選擇。
結構
ArrayList是在Array基礎上的一種基于索引的資料結構,随機通路其元素的性能為O(1)。
LinkedList是以連結清單的形式存儲資料的,每個元素與其前後的節點綴連。在這種情況下,對一個元素的搜尋操作需要的時間複雜度為O(n)。
操作
在LinkedList中對元素的插入、添加和删除操作執行速度更快,因為不需要調整數組大小,當元素插入到集合中的任意位置時也不需要調整索引,隻有前後的元素需要修改。
記憶體使用
LinkedList相比ArrayList要消耗更多的記憶體,因為其中的每個節點都存儲兩個引用,分别指向前驅節點以及後繼節點,而ArrayList中隻儲存資料和索引。
使用
下面是一些關于如何使用LinkedList的示例代碼。
建立
LinkedList<Object> linkedList = new LinkedList<>();
複制代碼
增加元素
LinkedList實作了List和Deque接口,除了标準的*add()和addAll()方法之外,還有addFirst()和addLast()*方法,分别會在頭尾添加新元素。
删除元素
與增加元素類似,LinkedList提供了removeFirst()和removeLast()方法。同樣,也有便利的方法removeFirstOccurence()和removeLastOccurence(),它們的傳回值為boolean(如果集合中包含指定元元素,則傳回true)。
隊列操作
Deque接口提供了隊列類的操作(實際上Deque繼承了Queue接口):
linkedList.poll();
linkedList.pop();
複制代碼
這兩個方法會擷取連結清單中的第一個元素,并從連結清單中删除該元素。
poll()和pop()方法的差別在于,當操作空連結清單時,pop會抛出NoSuchElementException()異常,而poll會傳回
NULL
。pollFirst() 和pollLast() 也是可用的。
下面是push方法的示例:
linkedList.push(Object o);
複制代碼
該方法會在集合的頭部插入元素。
LinkedList 還有很多其它的方法,對于使用過Lists的使用者而言,其中大多數方法已經熟悉了。其它的方法是Deque接口提供的,是“标準”方法的便利替代方案。
總結
ArrayList通常是List接口的預設實作。
但是,在一些重要的使用場景中,LinkedList是更好的選擇,如追求常數級的插入/删除耗時,而不要求常數級通路耗時和高效的記憶體使用(例如,頻繁的插入/删除/更新)。
CopyOnWriteArrayList
簡介
*CopyOnWriteArrayList*是一個在多線程程式設計中很有用的資料結構,我們可以在無需顯式同步操作的前提下,對一個清單進行線程安全的周遊操作。
CopyOnWriteArrayList API
CopyOnWriteArrayList的設計中使用了一個有趣的技巧,不需要同步操作即具有線程安全特性。當我們使用任何會對清單結構進行修改的方法(比如
add()
或者
remove()
)時,CopyOnWriteArrayList中的所有内容将被複制到一個内部副本中。
通過這個簡單的實作,我們可以安全地對清單進行疊代,即使會有并發的修改操作。
當我們在對CopyOnWriteArrayList調用
iterator()
方法時,我們會得到一個由CopyOnWriteArrayList内容的不可變快照備份的疊代器。其中的内容是建立疊代器時ArrayList中資料的精确副本。即使在此期間,其他線程在清單中添加或删除了某個元素,該修改也會生成資料的新副本,該副本将用于對該清單進行的後續資料查找。
CopyOnWriteArrayList這種資料結構的特點使它在疊代操作多于修改時更加有用,如果在應用場景中存在頻繁的增加元素操作,那麼CopyOnWriteArrayList就不是好的選擇,因為多餘的副本會導緻性能的急劇下降。
插入時對CopyOnWriteArrayList進行疊代
首先,建立一個存儲整型數的CopyOnWriteArrayList執行個體:
CopyOnWriteArrayList<Integer> numbers = new CopyOnWriteArrayList<>(new Integer[]{, , , });
複制代碼
接下來,我們要對數組進行疊代,是以建立一個Iterator執行個體:
Iterator<Integer> iterator = numbers.iterator();
複制代碼
疊代器建立之後,我們向清單中增加一個新元素:
numbers.add();
複制代碼
注意,當我們建立CopyOnWriteArrayList的疊代器時,得到的是調用
iterator()
方法時清單中的資料的一個不可變快照。
是以,當我們對其進行疊代時,其中沒有數字10:
List<Integer> result = new LinkedList<>();
iterator.forEachRemaining(result::add);
assertThat(result).containsOnly(, , , );
複制代碼
接着使用新建立的Iterator進行疊代會發現其中包含新加入的數字10:
Iterator<Integer> iterator2 = numbers.iterator();
List<Integer> result2 = new LinkedList<>();
iterator2.forEachRemaining(result2::add);
assertThat(result2).containsOnly(, , , , );
複制代碼
不允許在疊代時進行删除
CopyOnWriteArrayList設計的目的,在于即使底層清單資料被修改,仍然允許使用者安全地對元素進行周遊。
由于疊代器的拷貝機制,對于傳回的Iterator執行
remove()
方法是不被允許的,這會導緻UnsupportedOperationException:
@Test(expected = UnsupportedOperationException.class)
public void IterateOverItAndTryToRemoveElement() {
CopyOnWriteArrayList<Integer> numbers
= new CopyOnWriteArrayList<>(new Integer[]{, , , });
Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
iterator.remove();
}
}
複制代碼
List的常用操作及實作
不可變清單
集合類在Java中是引用類型,在操作的時候可能不經意間被程式修改,類似的“失誤”經常會在程式的其它地方導緻錯誤,往往很難定位問題根源。讓ArrayList不可改變,是一個防禦性程式設計技術,可以使用以下方式實作。
JDK
首先,JDK提供了一個方法,可以根據已有的清單獲得一個不可變的集合對象:
Collections.unmodifiableList(list);
複制代碼
獲得的新集合對象将不能被修改:
@Test(expected = UnsupportedOperationException.class)
public void UnmodifiableListIsCreated() {
List<String> list = new ArrayList<String>(Arrays.asList("one", "two", "three"));
List<String> unmodifiableList = Collections.unmodifiableList(list);
unmodifiableList.add("four");
}
複制代碼
JDK1.8的Collections類中使用了一個靜态内部類UnmodifiableList對底層數組進行了封裝,當調用
get()
方法時,會傳回對應的元素,如果調用
set()
、
add()
等修改方法時,則會直接抛出異常UnsupportedOperationException。
Guava
Guava中通過ImmutableList提供了一個類似的功能:
ImmutableList.copyOf(list);
複制代碼
同樣的,得到的結果清單也是不可修改的:
@Test(expected = UnsupportedOperationException.class)
public void UnmodifiableListIsCreatedUsingGuava() {
List<String> list = new ArrayList<String>(Arrays.asList("one", "two", "three"));
List<String> unmodifiableList = ImmutableList.copyOf(list);
unmodifiableList.add("four");
}
複制代碼
注意這裡的操作實際上傳回的是原始清單的一個副本,而不隻是一個視圖。
Guava同樣提供了一個建構器,該建構器将傳回強類型的ImmutableList而不是簡單的List:
@Test(expected = UnsupportedOperationException.class)
public void UnmodifiableListIsCreatedUsingGuavaBuilder() {
List<String> list = new ArrayList<String>(Arrays.asList("one", "two", "three"));
ImmutableList<Object> unmodifiableList = ImmutableList.builder().addAll(list).build();
unmodifiableList.add("four");
}
複制代碼
Apache Commons Collections
Commons Collection也提供了一個API用于建立不可變清單:
ListUtils.unmodifiableList(list);
複制代碼
同樣,對結果清單進行修改操作會導緻UnsupportedOperationException異常:
@Test(expected = UnsupportedOperationException.class)
public void UnmodifiableListIsCreatedUsingCommonsCollections() {
List<String> list = new ArrayList<String>(Arrays.asList("one", "two", "three"));
List<String> unmodifiableList = ListUtils.unmodifiableList(list);
unmodifiableList.add("four");
}
複制代碼
劃分清單
這裡讨論的劃分是将清單拆分為多個給定大小的子清單。這樣一個相對簡單的需求,Java的标準集合架構API中居然不支援,還好Guava和Apache Commons Collections都實作了該操作。
Guava
Guava通過**
Lists.partition
**操作來完成清單的劃分:
@Test
public void ParitioningIntoNSublists() {
List<Integer> intList = Lists.newArrayList(, , , , , , , );
List<List<Integer>> subSets = Lists.partition(intList, );
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, );
assertThat(subSets.size(), equalTo());
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
Guava中也可以對其它的集合類型進行劃分:
@Test
public void ParitioningIntoNSublists() {
Collection<Integer> intCollection = Lists.newArrayList(, , , , , , , );
Iterable<List<Integer>> subSets = Iterables.partition(intCollection, );
List<Integer> firstPartition = subSets.iterator().next();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, , );
assertThat(firstPartition, equalTo(expectedLastPartition));
}
複制代碼
需要注意劃分後的子清單隻是源集合類型的視圖,對源集合的操作會影響子清單:
@Test
public void OriginalListModified() {
// Given
List<Integer> intList = Lists.newArrayList(, , , , , , , );
List<List<Integer>> subSets = Lists.partition(intList, );
// When
intList.add();
// Then
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, , );
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
Apache Commons Collections
@Test
public void ParitioningIntoNSublists() {
List<Integer> intList = Lists.newArrayList(, , , , , , , );
List<List<Integer>> subSets = ListUtils.partition(intList, );
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, );
assertThat(subSets.size(), equalTo());
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
該方法不能像Guava一樣對原生集合類進行劃分,與Guava一樣的是,該方法傳回的是源清單的一個視圖。
Java 8 API
使用
Collectors.partitioningBy()
将清單分為兩個子清單:
@Test
public void ParitioningIntoSublistsUsingPartitionBy {
List<Integer> intList = Lists.newArrayList(, , , , , , , );
Map<Boolean, List<Integer>> groups =
intList.stream().collect(Collectors.partitioningBy(s -> s > ));
List<List<Integer>> subSets = new ArrayList<List<Integer>>(groups.values());
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, );
assertThat(subSets.size(), equalTo());
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
此外,也可以使用
Collectors.groupingBy()
:
@Test
public final void ParitioningIntoNSublistsUsingGroupingBy() {
List<Integer> intList = Lists.newArrayList(, , , , , , , );
Map<Integer, List<Integer>> groups =
intList.stream().collect(Collectors.groupingBy(s -> (s - ) / ));
List<List<Integer>> subSets = new ArrayList<List<Integer>>(groups.values());
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, );
assertThat(subSets.size(), equalTo());
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
注意,這裡傳回的劃分結果不是源清單的視圖,是以源清單的改動不會影響劃分的子清單。
我們還可以使用分隔符來劃分清單:
@Test
public void SplittingBySeparator() {
List<Integer> intList = Lists.newArrayList(, , , , , , , , , );
int[] indexes =
Stream.of(IntStream.of(-), IntStream.range(, intList.size())
.filter(i -> intList.get(i) == ), IntStream.of(intList.size()))
.flatMapToInt(s -> s).toArray();
List<List<Integer>> subSets =
IntStream.range(, indexes.length - )
.mapToObj(i -> intList.subList(indexes[i] + , indexes[i + ]))
.collect(Collectors.toList());
List<Integer> lastPartition = subSets.get();
List<Integer> expectedLastPartition = Lists.<Integer> newArrayList(, );
assertThat(subSets.size(), equalTo());
assertThat(lastPartition, equalTo(expectedLastPartition));
}
複制代碼
這個例子中我們使用“0”作為分隔符,首先我們擷取所有“0”元素的索引位置,然後将清單在這些位置上進行劃分。
删除清單中所有的null
JDK
Java集合架構提供了一個簡單的方法來删除清單中的所有null元素,使用while循環:
@Test
public void RemovingNullsWithPlainJava() {
List<Integer> list = Lists.newArrayList(null, , null);
while (list.remove(null));
assertThat(list, hasSize());
}
複制代碼
也可以使用稍微簡單一些的方法:
@Test
public void RemovingNullsWithPlainJavaAlternative() {
List<Integer> list = Lists.newArrayList(null, , null);
list.removeAll(Collections.singleton(null));
assertThat(list, hasSize());
}
複制代碼
注意這兩種方式都會修改源清單。
Google Guava
我們也可以使用Guava來删除清單中的null元素,通過謂詞可以有一個更函數式的實作:
@Test
public void RemovingNullsWithGuavaV1() {
List<Integer> list = Lists.newArrayList(null, , null);
Iterables.removeIf(list, Predicates.isNull());
assertThat(list, hasSize());
}
複制代碼
此外,如果不想修改源清單,Guava中也可以建立一個新的過濾後的清單:
@Test
public void RemovingNullsWithGuavaV2() {
List<Integer> list = Lists.newArrayList(null, , null, , );
List<Integer> listWithoutNulls = Lists.newArrayList(
Iterables.filter(list, Predicates.notNull()));
assertThat(listWithoutNulls, hasSize());
}
複制代碼
Apache Commons Collections
接下來看一下使用Apache Commons Collections庫的實作方法,使用函數式風格:
@Test
public void RemovingNullsWithCommonsCollections() {
List<Integer> list = Lists.newArrayList(null, , , null, , null);
CollectionUtils.filter(list, PredicateUtils.notNullPredicate());
assertThat(list, hasSize());
}
複制代碼
注意這個方法也會修改源清單。
使用Lambda表達式(Java 8)
最後,看一下使用Lambda表達式對清單進行過濾的方法,過濾操作可以并行或者串行執行:
@Test
public void FilteringParallel() {
List<Integer> list = Lists.newArrayList(null, , , null, , null);
List<Integer> listWithoutNulls = list.parallelStream()
.filter(Objects::nonNull)
.collect(Collectors.toList());
}
@Test
public void FilteringSerial() {
List<Integer> list = Lists.newArrayList(null, , , null, , null);
List<Integer> listWithoutNulls = list.stream()
.filter(Objects::nonNull)
.collect(Collectors.toList());
}
public void RemovingNullsWithRemoveIf() {
List<Integer> listWithoutNulls = Lists.newArrayList(null, , , null, , null);
listWithoutNulls.removeIf(Objects::isNull);
assertThat(listWithoutNulls, hasSize());
}
複制代碼
删除清單中的重複項
JDK
使用标準的Java集合架構删除清單中的重複元素,可以通過Set集合完成:
public void RemovingDuplicatesWithPlainJava() {
List<Integer> listWithDuplicates = Lists.newArrayList(, , , , , );
List<Integer> listWithoutDuplicates = new ArrayList<>(
new HashSet<>(listWithDuplicates));
assertThat(listWithoutDuplicates, hasSize());
}
複制代碼
可以看出,該方法不會更改源清單中的資料。
Guava
使用Guava的方法是類似的:
public void RemovingDuplicatesWithGuava() {
List<Integer> listWithDuplicates = Lists.newArrayList(, , , , , );
List<Integer> listWithoutDuplicates = Lists.newArrayList(Sets.newHashSet(listWithDuplicates));
assertThat(listWithoutDuplicates, hasSize());
}
複制代碼
同樣,源清單的資料沒有被修改。
Lambda表達式
還有一個方法是使用Lambda表達式,我們可以使用*Stream API中的*distinct()方法,該方法會傳回一個由不同元素組成的資料流,其中通過*equals()*判斷元素是否相同。
public void RemovingDuplicatesWithJava8() {
List<Integer> listWithDuplicates = Lists.newArrayList(, , , , , );
List<Integer> listWithoutDuplicates = listWithDuplicates.stream()
.distinct()
.collect(Collectors.toList());
}
複制代碼
查找清單中的某個元素
為了友善後續說明,我們首先定義一個Customer POJO對象:
public class Customer{
private int id;
private String name;
//getter/setter 代碼省略
@Override
public boolean equals(Object obj){
if(obj == null){
return null;
}
if(this == obj){
return true;
}
if(getClass() != obj.getClass()){
return false;
}
final Customer other = (Customer)obj;
if(id == other.getId()){
return true;
}
return false;
}
@Override
public int hashCode(){
return this.id;
}
}
複制代碼
再定義一個存儲Customer對象的ArrayList:
List<Customer> customers = new ArrayList<>();
customers.add(new Customer(, "zhao"));
customers.add(new Customer(, "qian"));
customers.add(new Customer(, "sun"));
複制代碼
注意,我們在Customer類中重寫了
equals()
和
hashCode()
,在我們的實作中,具有相同id的兩個Customer對象就認為是相等的。
Java API
Java本身提供了多種方法來查找清單中的某個元素。List提供了名為***
contains()
***的方法:
boolean contains(Object element)
複制代碼
如果清單中包含某個元素,該方法會傳回true,否則傳回false。是以隻需要檢查清單中是否存在某個元素,我們可以這樣做:
Customer qian = new Customer(, "qian");
if (customers.contains(qian)) {
// ...
}
複制代碼
indexOf()
也是一個用于查找元素的方法:
int indexOf(Object element)
複制代碼
該方法會傳回給定清單中某元素第一次出現的位置索引,如果清單中不包含該元素則傳回*-1*。是以,如果該方法傳回的不是-1,就說明清單中不包含該元素:
if(customers.indexOf(qian) != -) {
// ...
}
複制代碼
這個方法否主要優點就是可以獲得元素在清單中的位置。
如果我們需要基于某個字段來搜尋清單中的元素呢?比如通過名字來指定某個使用者。對于這一類基于字段的搜尋,我們就需要使用疊代。
對清單進行周遊的最典型的方法就是使用循環,在每個疊代中,将清單中的目前元素與我們搜尋的元素進行對比,确認是否比對:
public Customer findUsingEnhancedForLoop(String name, List<Customer> customers) {
for (Customer customer : customers) {
if (customer.getName().equals(name)) {
return customer;
}
}
return null;
}
複制代碼
這裡的name對應的就是我們所搜尋的對象的名稱,該方法會傳回比對該字段的第一個Customer對象,如果沒有比對項則傳回null。
同樣可以使用Iterator來周遊清單中的項:
public Customer findUsingIterator(
String name, List<Customer> customers) {
Iterator<Customer> iterator = customers.iterator();
while (iterator.hasNext()) {
Customer customer = iterator.next();
if (customer.getName().equals(name)) {
return customer;
}
}
return null;
}
複制代碼
Stream API
要使用Stream API在給定清單中查詢比對條件的元素時,可以通過以下步驟完成:
- 在清單上執行stream()
- 調用包含特定篩選條件的*filter()*方法
- 調用findAny()方法,該方法會将**比對篩選條件的第一個元素封裝為Optional**并傳回
Customer james = customers.stream()
.filter(customer -> "zhao".equals(customer.getName()))
.findAny()
.orElse(null);
複制代碼
如果Optional為空的話,則預設傳回null。
Guava
Guava中的做法與stream操作類似:
Customer sun = Iterables.tryFind(customers,
new Predicate<Customer>() {
public boolean apply(Customer customer) {
return "sun".equals(customer.getName());
}
}).orNull();
複制代碼
如果清單或者過濾條件為空,Guava會抛出一個NullPointerException。
Apache Commons Collections
正常操作:
Customer zhang = IterableUtils.find(customers,
new Predicate<Customer>() {
public boolean evaluate(Customer customer) {
return "zhang".equals(customer.getName());
}
});
複制代碼
但是,這裡有兩點差別:
- 如果傳入清單為null,Apache Commons會傳回null。
- 該方法不像Guava中的
一樣可以設定預設值。tryFind()
清單複制
複制清單的一個簡單方法就是使用以集合為參數的構造器:
List<T> copy = new ArrayList<>(list);
複制代碼
由于該方法是複制引用而非克隆對象,是以對任何元素的修改都會影響兩個清單。是以,該方法适合于複制不可變對象:
List<Integer> copy = new ArrayList<>(list);
複制代碼
Integer是一個不可變類,在建立執行個體時會指定取值,并且對應取值不可更改。是以,整數引用可以由多個清單和線程共享,任何人都無法更改它的值。
還有一個複制元素的方案就是使用
addAll()
方法:
List<Integer> copy = new ArrayList<>();
copy.addAll(list);
複制代碼
同樣,這裡兩個清單中的元素引用了相同的對象。如果我們在複制清單的同時,另外的線程中對其進行修改,則會抛出***ConcurrentAccessException***。可以通過以下方法解決該問題:
- 使用可并發通路的集合
- 在疊代集合時對其加鎖
- 尋找一種避免複制源集合的方法
我們剛才所使用的方法就不滿足線程安全要求。如果使用第一種方式解決該問題,我們可以使用CopyOnWhiteArrayList,之前說過針對該清單的所有改動都會先建立底層資料的新副本。如果需要對集合進行加鎖,可以使用ReentrantReadWriteLock(可重入讀寫鎖)鎖原語将讀寫操作有序化。
此外,Collections類中也提供了工具方法
copy()
對集合進行複制,該方法需要傳入一個源清單和一個目标清單,且目标清單的長度至少要與源清單相等。該方法在複制元素的時候會保留元素在源清單中的索引位置。
List<Integer> source = Arrays.asList(,,);
List<Integer> dest = Arrays.asList(,,);
Collections.copy(dest, source); // [1,2,3]
複制代碼
在這個示例程式中,dest清單原來的項都會被覆寫,因為兩個清單的長度相等。如果目标清單的長度大于源清單:
List<Integer> source = Arrays.asList(, , );
List<Integer> dest = Arrays.asList(, , , , , );
Collections.copy(dest, source); // [1,2,3,8,9,10]
複制代碼
隻有前三個元素被覆寫,其它元素保留。
Java 8中的Stream API也提供了函數式的實作方法:
List<String> copy = list.stream().collect(Collectors.toList());
複制代碼
該方法的優勢在于可以同時對元素進行過濾和跳過,如跳過第一個元素:
List<String> copy = list.stream()
.skip()
.collect(Collectors.toList());
複制代碼
也可以對元素的某些字段進行過濾比較:
List<String> copy = list.stream()
.filter(s -> s.length() > )
.collect(Collectors.toList());
複制代碼
也可以通過以下方法對null值進行處理:
List<Flower> flowers = Optional.ofNullable(list)
.map(List::stream).orElseGet(Stream::empty)
.skip()
.collect(Collectors.toList());
複制代碼
向ArrayList中加入多個元素
首先,我們可以使用
addAll()
方法向一個ArrayList中增加多個元素,該方法接收一個集合作為入參:
List<Integer> anotherList = Arrays.asList(, , , , , );
list.addAll(anotherList);
複制代碼
這裡需要注意的是,添加到清單list中的新元素與anotherList中的元素将引用同樣的對象。是以,對這些元素的修改會影響兩個清單。
除此之外還可以使用集合工具類Collections,該類中隻包含對集合進行操作或者傳回值為集合的靜态方法。
addAll()
就是其中之一,該方法需要傳入目标清單,需要傳入清單的項可以單獨指定也可以以數組形式傳入。下面是示例:
List<Integer> list = new ArrayList<>();
// 單獨指定元素項
Collections.addAll(list, , , , , );
// 使用數組作為入參
Integer[] otherList = new Integer[] {, , , , };
Collections.addAll(list, otherList);
複制代碼
與上一個方法類似,兩個清單中的内容指向相同的對象。
Java 8中的Stream子產品提供了新的方法:
List<Integer> source = ...;
List<Integer> target = ...;
source.stream().forEachOrdered(target::add);
複制代碼
這種方式的主要優勢在于可以對元素進行跳過或者過濾。下面是跳過第一個元素的示例:
source.stream().skip().forEachOrdered(target::add);
複制代碼
也可以對元素進行過濾:
source.stream().filter(i -> i > ).forEachOrdered(target::add);
複制代碼
如果希望處理方法具有空安全屬性,可以使用Optional:
Optional.ofNullable(source).ifPresent(target::addAll)
複制代碼
這裡通過調用
addAll()
方法将source中的元素加入到了target中。
删除清單中等于特定值的所有元素
在Java中,從List中删除某個元素可以直接使用
List.remove()
方法,但是,想要有效地删除所有的特定值要困難一些,下面整理了一些可供使用的方式。
使用while循環
既然我們已經知道如何删除單個元素,那麼就可以在循環中重複删除該操作:
void removeAll(List<Integer> list, int element) {
while (list.contains(element)) {
list.remove(element);
}
}
複制代碼
但是,很不巧這個程式沒法完成任務:
// given
List<Integer> list = list(, , );
int valueToRemove = ;
// when
assertThatThrownBy(() -> removeAll(list, valueToRemove))
.isInstanceOf(IndexOutOfBoundsException.class);
複制代碼
問題在于代碼第三行,我們調用了**
List.remove(int)
**,但是該方法會将傳入的參數作為待删除元素的索引值,而不是我們需要删除的元素的值。
在上面的測試用例中,我們一直調用
list.remove(1)
,但是我們想要删除的元素的索引為0,而調用該方法會将被删除元素後面的所有元素都向前移動。是以,最後會删掉除第一個元素以外的所有元素,當清單中隻有一個元素時,索引1就是非法值,是以程式會抛出異常。
要注意,隻有當我們傳入原始類型(byte,short,char或int)參數時,才會遇到該問題。因為編譯器在查找比對的重載方法時首先會對參數進行原始類型擴充。
我們隻需将傳入值得類型改為Integer即可:
void removeAll(List<Integer> list, Integer element) {
while (list.contains(element)) {
list.remove(element);
}
}
複制代碼
這樣代碼就可以正确工作了:
// given
List<Integer> list = list(, , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, ));
複制代碼
由于
List.contains()
與
List.remove()
兩個方法都需要先找到元素的第一個索引值,是以該方法中存在不必要的元素周遊。如果在第一次周遊的時候将索引值儲存起來,代碼效率會更高:
void removeAll(List<Integer> list, Integer element) {
int index;
while ((index = list.indexOf(element)) >= ) {
list.remove(index);
}
}
複制代碼
雖然這個方法代碼簡潔,但是性能仍然不足:因為我們并沒有對程式過程進行跟蹤,
List.remove()
方法隻能先找到給定值的第一個索引然後再對其進行删除。
循環使用remove方法
**
List.remove(E element)
**方法還有一個特點:該方法有一個boolean類型的 傳回值,如果清單結構因為該操作發生變化,則傳回true,表明清單中包含該元素。要注意,
List.remove(int index)
方法無傳回值,因為如果傳入的索引參數有效,則清單總會删除該元素,否則就會抛出IndexOutOfBoundsException。
是以我們可以這樣來删除元素:
void removeAll(List<Integer> list, int element) {
while (list.remove(element));
}
複制代碼
該方法也可以正常工作:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, ));
複制代碼
盡管代碼更簡潔,但是仍然存在前面所說的性能問題。
使用for循環
如果使用for循環,我們就可以跟蹤清單周遊的位置,如果周遊元素是待删除元素則可以直接删除:
void removeAll(List<Integer> list, int element) {
for (int i = ; i < list.size(); i++) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
}
}
}
複制代碼
看起來是可以完成任務的:
// given
List<Integer> list = list(, , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, ));
複制代碼
但是,如果我們換一個不同的輸入清單,結果就是錯誤的:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, , ));
複制代碼
我們來一步步分析一下代碼的工作過程:
- i = 0
- 第3行中element與list.get(i)值都為1,是以Java進入if代碼塊
- 删除索引0的元素
- 清單中的值變為[1,2,3]
- i = 1
- *list.get(i)*傳回2,因為在清單中删除一個元素之後,它後面的元素會依次前移
是以如果輸入清單中有兩個連續的元素都是待删除的元素,就會引發該問題。要解決這個問題,我們就需要在删除元素時保持循環變量。
如當删除元素時,将循環變量減一:
void removeAll(List<Integer> list, int element) {
for (int i = ; i < list.size(); i++) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
i--;
}
}
}
複制代碼
或者是,僅在不删除元素時對循環變量加一:
void removeAll(List<Integer> list, int element) {
for (int i = ; i < list.size();) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
} else {
i++;
}
}
}
複制代碼
這裡第二種方法的for條件中去掉了i++。
這兩種方法都是有效的,而且這個實作乍一看應該是完全正确的,但是仍然存在一些性能問題:
- 從ArrayList中删除元素,會移動該元素後面的所有元素
- 在LinkedList中通過索引通路元素,意味着需要從表頭周遊至索引位置。
使用for-each循環
Java 5開始可以使用for-each循環對清單進行周遊,我們不妨使用它來删除元素:
void removeAll(List<Integer> list, int element) {
for (Integer number : list) {
if (Objects.equals(number, element)) {
list.remove(number);
}
}
}
複制代碼
我們在這裡使用了Integer作為循環變量類型,是以避免了空指針異常。同時,我們調用的是
List.remove(E element)
方法,傳入參數為我們要删除的值而不是元素的索引。但是很不幸,這個方法是錯誤的:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
.isInstanceOf(ConcurrentModificationException.class);
複制代碼
因為for-each循環本質上是使用Iterator對元素進行周遊,但是當我們修改清單時,Iterator會進入一個不穩定狀态,進而抛出ConcurrentModificationException異常。
我們學到了一點:當通過for-each循環通路清單元素時,不要對清單進行修改。
使用Iterator
我們可以直接使用Iterator直接對清單進行周遊及修改:
void removeAll(List<Integer> list, int element) {
for (Iterator<Integer> i = list.iterator(); i.hasNext();) {
Integer number = i.next();
if (Objects.equals(number, element)) {
i.remove();
}
}
}
複制代碼
在上面的代碼中,Iterator會對清單狀态進行跟蹤,因為清單的修改是由疊代器完成的。是以代碼可以實作要求:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, ));
複制代碼
因為每一個List類都會提供自己的疊代器實作,我們可以認為,疊代器會以最有效的方式實作元素疊代。但是,在ArrayList時仍然會存在大量的元素移動。
收集元素
截至目前,我們都是通過删除不需要的元素來修改清單結構。其實我們也可以新建立一個新清單,将需要保留的元素納入其中:
List<Integer> removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}
return remainingElements;
}
複制代碼
這裡方法的傳回值變為了List對象,是以調用方式也需要做一些調整:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
List<Integer> result = removeAll(list, valueToRemove);
// then
assertThat(result).isEqualTo(list(, ));
複制代碼
這個方法中可以使用for-each循環的原因在于,我們并沒有對目前正在疊代的清單進行修改操作。同時,由于沒有删除操作,也就不需要對元素進行移動,是以該方法在使用ArrayList的時候效率較高。
這個實作方法與之前的相比,主要有兩點不同:
- 沒有對源清單進行修改,而是傳回了一個新的清單對象
- 方法的實作決定了最終傳回的List的具體實作,可能會與源清單不同
當然,我們也可以做一些調整,跟前面的方法保持一緻。也就是說,将源清單元素清除,再将保留的元素填入其中:
void removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}
list.clear();
list.addAll(remainingElements);
}
複制代碼
這裡我們不對源清單進行修改,也無需通過索引通路元素及移動元素,隻有兩個地方可能涉及數組的再配置設定:調用
List.clear()
和
List.addAll()
方法時。
使用Stream API
Java 8中引入的lambda表達式以及stream API,可以通過非常簡潔的代碼解決該問題:
List<Integer> removeAll(List<Integer> list, int element) {
return list.stream()
.filter(e -> !Objects.equals(e, element))
.collect(Collectors.toList());
}
複制代碼
有了lambda表達式及函數式接口之後,Java 8中也引入了一下擴充API。List中的
removeIf()
方法,就可以實作我們所讨論的功能。
該方法需要傳入一個謂詞函數,該函數對于需要删除的元素傳回true。這個地方與之前有所差別,前面的判斷都是對于需要保留的元素傳回true:
void removeAll(List<Integer> list, int element) {
list.removeIf(n -> Objects.equals(n, element));
}
複制代碼
測試看出,該方法是有效的:
// given
List<Integer> list = list(, , , );
int valueToRemove = ;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(, ));
複制代碼
該方案中的代碼是最為簡潔地,同時由于其中使用的方法
removeIf()
是由List本身實作的,我們可以放心地認為其性能是最優的。