编辑“︁Arraylist与linkedlist”︁

{{Java基础导航}}

== ArrayList与LinkedList ==

'''ArrayList'''和'''LinkedList'''是Java集合框架中两种最常用的列表实现，均实现了<code>List</code>接口，但在底层数据结构、性能特性和适用场景上有显著差异。理解它们的区别对编写高效Java程序至关重要。

=== 概述 ===
* '''ArrayList'''：基于动态数组实现，支持快速随机访问，但在中间插入/删除元素时效率较低。
* '''LinkedList'''：基于双向链表实现，插入/删除高效，但随机访问性能较差。

=== 底层数据结构 ===
<mermaid>
graph LR
    subgraph ArrayList
        A[Object数组] --> B[自动扩容]
    end
    subgraph LinkedList
        C[Node] --> D["prev|item|next"]
        D --> E[前驱节点]
        D --> F[后继节点]
    end
</mermaid>

=== 核心区别对比 ===
{| class="wikitable"
|+ ArrayList vs LinkedList 特性对比
! 特性 !! ArrayList !! LinkedList
|-
| '''数据结构''' | 动态数组 | 双向链表
|-
| '''随机访问''' | O(1) | O(n)
|-
| '''头部插入''' | O(n) | O(1)
|-
| '''尾部插入''' | O(1) 均摊 | O(1)
|-
| '''中间插入''' | O(n) | O(1) 已知位置时
|-
| '''内存占用''' | 更小（仅存储数据） | 更大（额外存储节点信息）
|}

=== 代码示例 ===

==== 基础操作对比 ====
<syntaxhighlight lang="java">
import java.util.*;

public class ListComparison {
    public static void main(String[] args) {
        // 初始化
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 尾部插入性能
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) arrayList.add(i);
        System.out.println("ArrayList尾部插入: " + (System.nanoTime()-start)/1e6 + "ms");

        start = System.nanoTime();
        for (int i = 0; i < 100000; i++) linkedList.add(i);
        System.out.println("LinkedList尾部插入: " + (System.nanoTime()-start)/1e6 + "ms");

        // 随机访问性能
        start = System.nanoTime();
        arrayList.get(50000);
        System.out.println("ArrayList随机访问: " + (System.nanoTime()-start) + "ns");

        start = System.nanoTime();
        linkedList.get(50000);
        System.out.println("LinkedList随机访问: " + (System.nanoTime()-start) + "ns");
    }
}
</syntaxhighlight>

'''输出示例'''：
 ArrayList尾部插入: 12.345ms
 LinkedList尾部插入: 15.678ms
 ArrayList随机访问: 150ns
 LinkedList随机访问: 24500ns

=== 扩容机制 ===
ArrayList的扩容需要数学计算：
<math>
newCapacity = oldCapacity + (oldCapacity >> 1)
</math>

当添加元素超过当前容量时，ArrayList会创建一个新数组（大小为原数组的1.5倍），然后拷贝数据。

=== 实际应用场景 ===
* '''使用ArrayList'''：
  * 频繁随机访问（如<code>get(index)</code>）
  * 主要进行尾部操作
  * 内存敏感的应用

* '''使用LinkedList'''：
  * 频繁在任意位置插入/删除
  * 实现队列/双端队列（实现了<code>Deque</code>接口）
  * 不需要大量随机访问

=== 高级特性 ===
'''LinkedList特有方法'''：
<syntaxhighlight lang="java">
LinkedList<String> list = new LinkedList<>();
list.addFirst("Head");  // 等同于push()
list.addLast("Tail");
String first = list.removeFirst(); // 等同于pop()
String last = list.removeLast();
</syntaxhighlight>

=== 性能分析 ===
对于n个元素的操作时间复杂度：
{| class="wikitable"
|+ 时间复杂度对比
! 操作 !! ArrayList !! LinkedList
|-
| <code>add(E e)</code> | O(1) 均摊 | O(1)
|-
| <code>add(int index, E e)</code> | O(n) | O(1) 已知节点时
|-
| <code>remove(int index)</code> | O(n) | O(1) 已知节点时
|-
| <code>get(int index)</code> | O(1) | O(n)
|}

=== 内存布局可视化 ===
<mermaid>
graph TD
    subgraph ArrayList内存
        A[引用1] --> B[连续内存块]
        C[引用2] --> B
    end
    subgraph LinkedList内存
        D[引用1] --> E[节点A]
        E --> F[节点B]
        F --> G[节点C]
        G --> H[...]
    end
</mermaid>

=== 最佳实践建议 ===
1. 默认首选ArrayList（大多数场景更优）
2. 只有在频繁在列表'''中间'''插入删除时才考虑LinkedList
3. 使用<code>ListIterator</code>可以改善LinkedList的遍历性能
4. 使用<code>initialCapacity</code>参数优化ArrayList初始化

{{Java基础导航}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:Java基础]]