????先摘選一段

@Test
public?void?test_LinkedList()?{
?//?初始化100萬數據
????List?list?=?new?LinkedList(1000000);//?遍歷求和int?sum?=?0;for?(int?i?=?0;?i?????????sum?+=?list.get(i);
????}
}

---

• 乍一看可能覺得沒什么問題，但是這個遍歷求和會非常慢。主要因為鏈表的數據結構，每一次list.get(i)都是從鏈表的頭開始查找，與ArrayList不同，LinkedList它時間復雜度是O(n)。那如果說你不知道對方傳過來的是LinkedList還是ArrayList呢，其實可以通過list instanceof RandomAccess?進行判斷。ArrayList?有隨機訪問的實現，LinkedList?是沒有。同時也可以使用增強的for循環或者Iterator進行遍歷。(以上片段來自小傅哥的 握草，你竟然在代碼里下毒！，地址：https://mp.weixin.qq.com/s/q9goqjke-hTsx0_QSH_U1w)

看到這個感覺對linkedList的知識點有點模糊了，有必要簡單復習一下。結構上：LinkedList 底層數據結構是一個雙向鏈表，整體結構如下圖所示：

鏈表每個節點我們叫做 Node，Node 有 prev 屬性，代表前一個節點的位置，next 屬性，代表后一個節點的位置；

first 是雙向鏈表的頭節點，它的前一個節點是 null。?

last 是雙向鏈表的尾節點，它的后一個節點是 null；當鏈表中沒有數據時，first 和 last 是同一個節點，前后指向都是 null；?

因為是個雙向鏈表，只要機器內存足夠強大，是沒有大小限制的。

????????因為是鏈表這種結構，所以添加刪除比較容易，只要在頭尾節點進行刪除就行，

而對于ArrayList這種數組結構，還需要判斷進行擴容。

回到上面的問題，為啥get會慢。看源碼就知道了。

public E get(int index) { checkElementIndex(index); return node(index).item; } Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Nodex = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Nodex = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

都是截半然后進行for循環查找的。

總結

以上是生活随笔為你收集整理的增强型的for循环linkedlist_LinkedList的复习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。