每日一考-9.11

ArrayList和LinkedList區別 3

簡說
arraylist

1. 基於數組，需要連續記憶體
2. 隨機訪問快（指根據下標訪問）
3. 尾部插入、刪除性能可以，其它部分插入、刪除都會移動數據，因此性能會低
4. 可以利用 cpu 緩存，局部性原理

linkedlist

1. 基於雙向鏈表，無需連續記憶體
2. 隨機訪問慢（要沿著鏈表遍歷）
3. 頭尾插入刪除性能高
4. 占用記憶體多

細說
由於arraylist底層是數組，所以元素必須連續存儲，當要進行隨機查找，其實是根據arraylist連續存儲中的下標查找，這操作速度很快。

由於linkedlist底層是雙向鏈表，所以存儲是無序的，占用記憶體多（大約同樣存儲量，占用記憶體是arraylist的4倍左右），進行隨機查找時，得一個一個查，所以訪問效率低很多。

且arraylist底層實現了一個RandomAccess（隨機訪問介面），而linkedlist沒有實現，實現這個介面就可以通過下標去找，沒有實現就只有通過迭代器找

list集合去重都有哪些方法 3

1. 雙重for迴圈

2. 利用list集合中contains方法迴圈遍歷，清空，重新添加

3. 利用HashSet不能重覆特性，但不能保證順序，只有額外加判斷條件保證順序

4. 利用Java8特性stream流進行list去重

5. （最佳）使用LinkedHashSet刪除ArrayList中的重覆元素

   可以做到即刪除了重覆數據，又保持添加到其中的數據的順序。

數組和鏈表分別適用於什麼場景，為什麼 3

數組：數組是將元素在記憶體中連續存儲的；它的優點：因為數據是連續存儲的，記憶體地址連續，所以在查找數據的時候效率比較高；它的缺點：在存儲之前，我們需要申請一塊連續的記憶體空間，並且在編譯的時候就必須確定好它的空間的大小。在運行的時候空間的大小是無法隨著你的需要進行增加和減少而改變的，當數據兩比較大的時候，有可能會出現越界的情況，數據比較小的時候，又有可能會浪費掉記憶體空間。在改變數據個數時，增加、插入、刪除數據效率比較低。

鏈表：鏈表是動態申請記憶體空間，不需要像數組需要提前申請好記憶體的大小，鏈表只需在用的時候申請就可以，根據需要來動態申請或者刪除記憶體空間，對於數據增加和刪除以及插入比數組靈活。還有就是鏈表中數據在記憶體中可以在任意的位置，通過應用來關聯數據（就是通過存在元素的指針來聯繫）。

其實這兩者最典型的實現就是arraylist和linkedlist

數組應用場景：數據比較少；經常做的運算是按序號訪問數據元素；數組更容易實現，任何高級語言都支持；構建的線性表較穩定。

鏈表應用場景：對線性表的長度或者規模難以估計；頻繁做插入刪除操作；構建動態性比較強的線性表。