歡迎光臨
每天分享高質量文章

用 ArrayList 還是 LinkedList?

(給ImportNew加星標,提高Java技能)

 

來自:唐尤華

https://dzone.com/articles/arraylist-or-linkedlist

 

本文旨在為 Java 開發這擇合適的順序資料結構提供指導。

 

Arraylist 和 LinkedList 是 Java 集合框架中用來儲存物件取用串列的兩個類。Arraylist 和 LinkedList 都實現 List 接口。首先,讓我們瞭解一下它們最重要的父接口——List。

 

1. List 接口

 

串列(list)是元素的有序集合,也稱為序列。它提供了基於元素位置的操作,有助於快速訪問、添加和刪除串列中特定索引位置的元素。List 接口實現了 Collection 和 Iterable 作為父接口。它允許儲存重覆值和空值,支持通過索引訪問元素。

 

2. 用法

 

下麵是使用 List 接口宣告 ArrayList 和 LinkedList 的代碼片段。

 

 

import java.util.*;
public class MyClass {
  // 非同步或非執行緒安全
  List arrayList = new ArrayList<>(); // 宣告一個 array list
  List linkedList = new LinkedList(); // 宣告 linked list   
  // 確保執行緒安全
  List tsArrayList = Collections.synchronizedList(new LinkedList<>());
  List tsLinkedList = Collections.synchronizedList(new LinkedList<>());   
}

 

Vector 與 ArrayList 類似,只是它們支持自動同步,這也使得 Vector 執行緒安全,但同時會帶來一些性能損耗。

 

3. 內部實現

 

3.1 LinkedList 內部實現

 

Linkedlist 資料結構包含一組有序的資料元素,稱為節點。每個元素都包含對其後續元素,即下一個元素的鏈接或取用。 序列的最後一個元素(尾部)指向空元素。鏈表本身包含對鏈表第一個元素的取用,該元素稱為 head 元素。Java 中的 LinkedList 是 List 接口的雙向鏈表。在雙向鏈表中,每個節點都指向它的上一個節點和下一個節點。此外,它還實現了其他接口,比如 Serializable、 Cloneable 和 Deque(實現 Queue 作為父接口)。

 

3.2 ArrayList 內部實現

 

Arraylist 是可調整大小的陣列,實現了 List 接口。 它的內部是一個物件陣列,可以根據需要擴容支持在集合中加入更多元素。可以通過建構式 ArrayList(int initialCapacity)指定 ArrayList 的初始容量,然後在必要時使用 void ensureCapacity(int minCapacity) 增加容量,確保至少可以容納初始化時最小容量引數指定數量的元素。

 

它還提供一個方法 void trimToSize(),可以減少現有元素的大小。

 

 

// 呼叫建構式 ArrayList(initialCapacity)
List arr = new ArrayList(10);

 

預設情況下,ArrayList 創建初始容量為10的串列,而 LinkedList 只構造一個沒有設置任何初始容量的空串列。 Linkedlist 不實現 RandomAccess 接口,而 ArrayList 實現了 RandomAccess 接口(而非 Deque 接口)。

 

4. 各種操作的時空複雜性

 

 

5. 小貼士

 

考慮下麵遍歷 LinkedList 的示例代碼。在這段代碼中遍歷會非常慢,因為 LinkedList 不支持隨機訪問,因此每次遍歷都會帶來巨大的開銷。

LinkedList ll = new LinkedList();
…
…
Object o = null;   
for (int i = 0; i < list.size(); i++)
{       
  o = list.get(i);
  …
}

 

一個更好的方法可提高性能,像下麵這段代碼。

LinkedList ll = new LinkedList(); 
… 
…   
Object o = null;    
ListIterator li = list.listIterator(0);   
while (li.hasNext()){
  o = ll.next();
  …    
}

 

6. 總結

 

相比較而言 Arraylist 更快而且更好,因為它支持對其元素的隨機訪問。 遍歷鏈表或在中間插入新元素開銷很大,因為必須遍歷每個元素而且很可能遇到快取失敗。 如果需要在一次迭代中對串列中的多個專案執行處理,那麼 LinkedList 的開銷比 Arraylist 使用時多次複製陣列元素的開銷要小。

 

歡迎分享你對這個話題的經驗與見解,請在文章的評論區中提出你的想法。

看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

喜歡就點「好看」唄~

 

    赞(0)

    分享創造快樂