本文旨在为 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. 各种操作的时空复杂性

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/ar…

翻译：唐尤华

近期热文举荐：

1.1,000+ 道 Java 面试题及答案整顿 (2021 最新版)

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

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

4.Spring Boot 2.5 重磅公布，光明模式太炸了！

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

感觉不错，别忘了顺手点赞 + 转发哦！