java 集合類之List（二）

引言

昨天介紹了java集合類框架，接下來會詳細聊一下各個集合類的適用場景和需要注意的地方。今天主要介紹一下List,如有錯誤之處，還望指正。

List

List 是java集合中最簡單，也是最常用的一種集合。List存儲的是一種有序、不重複的數據。比如產品列表、商品列表等等。ArrayList和LinkedList是比較常用的List集合類。今天主要是聊一聊這兩種List的具體實現以及適用場景。

ArrayList

ArrayList常用增刪改查操作如下:

ArrayList的底層實現是一個數組，默認的構造函數new ArrayList<>(),數組的容量為10。當調用add()或者add（index,value）方法的時候。首先要判斷數組的是否超過容量，不然需要擴容長度。擴容的邏輯是在原有的長度上，增加1/2，也即原來如果是10的話，第一次擴容的長度是15，用Arrays.copyOf()方法複製一個新的容量為新長度數組出來，複製給原先的數組。如果擴充的長度超過Integer.MAX_VALUE時會報OutOfMemoryError。

增：ArrayList有兩種增加元素的方法，在數組的末尾直接添加元素即add(element)。還有一種方式是在指定的index上添加元素，此時如果該index上有元素，當前元素和後續元素都需後移，時間複雜度為O(N)。

刪：ArrayList有兩種刪除元素的方法，按元素值刪除和按index刪除。按值刪除，首先需要找到元素值得位置，這裡要注意的是，自定義對象要實現equals方法，因為決定元素值是否相等取決於equals的返回值。找到位置後，該位置後續的所有元素都要前移，時間複雜度為O(n)。按index刪除,根據index找到位置，該位置後面所有的元素前移，時間複雜度為O(n)。

改：ArrayList的修改操作比較簡單，直接在數組的index，把新的值賦值給所在的index即可,時間複雜度為O(1)。

查：直接根據index，找到位置取出值即可。

結論：

1、ArrayList適合創建前能預估容量大小的場景

2、ArrayList適合於查詢和更改比較多的場景，不適合刪除比較多的場景

3、在使用按值刪除操作時，需實現equals方法。個人建議，自定義對象默認都要實現equals和hashCode方法，不然容易掉坑裡面。

LinkedList

LinkedList常用的增刪改查操作如下：

可以看到的是和ArrayList調用的方法是一樣的。但是實現原理是不一樣的。LinkedList的實現原理是一個鏈表。

增：LinkedList同樣有兩種增加元素的方法，在鏈表尾部增加元素和指定index增加元素，在尾部增加元素，直接在last節點增加節點，重新複製last即可，時間複雜度為O(1).指定index增加元素，相比ArrayList多了個尋找index的操作，但是不需要移動元素，只需更改結點之間的指向關係就可以，時間複雜度為O(n)（不是通常認為的O(1)，好多人認為是O(1)。

刪：LinkedList同樣兩種刪除元素的方法，按元素值刪除和按index刪除。

按值刪除，與ArrayList類似，不同的是元素不需要移動，時間複雜度為O(n)。按index刪除,根據index找到元素後,也不需要移動元素，時間複雜度為O(n)。

改：根據index找到位置後，更新值。這個比較簡答，沒什麼可說的，時間複雜度也是O(1)。

查: LinkedList的查詢相對於ArrayList複雜度就比較高，LinkedList需要移動指針找到查詢的元素，時間複雜度為O(1)。

結論：

1、LinkedList不需要連續的內存，分散的內存空間也可以。ArrayList是必須要連續的存儲空間的。此外LinkedList沒有擴容這麼一說。

2、LinkedList增加和刪除沒有涉及元素的移動，相對ArrayList是比較合適的，但是不適合查詢。

此外，LinkedList不僅僅用做List，還被經常用作隊列和棧。隊列是一種先進先出FIFO的數據結構。棧是一種先進後出FILO的數據結構。這兩種數據結構是計算機中使用比較頻繁的數據結構，後續有空再詳細介紹

如果覺得文章還不錯，歡迎關注、轉發、評論。