主要差別:
- 首先他們的底層資料結構不同,ArrayList底層是基于數組實作的,LinkedList底層是基于連結清單實作的。
- 由于底層的資料結構不同,造成了他們所适用的場景也不同,ArrayList更适合随機查找,而LinkedList更适合删除和添加,同時查詢、添加、删除的時間複雜度也不同。
- 另外ArrayList和LinkedList都實作了List接口,但是LinkedList還實作了Deque接口,是以LinkedList還可以當作隊列來使用。
查詢:
ArrayList由于底層是數組,那麼在擷取其中某個元素的時候能直接擷取。
LinkedList底層是由連結清單實作的,那麼在擷取LinkedList中非首尾元素時速度要更慢,需要通過周遊才行,在LinkedList源碼中也是這樣實作。
get方法中具體實作:
get方法中具體實作:
同時又因為LinkedList底層為連結清單的原因,通過getFirst()方法擷取第一個元素和getLast()方法擷取最後一個元素時速度還是很快的。
- 添加:
ArrayList在數組最後添加一個元素操作時直接把元素添加到最後的位置上同時進行擴容,在中間某個下标添加元素時,由于該下标已經由元素了就需要給添加的元素騰出一個位置,是以後面的元素就需要整體往後移,然後再把添加的元素插入到該下标中。
LinkedList在最後添加一個元素操作時直接在連結清單最後添加一個元素,不涉及到擴容。在中間添加元素時需要先周遊連結清單找到這個下标,然後再插入過程中不涉及元素的移動操作,這裡的快慢取決于下标的大小。
兩者添加的性能沒法進行比較需要看具體的使用場景。
- 删除
ArrayList删除就和插入剛好相反,删除其中某個下标的元素删除後該下标之後的元素整體往前移,LinkedList 删除操作時先周遊找出該下标再進行删除。
作者:騎電動車的小黃
連結:https://juejin.cn/post/7017697104311091237
來源:稀土掘金
著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。主要差別:
- 首先他們的底層資料結構不同,ArrayList底層是基于數組實作的,LinkedList底層是基于連結清單實作的。
- 由于底層的資料結構不同,造成了他們所适用的場景也不同,ArrayList更适合随機查找,而LinkedList更适合删除和添加,同時查詢、添加、删除的時間複雜度也不同。
- 另外ArrayList和LinkedList都實作了List接口,但是LinkedList還實作了Deque接口,是以LinkedList還可以當作隊列來使用。
查詢:
ArrayList由于底層是數組,那麼在擷取其中某個元素的時候能直接擷取。
LinkedList底層是由連結清單實作的,那麼在擷取LinkedList中非首尾元素時速度要更慢,需要通過周遊才行,在LinkedList源碼中也是這樣實作。
get方法中具體實作:
get方法中具體實作:
同時又因為LinkedList底層為連結清單的原因,通過getFirst()方法擷取第一個元素和getLast()方法擷取最後一個元素時速度還是很快的。
- 添加:
ArrayList在數組最後添加一個元素操作時直接把元素添加到最後的位置上同時進行擴容,在中間某個下标添加元素時,由于該下标已經由元素了就需要給添加的元素騰出一個位置,是以後面的元素就需要整體往後移,然後再把添加的元素插入到該下标中。
LinkedList在最後添加一個元素操作時直接在連結清單最後添加一個元素,不涉及到擴容。在中間添加元素時需要先周遊連結清單找到這個下标,然後再插入過程中不涉及元素的移動操作,這裡的快慢取決于下标的大小。
兩者添加的性能沒法進行比較需要看具體的使用場景。
- 删除
ArrayList删除就和插入剛好相反,删除其中某個下标的元素删除後該下标之後的元素整體往前移,LinkedList 删除操作時先周遊找出該下标再進行删除。