用 ArrayList 还是 LinkedList？看完你就懂了！

本是古典何须时尚 2022-09-06 15:27 296阅读 0赞

本文旨在为 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<Object> arrayList = new ArrayList<>(); // 声明一个 array list
      List<Object> linkedList = new LinkedList(); // 声明 linked list
      // 确保线程安全
      List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());
      List<Object> 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<type>(initialCapacity)
    List arr = new ArrayList<Integer>(10);

默认情况下，ArrayList 创建初始容量为10的列表，而 LinkedList 只构造一个没有设置任何初始容量的空列表。 Linkedlist 不实现 RandomAccess 接口，而 ArrayList 实现了 RandomAccess 接口（而非 Deque 接口）。

# 4. 各种操作的时空复杂性 #

![20210821150117293.png][]

# 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 使用时多次复制数组元素的开销要小。

欢迎分享你对这个话题的经验与见解，请在文章的评论区中提出你的想法。

原文：[https://dzone.com/articles/arraylist-or-linkedlist][https_dzone.com_articles_arraylist-or-linkedlist]  
翻译：唐尤华

**近期热文推荐：**

1.[1,000+ 道 Java面试题及答案整理(2021最新版)][1_000_ _ Java_2021]

2.[别在再满屏的 if/ else 了，试试策略模式，真香！！][if_ else]

3.[卧槽！Java 中的 xx ≠ null 是什么新语法？][Java _ xx _ null]

4.[Spring Boot 2.5 重磅发布，黑暗模式太炸了！][Spring Boot 2.5]

5.[《Java开发手册（嵩山版）》最新发布，速速下载！][Java]

觉得不错，别忘了随手点赞+转发哦！

[20210821150117293.png]: /images/20220829/e13191d810b54203ad6e193347a9ca92.png
[https_dzone.com_articles_arraylist-or-linkedlist]: https://dzone.com/articles/arraylist-or-linkedlist
[1_000_ _ Java_2021]: https://www.javastack.cn/mst/
[if_ else]: https://www.javastack.cn/article/2021/strategy-pattern-instead-of-if-else/
[Java _ xx _ null]: https://www.javastack.cn/article/2021/intellij-idea-ligatures-settings/
[Spring Boot 2.5]: https://www.javastack.cn/article/2021/spring-boot-2.5-released/
[Java]: http://www.javastack.cn/article/2020/alibaba-release-java-develop-rules-songshan/