ArrayList，與LinkedList都是屬于實作了List介面的類，首先從名字前綴開始看 ，Array表示陣列，Link表示鏈表，
所以ArrayList底層是基于動態陣列的，而LinkedList底層是基于雙向鏈表的，
ArrayList必須是連續記憶體的，而LinkedList不要求連續記憶體，
ArrayList查詢快，增加和洗掉慢；LinkedList增加和洗掉快，查詢慢，
ArrayList 底層為動態陣列，所以查詢時是直接通過訪問下標，查詢效率高，而增加而洗掉時，為了保證記憶體的連續，增加和洗掉某一位置后，后方元素都得向前移動一位，
最壞情況就是洗掉第一個元素，則后面第2個到第n個元素都得往前移動一位，所以增加洗掉慢，
LinkedList底層為雙向鏈表，不必保證記憶體上的連續，所以增刪快，而查詢時必須要經歷從頭到尾的遍歷，所以查詢慢，
為什么說ArrayList是基于動態陣列呢？一般的陣列，容量確定了就不可以再更改，也無法超過，但是ArrayList可以，
例如當陣列元素數已滿時呼叫了add方法向尾部添加一個元素，則此時會進行擴容，ArrayList會自動創建一個更大的陣列，并將所有元素拷貝到新陣列中，而原陣列會被拋棄，
會被GC回收，擴容后新陣列的容量為原來的1.5倍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136671.html
標籤：其他
上一篇：2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest- H. Rikka with A Long Colour Palette -思維+貪心