ArrayList 和 LinkedList 區別 - 五六柒的個人空間 - 詳情 - ci,java,System,Python,後端開發 mob64ca140caeb2 博客

1. 引言：兩種不同的數據結構

ArrayList和LinkedList雖然都實現了List接口，但底層採用了完全不同的數據結構：

ArrayList：基於動態數組實現，支持隨機訪問
LinkedList：基於雙向鏈表實現，擅長頻繁的插入刪除操作

讓我們通過源碼來深入理解它們的設計理念和性能特點。

2. ArrayList源碼深度解析

2.1 底層數據結構

```java // ArrayList的底層數組 transient Object[] elementData;

// 默認初始容量 private static final int DEFAULT_CAPACITY = 10;

// 空數組實例，用於空實例的共享 private static final Object[] EMPTY_ELEMENTDATA = {};

// 默認大小的空數組實例 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; ```

ArrayList使用Object數組來存儲元素，這種連續內存分配的特性帶來了高效的隨機訪問能力。

2.2 動態擴容機制

ArrayList最核心的特性就是動態擴容，讓我們看看add方法的實現：

```java public boolean add(E e) { ensureCapacityInternal(size + 1); // 確保容量足夠 elementData[size++] = e; // 在末尾添加元素 return true; }

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }

private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); // 需要擴容 }

private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍擴容 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); // 數組拷貝 } ```

擴容性能分析： - 平均時間複雜度：O(1)（分攤分析） - 最壞情況：O(n)（需要拷貝整個數組） - 空間浪費：通常會有25%-50%的空間浪費

2.3 隨機訪問性能

```java // 高效的隨機訪問 public E get(int index) { rangeCheck(index); // 檢查索引範圍 return elementData(index); // 直接數組訪問 O(1) }

E elementData(int index) { return (E) elementData[index]; // 直接內存訪問 } ```

ArrayList的get操作是常數時間O(1)，這是數組結構的天然優勢。

3. LinkedList源碼深度解析

3.1 節點結構設計

LinkedList基於雙向鏈表實現，每個節點包含前驅、後繼引用和數據：

```java private static class Node { E item; // 存儲的數據 Node next; // 後繼節點 Node prev; // 前驅節點

Node(Node prev, E element, Node next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
}

} ```

3.2 添加操作實現

```java // 在鏈表末尾添加元素 public boolean add(E e) { linkLast(e); return true; }

void linkLast(E e) { final Node l = last; // 當前尾節點 final Node newNode = new Node<>(l, e, null); // 創建新節點 last = newNode; // 更新尾指針 if (l == null) // 空鏈表情況 first = newNode; else l.next = newNode; // 連接新節點 size++; modCount++; }

// 在指定位置插入元素 public void add(int index, E element) { checkPositionIndex(index);

if (index == size)               // 在末尾插入
    linkLast(element);
else
    linkBefore(element, node(index));  // 在中間插入

}

void linkBefore(E e, Node succ) { final Node pred = succ.prev; // 前驅節點 final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; // 更新後繼的前驅指針 if (pred == null) // 插入到頭部 first = newNode; else pred.next = newNode; // 更新前驅的後繼指針 size++; modCount++; } ```

3.3 查找操作性能問題

```java // 按索引查找需要遍歷鏈表 public E get(int index) { checkElementIndex(index); return node(index).item; }

// 核心的節點查找方法 - O(n)時間複雜度 Node node(int index) { if (index < (size >> 1)) { // 索引在前半部分 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 索引在後半部分 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } ```

雖然LinkedList通過從兩端遍歷進行了優化，但get操作仍然是O(n)時間複雜度。

4. 性能對比實測

4.1 基準測試代碼

```java public class ListPerformanceTest { private static final int SIZE = 100000;

public static void main(String[] args) {
    // 順序插入性能測試
    testAddPerformance();

// 隨機訪問性能測試 testGetPerformance(); // 隨機插入性能測試 testInsertPerformance(); // 內存佔用測試 testMemoryUsage();

}

static void testAddPerformance() {
// ArrayList順序插入
List<Integer> arrayList = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
arrayList.add(i);
}
long arrayListTime = System.nanoTime() - start;

// LinkedList順序插入
List<Integer> linkedList = new LinkedList<>();
start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
    linkedList.add(i);
}
long linkedListTime = System.nanoTime() - start;
System.out.printf("順序插入%d個元素：\n", SIZE);
System.out.printf("ArrayList: %d ns\n", arrayListTime);
System.out.printf("LinkedList: %d ns\n", linkedListTime);

}

static void testGetPerformance() {
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// 準備測試數據
for (int i = 0; i < SIZE; i++) {
    arrayList.add(i);
    linkedList.add(i);
}
// ArrayList隨機訪問
long start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
    arrayList.get(i);
}
long arrayListTime = System.nanoTime() - start;
// LinkedList隨機訪問
start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
    linkedList.get(i);
}
long linkedListTime = System.nanoTime() - start;
System.out.printf("\n隨機訪問%d次：\n", SIZE);
System.out.printf("ArrayList: %d ns\n", arrayListTime);
System.out.printf("LinkedList: %d ns\n", linkedListTime);

}

} ```

4.2 實測結果分析

在實際測試中（數據量10萬級別），我們可以看到明顯的性能差異：

順序插入性能： - ArrayList：由於需要偶爾擴容，但攤銷後性能很好 - LinkedList：每次插入都是O(1)，但對象創建開銷較大

隨機訪問性能： - ArrayList：O(1)時間複雜度，性能極佳 - LinkedList：O(n)時間複雜度，性能極差

5. 內存佔用分析

5.1 ArrayList內存結構

java // ArrayList內存佈局（64位JVM，壓縮指針開啓） // - 對象頭: 12字節 // - elementData引用: 4字節 // - size: 4字節 // - modCount: 4字節 // - 數組對象頭: 16字節 // - 數組數據: n 4字節（引用大小） // 總內存 ≈ 40 + n 4 字節

5.2 LinkedList內存結構

```java // 每個Node節點的內存佔用： // - 對象頭: 12字節 // - item引用: 4字節 // - next引用: 4字節
// - prev引用: 4字節 // 對齊填充: 4字節（64位JVM要求8字節對齊） // 每個節點 ≈ 28字節

// LinkedList總內存 ≈ 32（LinkedList對象） + n 28 字節 ```

內存佔用對比： - 小數據量時：LinkedList內存佔用更大（節點開銷） - 大數據量時：ArrayList更緊湊，但可能有空間浪費

6. 迭代器性能對比

6.1 ArrayList迭代器實現

```java private class Itr implements Iterator { int cursor; // 下一個要返回的元素索引 int lastRet = -1; // 最近返回的元素索引 int expectedModCount = modCount;

public boolean hasNext() {
    return cursor != size;
}

@SuppressWarnings(“unchecked”)
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i]; // 直接數組訪問
}

} ```

6.2 LinkedList迭代器實現

```java private class ListItr implements ListIterator { private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount;

public boolean hasNext() {
    return nextIndex < size;
}

public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();

lastReturned = next;
next = next.next;  // 移動到下一個節點
nextIndex++;
return lastReturned.item;

}

} ```

迭代性能：兩者都是O(n)，但ArrayList的緩存局部性更好，實際性能更優。

7. 實際應用場景建議

7.1 推薦使用ArrayList的場景

```java // 場景1：頻繁隨機訪問 public class RandomAccessExample { public static int binarySearch(List list, int key) { // 二分查找需要頻繁隨機訪問 - 選擇ArrayList int low = 0; int high = list.size() - 1;

while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = list.get(mid);  // 頻繁的get操作
        // ... 二分查找邏輯
    }
    return -1;
}

}

// 場景2：內存敏感的應用 public class MemorySensitiveApp { public void processLargeData() { // 處理大量數據時，ArrayList內存效率更高 List dataList = new ArrayList<>(1000000); // ... 數據處理 } } ```

7.2 推薦使用LinkedList的場景

```java // 場景1：頻繁在頭部插入刪除 public class QueueSimulation { public static void main(String[] args) { // 實現隊列功能 - 頻繁在頭部刪除，尾部添加 LinkedList queue = new LinkedList<>();

// 入隊操作
    queue.addLast(1);
    queue.addLast(2);

// 出隊操作 - LinkedList.removeFirst()是O(1) while (!queue.isEmpty()) { Integer item = queue.removeFirst(); System.out.println("處理: " + item); }

}

// 場景2：中間頻繁插入刪除 public class MiddleOperationExample { public static void main(String[] args) { LinkedList list = new LinkedList<>(); list.addAll(Arrays.asList("A", "B", "D", "E"));

// 在中間插入元素 - O(1)時間複雜度
    ListIterator iterator = list.listIterator();
    while (iterator.hasNext()) {
        if ("B".equals(iterator.next())) {
            iterator.add("C");  // 在B後面插入C
            break;
        }
    }
}

} ```

8. Java 8+的優化特性

8.1 ArrayList的性能改進

Java 8在ArrayList中引入了更好的擴容策略和流式操作：

```java // 使用流API進行批量操作 List arrayList = new ArrayList<>(); IntStream.range(0, 1000000).forEach(arrayList::add);

// 並行流處理 - ArrayList支持更好的並行性能 long count = arrayList.parallelStream() .filter(i -> i % 2 == 0) .count(); ```

8.2 LinkedList的改進限制

LinkedList由於底層結構限制，在並行處理和流操作中收益有限：

```java // LinkedList的流操作性能較差 List linkedList = new LinkedList<>(); IntStream.range(0, 100000).forEach(linkedList::add);

// 並行處理效果不明顯，因為鏈表遍歷是順序的 long count = linkedList.parallelStream() // 並行效果有限 .filter(i -> i % 2 == 0) .count(); ```

9. 總結與最佳實踐

9.1 性能總結表格

| 操作 | ArrayList | LinkedList | 推薦選擇 | |------|-----------|------------|----------| | get(int index) | O(1) | O(n) | ArrayList | | add(E element) | O(1)攤銷 | O(1) | 相當 | | add(int index, E element) | O(n) | O(1) | LinkedList | | remove(int index) | O(n) | O(1) | LinkedList | | 內存效率 | 高 | 較低 | ArrayList | | 迭代性能 | 高 | 中等 | ArrayList |

9.2 選擇建議

優先選擇ArrayList：在大多數情況下，ArrayList是更好的選擇
特定場景使用LinkedList：當需要頻繁在列表中間進行插入刪除操作時
考慮內存因素：內存敏感的應用優先選擇ArrayList
利用接口編程：List<Integer> list = new ArrayList<>();

9.3 現代Java開發中的考量

隨着硬件發展，CPU緩存的重要性日益突出。ArrayList的連續內存佈局能夠更好地利用緩存局部性，這在現代CPU架構中具有顯著優勢。而LinkedList的節點分散存儲可能導致較多的緩存未命中。

java // 充分利用ArrayList的緩存友好性 public class CacheFriendlyExample { public static void processList(List<Data> list) { // ArrayList的連續內存訪問模式對緩存友好 for (Data data : list) { data.process(); // 緩存命中率高 } } }

本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。

mob64ca140caeb2 博客

mob64ca140caeb2 博客

博客 / 詳情