ArrayList和LinkedList的区别、扩容机制以及底层的实现方式
作者:WINGZINGLIU 发布时间:2023-11-27 01:26:57
ArrayList和LinkedList区别、扩容机制及底层实现
ArrayList
ArrayList的底层实现为数组存储在内存中,线程不同步。可通过数组下标的形式进行查找,所以在查询方面的效率较为出色,常用在查询较多的情景下。
LinkedList
LinkedList的底层实现为链表形式,也为线程不同步。而链表的底层也决定了它在查询方面不如数组底层的ArrayList而在指定位置插入等修改操作下,性能优于ArrayList。
Vestor
另外还有Vestor,Vestor也是和ArrayList、LinkedList一样实现了java.util.List接口。最大的区别在于Vestor是线程同步的,所以在效率方面不如另外两者,适用于多线程项目中。
ArrayList的扩容机制
/**
* Constructs an empty list with the specified initial capacity.
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
翻阅源码会发现ArrayList初始化如果不指定大小的时候 初始大小为10。
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;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
扩容的规则也在源码中有体现,扩容后的大小= 原始大小+原始大小/2 + 1。在进行插入等操作的时候,如果判断出大小不够,会依据此方法进行扩容。(以上是JDK1.6版本的源码,在JDK1.7中扩容规则进行了修改,改为了扩容后的大小= 原始大小+原始大小/2)
LinkedList的扩容机制
由于它的底层是用双向链表实现的,没有初始化大小,也没有扩容的机制。
ArrayList和LinkedList(常用方法、底层结构及扩容机制)
1.ArrayList解说
ArrayList初始长度为0(这里以jdk1.8为例),是一个Object类型的空数组,如下
当第一次调用add后,长度变为10
当数组首次扩容的10个空间用完需要扩容后,会第二次走grow方法来扩容(每次扩容为1.5倍)
总的来说:
ArrayList初始大小为10,每次1.5倍进行扩容;它的底层是用数组实现的,所以查询速度相对LinkedList要快。
2.LinkedList解说
(1)
* LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
* LinkedList 实现 List 接口,能对它进行队列操作。
* LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
* LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
* LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
* LinkedList 是非同步的。
由于它的底层是用双向链表实现的,所以它对元素的增加、删除效率要比ArrayList好;它是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
(2)LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
header是双向链表的头节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该
节点所包含的值。size是双向链表中节点实例的个数。
总之,addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解,下面给出插入节点的示意图。
来源:https://blog.csdn.net/WINGZINGLIU/article/details/83715578
猜你喜欢
- IDEA SpringBoot项目配置热更新的步骤1.在pom.xml中添加依赖:<dependency><groupId
- 一、原理1、不变模式(不可变对象)在并行软件开发过程中,同步操作似乎是必不可少的。当多线程对同一个对象进行读写操作时,为了保证对象数据的一致
- 本文实例汇总了Java的System.getProperty()方法获取信息的用法。分享给大家供大家参考。具体如下:System.out.p
- (一) collection和collections这两者均位于java.util包下,不同的是:collection是一个集合接口,有Li
- 本文实例为大家分享了C++实现俄罗斯方块的具体代码,供大家参考,具体内容如下先是效果图:主菜单:游戏:设置:错误处理:代码:#include
- 使用开源项目JAVAE 进行视频格式转换JAVAE简介:JAVE (Java音频视频编码器)库是ffmpeg项目的Java包装器。开发人员可
- Android 自动获取验证码的两种方式分别是BroadcastReceiver及ContentObserver,两种方式都需要进行注册、取
- 一、说明Boost.MPI 提供了 MPI 标准(消息传递接口)的接口。该标准简化了并发执行任务的程序的开发。您可以使用线程或通过共享内存或
- Java裁剪压缩PNG图片,透明背景色变黑import java.awt.Graphics2D;import java.awt.Image;
- 在Java中,可以通过Runtime类或ProcessBuilder类来实现调用外部程序。Runtime类与ProcessBuilder类使
- 一、饿汉式单例类public class Singleton { privat
- 最近在做一个项目,遇到了项目打成 war 包的一个问题,项目创建时选择的时 jar 包方式,后因项目部署要求,需要打成 war 包部署,遇到
- 前言开篇一个例子,我看看都有谁会?如果不会的,或者不知道原理的,还是老老实实看完这篇文章吧。@Slf4j(topic = "c.V
- 本文实例讲述了Android中TextView显示插入的图片实现方法。分享给大家供大家参考,具体如下:Android系统默认给TextVie
- SpringBoot的持久化层可以是Spring内置的轻量级JdbcTemplate、也可以是Hibernate或Mybatis等等,只需要
- 服务降级服务压力剧增的时候,根据当前的业务情况及流量对一些服务和页面有策略的降级,以此缓解服务器的压力,以保证核心任务的进行。同时保证部分甚
- 现假设某个公司采用公用电话来传递数据,数据是四位的整数,在传递过程中是加密的。加密规则是每位数字都加上5,然后再用除以10的余数代替该数字,
- 本文实例为大家分享了Java金额大小写转换的具体代码,供大家参考,具体内容如下/** * @ClassName: NumberConver
- 使用maven的profile功能,我们可以实现多环境配置文件的动态切换,可参考我的上一篇博客。但随着SpringBoot项目越来越火,越来
- Pom依赖<parent> <groupId>org.springframework.bo