1. 一句话结论
arraylist 基于动态数组,随机访问快、尾部追加快;linkedlist 基于双向链表,头尾插入删除快,但随机访问慢。绝大多数业务场景优先选 arraylist。
2. 底层数据结构
| 对比项 | arraylist | linkedlist |
|---|---|---|
| 底层结构 | 动态数组(object[] elementdata) | 双向链表(node 节点,含 prev/next) |
| 内存布局 | 连续内存 | 分散内存,每个节点额外存两个引用 |
| 是否实现 deque | 否 | 是(可作为队列/双端队列使用) |
arraylist 的核心字段:
transient object[] elementdata; // 存储元素的数组 private int size; // 实际元素个数
linkedlist 的节点定义:
private static class node<e> {
e item;
node<e> next;
node<e> prev;
}
3. 时间复杂度对比
| 操作 | arraylist | linkedlist |
|---|---|---|
get(index) 随机访问 | o(1) | o(n) |
尾部 add(e) | 均摊 o(1) | o(1) |
头部 add(0, e) | o(n) | o(1) |
中间 add(index, e) | o(n) | 查找 o(n) + 插入 o(1) |
remove(index) | o(n) | 查找 o(n) + 删除 o(1) |
| 遍历 | 快(连续内存,缓存友好) | 较慢(指针跳转,缓存不友好) |
注意:linkedlist 的「插入删除 o(1)」有个前提——已经拿到目标节点。如果只给下标,仍然要先遍历定位,整体还是 o(n)。
4. 内存占用
arraylist:数组本身有容量冗余(扩容后可能浪费空间),但每个元素只占一个引用。linkedlist:每个元素都要额外维护一个node对象,包含item、next、prev三个引用,内存开销明显更大。
粗略估算:同样存 100 万个元素,linkedlist 的额外对象头和指针开销通常是 arraylist 的数倍。
5. 扩容机制
arraylist 默认容量为 10,扩容时按 1.5 倍增长:
int newcapacity = oldcapacity + (oldcapacity >> 1); elementdata = arrays.copyof(elementdata, newcapacity);
扩容会触发数组拷贝,因此如果能预估元素数量,建议在构造时指定初始容量:
list<string> list = new arraylist<>(10000);
linkedlist 没有扩容概念,每次插入都新建节点。
6. 代码示例:性能差异实测
import java.util.arraylist;
import java.util.linkedlist;
import java.util.list;
public class listbenchmark {
private static final int n = 100_000;
public static void main(string[] args) {
list<integer> arraylist = new arraylist<>();
list<integer> linkedlist = new linkedlist<>();
// 1. 尾部追加
long t1 = system.nanotime();
for (int i = 0; i < n; i++) arraylist.add(i);
long t2 = system.nanotime();
for (int i = 0; i < n; i++) linkedlist.add(i);
long t3 = system.nanotime();
system.out.println("尾部追加 arraylist: " + (t2 - t1) / 1_000_000 + " ms");
system.out.println("尾部追加 linkedlist: " + (t3 - t2) / 1_000_000 + " ms");
// 2. 随机访问
long t4 = system.nanotime();
long sum1 = 0;
for (int i = 0; i < n; i++) sum1 += arraylist.get(i);
long t5 = system.nanotime();
long sum2 = 0;
for (int i = 0; i < n; i++) sum2 += linkedlist.get(i);
long t6 = system.nanotime();
system.out.println("随机访问 arraylist: " + (t5 - t4) / 1_000_000 + " ms");
system.out.println("随机访问 linkedlist: " + (t6 - t5) / 1_000_000 + " ms");
}
}典型结果:尾部追加两者接近,随机访问 arraylist 快一到两个数量级。
7. 如何选择
- 优先
arraylist:绝大多数业务场景,尤其是读多写少、需要按下标访问、需要遍历。 - 考虑
linkedlist:频繁在头部插入/删除,或需要当作队列/双端队列使用(此时更推荐直接用arraydeque)。 - 需要线程安全:两者都不是线程安全的,可用
collections.synchronizedlist或copyonwritearraylist(读多写少场景)。
8. 常见误区
- 「linkedlist 插入删除一定比 arraylist 快」:错。按下标插入时,定位本身就要 o(n),且数组拷贝在数据量不大时非常快。
- 「linkedlist 更省内存」:错。每个节点额外两个引用加对象头,通常更费内存。
- 「linkedlist 适合做队列」:
arraydeque在绝大多数场景下性能更好,官方也推荐优先使用它。
9. 总结
arraylist 是默认选择,linkedlist 只在特定场景(已知节点位置的频繁增删、需要双端操作)才有优势。理解底层结构,才能在实际开发中做出合理选型。
到此这篇关于java中的arraylist 与 linkedlist 的区别、原理、性能与选型实战指南的文章就介绍到这了,更多相关java arraylist 与 linkedlist 的区别内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网!
发表评论