Java面試之Java List集合

Java集合架構

Java集合類存放于Java.util包中，主要有3種：List(清單包含Queue)、Set(集)、Map(映射)

List是有序的Collection。是線性資料結構的主要表現，存儲的元素是有序的，可重複的。

一共三個實作類: 分别是ArrayList、Vector和LinkedList。

ArrayList底層使用數組實作，元素存儲有序可重複，線程不安全，查詢快增删慢，支援快速随機通路，擴容1.5倍。

ArrayList的自動擴容機制

ArrayList是一個數組結構的存儲容器，預設情況下，數組的長度是10，當然我們可以在建構ArrayList對象的時候自己指定初始化長度。随着在程式裡面不斷的往ArrayList中添加資料，當添加的資料達到10個的時候，ArrayList就沒有多餘的容量可以存儲後續的資料。

這個時候ArrayList就會自動觸發擴容。擴容的具體流程很簡單：

首先，建立一個新的數組，這個數組的長度是原來數組長度的1.5倍。

然後使用Arrays.copyOf方法把老數組裡面的資料拷貝到新的數組裡面。

擴容完成後再把目前要添加的元素加入到新的數組裡面，進而完成動态擴容的過程。

LinkedList底層使用雙向連結清單實作，元素存儲排序有序可重複，線程不安全，查詢慢增删快，不支援随機通路。

Vector1.0就存在，1.2出現在集合架構中。和ArrayList一樣也是數組結構，是線程安全的，是以運作效率慢，每次擴容100%。

ArrayList與LinkedList差別

1.資料結構

ArrayList是基于動态數組實作的，它内部維護一個可變長度的數組，當元素數量增加時，會根據需要自動擴容。

LinkedList則是基于連結清單實作的，它内部維護一個雙向連結清單。

2.通路效率

ArrayList是基于數組實作的，是以它能夠随機通路集合中的元素，時間複雜度為O(1)，但在插入和删除元素時，需要将後續的元素向前或向後移動，時間複雜度為O(n)。

LinkedList則是基于連結清單實作的，是以在通路元素時需要從頭或尾開始周遊連結清單，時間複雜度為O(n)，但在插入和删除元素時，由于隻需要修改前後節點的引用，時間複雜度為O(1)。

3.空間占用

ArrayList需要維護一個動态數組，是以在一定程度上比LinkedList占用更多的空間。

但在實際應用中，ArrayList更常用，因為它能夠提供更快的随機通路和更好的緩存性能。

4.線程安全

ArrayList和LinkedList都不是線程安全的，如果需要在多線程環境中使用，需要使用線程安全的集合類或者在通路時進行同步控制。

ArrayList與Vector差別

1.線程安全性

Vector是線程安全的，而ArrayList是非線程安全的。是以，在多線程的情況下，ArrayList的性能更好，而Vector的線程安全性可能會導緻性能損失。

2.擴容機制

ArrayList和Vector在擴容時都會增加容量大小，不同之處在于，ArrayList擴容時會增加原始容量的一半，而Vector擴容時會将容量翻倍。是以，ArrayList相對于Vector更加靈活，可以更快地适應容量變化。

3.資料增删效率

ArrayList和Vector在資料增删時的效率也有所不同。由于Vector是線程安全的，在進行資料操作時需要進行同步，這會導緻效率降低。而ArrayList不需要同步，是以資料操作效率更高。

4.性能

由于ArrayList不是線程安全的，是以其性能要比Vector高。

Iterator和ListIterator都是Java集合架構中的疊代器，用于周遊集合中的元素。Iterator可以周遊所有Collection接口的實作類，如List、Set等。但是隻能單向周遊，即隻能從前向後周遊，不能向後回退。Iterator提供的方法有：

hasNext()：判斷是否還有下一個元素。

next()：傳回下一個元素。

remove()：移除上一個元素(如果未調用next()方法則沒有元素可删，如果連續調用兩次remove()方法也會報錯)。

ListIterator隻能周遊List接口的實作類，而且是雙向周遊。即可以從前向後周遊，也可以從後向前周遊。ListIterator提供的方法有：

hasNext()：判斷是否還有下一個元素。

next()：傳回下一個元素。

hasPrevious()：判斷是否還有上一個元素。

previous()：傳回上一個元素。

remove()：移除上一個元素（如果未調用next()或previous()方法則沒有元素可删，如果連續調用兩次remove()方法也會報錯）。

add(E e)：在目前元素位置後添加一個元素。

set(E e)：修改目前元素。