关于List集合类ArrayList、LinkedList、Vector详解
各位小伙伴们大家好,欢迎来到这个小扎扎的《Java核心技术 卷Ⅰ》笔记专栏,在这个系列专栏中我将记录浅学这本书所得收获,鉴于 看到就是学到、学到就是赚到 精神,这波简直就是血赚
🛫 关于List集合类你都知道什么?
我们将实现了List接口的类称为是List集合类,List集合类中元素存储有一个特点:有序、可重复,List接口常用的有三个实现类:ArrayList、LinkedList和Vector
🪂 List接口三个实现类的异同?
三者相同点:ArrayList、LinkedList和Vector都实现了List接口,所以它们存储数据的特点都一致,那就是有序、可重复
ArrayList和Vector相比,相同点就是底层结构上都用到了Object [ ]数组存储元素,不同点就是ArrayList是线程不安全但是效率高的,而Vector是线程安全但是效率低的,造成这个不同的原因就是Vector中的方法都使用了同步锁,这样在保证线程安全的同时也会降低它的效率
ArrayList和LinkedList相比最大的不同点就是底层存储结构,上面说过ArrayList使用的是Object [ ]数组存储元素,而LinkedList则是使用双向链表进行存储,双向链表的特点就是将每一个元素都存储在一个单独的链接(link)中,这个链接由三部分组成:上一个链接的运用、数据、下一个链接的引用,双向链表就是通过上下引用将所有的链接链成一张表。 要知道数组最令人诟病的就是对元素的添加和删除,每次操作都需要移动它后面的所有元素,双向链表每次添加和删除元素只和它前后的两link有关,只需要改变上下链接的引用即可,这样的话就可以很好的解决这个弊端。于是,涉及到频繁的添加删除操作的话,可以选择使用LinkedList集合。但是由于数组中可以使用索引快速定位一个元素,而链表则是需要从头开始顺着链查找,所以涉及到频繁的查询数据可以选择使用ArrayList
🪂 ArrayList类源码浅析
ArrayList的源码在jdk 7和jdk 8之间还是有些设计上的不同的,接下来就通过对两个版本的分析来体会不同点,并思考一下jdk 8改变设计的原因
jdk 7 使用无参构造器创建一个ArrayList对象会调用它的有参构造器并传参为10,也就是说使用无参构造器默认创建一个长度为10的Object [ ]数组。然后每次调用add方法添加元素之前都会通过ensureCapacityInternal方法判断当前集合再添加新元素,也就是集合中元素个数size + 1之后会不会大于数组长度,如果超过的话就调用grow方法进行扩容。扩容的时候先将当前数组长度扩大1.5倍,如果扩大1.5之后还是无法没有size + 1大的话直接将扩容后的数组长度设置为size + 1;如果扩大1.5倍之后大于给定的常量值,判断size + 1有没有大于这个常量值,大于的话数组长度设为整型的最大值,否则就设置成给定的常量值;至此扩容后的数组长度newCapacity就确定了,然后就是调用Arrays工具类的copyOf方法将原来的数组内容拷贝到长度为newCapacity的新数组中
数组扩容完成之后就是添加新元素,回到add方法中,将参数元素添加到数组中索引为size的位置,然后size + 1索引向后移(这一步就是size++的效果),如果数组无需扩容的话就直接执行添加操作
jdk 8 jdk 8 的时候ArrayList集合调用无参构造器默认创建一个空数组对象,而不是一个有长度的数组,这样做的好处就是可以节省内存提高效率。jdk 7 就是创建一个长度为10的数组,这样的话一旦加载ArrayList类就会给数组定义长度就要按照长度分配内存空间;而jdk 8 中则使用空数组解决了这个问题,等到ArrayList集合调用add方法添加元素的时候才会动态的创建数组,类似于单例设计模式的懒汉模式思想
调用add方法都会发生什么呢?根据上图源码浅析一下,为了便于区分不同的方法调用使用不同颜色标记。
①在添加元素之前,先将当前集合再添加新元素时的长度,也就是集合中元素个数size + 1之后的值,使用②③方法进行一系列的判断
②判断当前的数组是否为空,如果为空的话返回默认数组长度10与size + 1之间的最大值,否则直接返回size + 1
③将②中的返回值作为参数执行③方法判断size + 1的大小是否大于数组的长度,如果是的话就调用grow方法扩容
④扩容的机制和jdk 7中的一致,先将当前数组长度扩大1.5倍,如果扩大1.5之后还是无法没有size + 1大的话直接将扩容后的数组长度设置为size + 1;如果扩大1.5倍之后大于给定的常量值,判断size + 1有没有大于这个常量值,大于的话数组长度设为整型的最大值,否则就设置成给定的常量值;至此扩容后的数组长度newCapacity就确定了,然后就是调用Arrays工具类的copyOf方法将原来的数组内容拷贝到长度为newCapacity的新数组中
根据上述分析,梳理jdk 8 的时候ArrayList集合第一次添加元素流程:首先实例化ArrayList对象的时候会调用无参构造器创建一个空数组对象,然后第一次调用add方法添加元素会被拦截到方法②③进行判断,执行方法②的时候数组为空对象执行判断体返回10(默认数组长度)和1(size + 1)的最大值10,然后执行方法③10(方法②返回值作③的参数)减去0(空数组长度)>0,执行判断体中方法④扩容数组,空数组扩容1.5倍还是小于10,所以将新数组长度定为10,并将原空数组拷贝到新数组中(这一步虽然像废话但是代码中定义有),最后将add的参数放到索引为0的位置,然后索引自增1
所以说,有了上面分析的前车之鉴,大家如果在使用ArrayList集合的时候明显知道元素的个数,或者知道一定多于10个的话,可以在创建ArrayList对象的时候使用有参构造器指定底层数组的长度,这样的话就可以避免向集合对象中添加元素的时候多次扩容,提高程序的效率
🪂 LinkedList类源码浅析
LinkedList类内部定义了一个内部类Node也就是双向链表的一个节点,前面讲过它是由三个部分组成,于是内部类Node也包含三个属性与之对应(上一个节点的引用 => prev、数据 => item、下一个节点的引用 => next),然后使用无参构造器创建LinkedList对象底层什么都不创建并不会像ArrayList一样创建一个数组啥的,但是它会默认初始化类属性first(头结点)和last(尾结点)为null。
再之后就是调用add方法添加元素了,add方法底层使用的是linkLast方法,第一次添加元素的时候last的值为默认初始化的null,否则就是原链表的尾节点。将last的值赋值给 l 这个 l 就是通过有参构造器创建Node对象时的第一个参数,也就是将新链接的前一个节点引用指向原链表的尾节点,然后第二个参数是数据e,第三个参数是null(因为将数据添加到了最后,后面没有节点了,所以下一个节点的引用为null)。将创建好的Node对象赋值给last也就是指定新链表的尾节点,l 是null的话就将创建好的Node对象也赋值给first也就是指定新链表的头节点,表示新链表的头节点和尾节点都是新建节点(因为第一次添加元素双向链表中就只有一个节点);如果不为null的话就将原链表的尾节点的下一个链接的引用指向新节点。
根据上面的分析可以得知,所有的新节点都链在了双向链表的尾部,所以这种方法就是双向链表的尾插法
🪂 vector类源码简析
由于vector类已经很久未更新,于是它的底层源码就和ArrayList的jdk 7 版本的几乎一致,使用无参构造器创建对象的时候会调用有参构造器创建一个长度为10的object数组,只不过是扩容的时候会扩容到原来长度的2倍,它和ArrayList的区别前面也说过就是vector的方法上都加了锁,因此会牺牲性能来保证线程安全
🛫 List的常用API都有哪些?
🪂 List接口的常用API
🪂 linkedList类的特有API
由于linkedList底层特有的双向链表结构,所以它提供了一些可以对链头或者链尾元素进行操作的API
🪂 List集合类的API分析
以下是List集合类的继承实现关系,由于没有系统的学过UML图,所以用文字表示了继承实现关系,大家将就将就看🤐
三个集合类都间接实现了Collection接口,所以上一篇博客里涉及到的Collection接口API,在这三个集合类依旧可以使用,但是Collection接口中的API方法都是抽象方法,是不会就意味着我们需要自己在类中实现这些方法的方法体呢?并不是,还记得我们说完Collection接口之后有接触到了一个类叫AbstractCollection,它实现了Collection接口中大部分常用的API的默认方法体,而我们的三个类都间接继承了这个AbstractCollection类,所以说,类中无需实现Collection接口中的方法,而是直接使用即可
除了Collection的API之外,List集合类还都间接实现了List接口,所以List接口中的API在这三个集合类也可以直接使用,由于列表多是数组作底层结构,所以List接口中的API也都大多有索引的参数用于直接定位到某个元素。毋庸置疑的是List接口中的API也会是抽象的,所以它也有一个和Collection接口一样的实现类AbstractList提供了这些抽象方法的默认实现,三个集合类也都继承了这个实现类,所以直接使用即可无需提供实现
与此同时,List集合类还都间接实现了Iterator接口,所以都可以直接使用Iterator接口的API,借助迭代器遍历集合中的每一个元素。Iterator接口中有一个很重要的方法forEach,可以直接操作集合中的所有元素,具体操作使用Lambda表达式写在forEach方法参数里
![](https://res.hc-cdn.com/ecology/9.3.128/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
- 点赞
- 收藏
- 关注作者
评论(0)