文章目錄
- 前言
- 一、LinkedList
- 二、ArrayList與LinkedList異同
-
- 2.1 資料結構
- 2.2 增删改查
- 2.3 使用場景
- 總結
前言
LinkedList(Queue與List的實作類)底層資料結構是Node節點(data資料+next下一個節點的引用)本質是雙向連結清單。
一、LinkedList
雙向連結清單構成的集合，可用疊代器周遊
a.底層資料結構:
鍊式結構
b.底層實作:
Node節點(data[資料] + next[下一個節點的引用])
c.特點:
LinkedList是雙向連結清單
①.連結清單是記憶體中固定順序,但是他的實體空間不連續（随機存放）
②.沒有下标
③.所有節點的通路,都必須通過頭節點(next)/尾節點(pre)
④.head(頭節點): 隻存next,不存data
last(尾節點): 隻存pre,不存data
⑤.head.next = null -> 空連結清單
last.pre = null -> 空連結清單
d.優缺點:
優點:
a.插入/删除效率高
b.不需要連續的記憶體實體空間,是以空間使用率高
缺點:
查詢效率低,隻能從頭節點出發開始查詢
e.LinkedList獨有的API:
(隻要帶有First/last的方法)
void addFirst(E e)
void addLast(E e)
E getFirst()
E getLast()
E remove(int index)
E removeFirst()
E removeLast()
構造方法：
常用方法:
二、ArrayList與LinkedList異同
2.1 資料結構
ArrayList是基于數組實作的，LinkedList是基于雙連結清單實作的。另外LinkedList類不僅是List接口的實作類，可以根據索引來随機通路集合中的元素，除此之外，LinkedList還實作Deque 接口，Deque接口是Queue接口的子接口，它代表一個雙向隊列，是以LinkedList可以作為雙向隊列 ，棧（可以參見Deque提供的接口方法）和List集合使用，功能強大。ArrayList長度固定，每次以1.5倍進行擴容（然後Arrays.copyOf()去淺克隆），LinkedList連結清單長度可變。
2.2 增删改查
ArrayList -> 增删慢,查詢快
LinkedList -> 增删快,查詢慢
2.3 使用場景
使用場景：
(1）如果應用程式對資料有較多的随機通路，ArrayList對象要優于LinkedList對象；
(2) 如果應用程式有更多的插入或者删除操作，較少的随機通路，LinkedList對象要優于ArrayList對象；
(3）不過ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那麼ArrayList隻需要移動較少的資料，而LinkedList則需要一直查找到清單尾部，反而耗費較多時間，這時ArrayList就比LinkedList要快。
總結：在使用List集合時,會選擇ArrayList,在綜所有條件之後,ArrayList插入和查詢的效率高于LinkedList.
總結
提示：LinkedList與ArrayList相同部分也就繼承Collection擁有Collection的特點。