ArrayList与LinkedList

简介: 在Java中有两种用来存储列表的集合类:ArrayList与LinkedList,我们来讨论一下它们两者之间的区别 ArrayListArrayList维护着对象引用的一个内部数组...

在Java中有两种用来存储列表的集合类:ArrayList与LinkedList,我们来讨论一下它们两者之间的区别

ArrayList

ArrayList维护着对象引用的一个内部数组,它是可以 动态增长
动态增长方式:ArrayList 默认大小是10,当调用add方法且内部数组已经满了,数组列表就将自动创建一个更大的数组,并将所有的对象从原来的数组中拷贝到新的更大的数组中

ArrayList增长方式源码:

// 若ArrayList的容量不足以容纳当前的全部元素,设置新的容量 = (原始容量x3)/2 + 1
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

注意:数组列表的容量与数组的大小有一个非常重要的区别,如果为数组分配100个元素的存储空间,数组就有100个空位置可以使用,而容量为100个元素的数组列表只是拥有保存100个元素的潜力(实际上,重新分配空间的话,将会超过100),但是在最初,甚至完成初始化之后,数组列表根本就不含有任何元素
因为ArrayList是依靠数组形式存储数据,所以它最大的 缺点 就是:
执行从中间插入与删除元素操作代价很大,因为数组中间的任何一个位置出现变动,所有后面的元素都要移动位置
优点 是:
它支持高效率的随机访问,你可以通过数组下标快速的访问任意元素

LinkedList

LinkedList是依靠链表实现列表的存储的,实际上,在Java中,所有的链表都是双向链接的,即每个结点除指向下一个结点的next引用,还存放着指向前驱结点的previous引用

LinkedList正好与ArrayList相反,它在插入与删除元素上表现的很高效,但是,在访问元素上就表现的并不高效

LinkedList随机访问的效率非常的低,它依靠迭代器ListIterator类从前后两个方向遍历链表中的元素,并可以添加、删除元素,所以如果想要删除链表当中的元素,或是从中插入新元素,都必须从头或从尾逐个遍历过去

在LinkedList中先添加3个元素,然后再将第2个元素删除:

List<String> staff = new LinkedList<>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator iter = staff.iterator();
String first = iter.next();  // first == "Amy"
String second = iter.next();  // second == "Bob"
iter.remove();   // remove Bob

在调用next之后,remove方法会删除迭代器左侧的元素,如果调用previous就会删除右侧的元素,并且不能连续两次调用remove

add方法只依赖于迭代器的位置,而remove方法依赖于迭代器的状态

在使用迭代器对LinkedList进行读写操作时,会有一些安全隐患,比如,如果有很多迭代器对同一个LinkedList进行操作,前一个迭代器将下一个迭代器要访问的元素删除了,那么就会出错,为了避免发生并发修改异常,我们需要遵循以下原则
可以给容器附加多个可读迭代器,但是一个容器最好只附加一个可写迭代器

有一种简单的方法可以检测到并发修改的问题。集合可以跟踪改写操作的次数,每个迭代器都维护一个独立的计数值,在每个迭代器方法的开始处检查自己改写操作的计数值是否与集合改写操作计数值一致,如果不一致,抛出一个ConcurrentModificationException

参考文献:[美]Cay S. Horsimann著 《Java 核心技术 卷I》(第十版)

目录
相关文章
|
10天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1216 5
|
9天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1180 87
|
10天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1773 12
|
19天前
|
人工智能 运维 安全
|
2天前
|
资源调度
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
230 127
|
10天前
|
弹性计算 Kubernetes jenkins
如何在 ECS/EKS 集群中有效使用 Jenkins
本文探讨了如何将 Jenkins 与 AWS ECS 和 EKS 集群集成,以构建高效、灵活且具备自动扩缩容能力的 CI/CD 流水线,提升软件交付效率并优化资源成本。
362 0