聯系與區別：
- ArrayList：底層使用陣列來存盤元素(動態型別的順序表)，查詢快，增刪慢，執行緒不安全
LinkedList：底層使用雙向鏈表結構存盤管理元素(雙向鏈表)，查詢慢，增刪快，執行緒不安全 - LinkedList 不支持高效的隨機元素訪問
- ArrayList 的空間浪費主要體現在在 list 的結尾預留一定的空間容量，
LinkedList 的空間花費則體現在它的每一個元素都需要消耗相當的空間 - ArrayList 和 LinkedList，其在末尾增加一個元素所花的開銷都是固定的
- 兩者均實作了 List 介面
時間復雜度分析：
ArrayList
1.add(E e) — O(1)
直接在后邊添加元素
2.add(int index， E e) — O(N)
添加元素，在第 index 個元素后面插入，后面的元素需要向后移動
3.get(int index) — O(1)
直接讀取第 index 下標的元素
4.remove(int index) — O(N)
洗掉指定位置的元素
LinkedList
1.add(E e) — O(1)
直接在串列末尾追加元素
2.add(int index， E e) — O(N)
在此串列中的指定位置插入指定的元素，需要先找到指定位置
3.get(int index) — O(N)
回傳此鏈表中指定位置的元素，需依次遍歷
4.remove( ) — O(1)
檢索并洗掉此鏈表的頭
補充
若 ArrayList 無限添加元素，會拋例外嘛？
每個 ArrayList 實體都有一個容量，該容量是指用來存盤串列元素的陣列的大小，它總是至少等于串列的大小
用無參構造方法時系統會默認提供默認引數10，隨著向 ArrayList 中不斷添加元素，其容量也自動增長，自動增長會帶來資料向新陣列的重新拷貝，因此，如果可預知資料量的多少，可在構造ArrayList時指定其容量
ArrayList擴容時，正常情況下會擴容1.5倍 (newCapacity = oldCapacity + (oldCapacity >> 1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/321233.html
標籤：其他