> 文档中心 > 【JavaSE】深入源码解读ArrayList、Vector与LinkedList

【JavaSE】深入源码解读ArrayList、Vector与LinkedList

💁 个人主页:Nezuko627的博客主页
❤️ 支持我:👍 点赞 🌷 收藏 🤘关注
🎏 格言:立志做一个有思想的程序员 🌟
📫 作者介绍:本人本科软件工程在读,博客主要涉及JavaSE、JavaEE、MySQL、SpringBoot、算法等知识。专栏内容长期更新,如有错误,欢迎评论区或者私信指正!期待共同进步~~~
Tips:一步一个脚印,才能承接所谓的幸运。

本篇学习目标:

  • ⭐️ 熟悉List接口的常用方法
  • ⭐️ 掌握ArrayList与Vector的扩容原理与区别;
  • ⭐️ 了解LinkedList的底层原理;
  • ⭐️ 掌握ArrayList与LinkedList的区别;
  • ⭐️ 掌握 debug 的方式查看源码。

本文来自专栏:JavaSE系列专题知识及项目 欢迎点击支持订阅专栏 ❤️
在这里插入图片描述

文章目录

  • 写在前面
  • 1 List接口
    • 1.1 List接口的基本介绍
    • 1.2 List接口常用方法
    • 1.3 List的遍历方式
  • 2 ArrayList
    • 2.1 ArrayList说明
    • 2.2 ArrayList扩容机制与源码解读
  • 3 Vector
    • 3.1 Vector说明
    • 3.2 Vector扩容机制与源码解读
    • 3.3 小结——ArrayList与Vector横向对比
  • 4 LinkedList
    • 4.1 LinkedList说明
    • 4.2 LinkedList底层操作机制
    • 4.3 LinkedList源码解读
    • 4.4 小结——ArrayList与LinkedList横向对比
  • 写在最后

写在前面

本篇内容为单列集合中的 ArrayListLinkedListVector。 在下一篇中将讲述 HashSetTreeSet,敬请期待。实验环境为 jdk-1.8。
在这里插入图片描述


1 List接口

1.1 List接口的基本介绍

List 接口是 Collection 接口的子接口:

  1. List 集合类中的元素有序,且可重复。 有序指的是: 添加顺序与取出顺序一致;
  2. List 集合中每个元素都有对应的顺序索引,即 支持索引。

1.2 List接口常用方法

方法 作用
void add(int index,Object ele) 在index位置插入ele元素,如果没有指定index,则默认添加在最后
boolean addAll(int index,Collection eles) 从index位置开始将eles中的所有元素添加进来
Object get(int index) 获取指定index位置的元素
int indexOf(Object obj) 返回obj在当前集合中首次出现的位置
int lastIndexOf(Object obj) 返回obj在当前集合中末次出现的位置
Object remove(int index) 移除指定index位置的元素,并返回此元素
Object set(int index,Object ele) 设置指定index位置的元素为ele,类似替换
List subList(int fromIndex, int toIndex) 返回从fromIndex到toIndex位置的子集合[fromIndex,toIndex)

1.3 List的遍历方式

 List主要有以下三种遍历方式,这里给大家简单示范一下(未使用泛型):

List myList = new ArrayList();myList.add("Nezuko627");myList.add("Whisper.❤");myList.add("是你的大头吖");myList.add("小丫么小牛马");myList.add("小鹏Linux");

方式1️⃣ :使用迭代器 iterator:

Iterator iter = myList.iterator();while (iter.hasNext()){    Object obj = iter.next();    System.out.println(obj);}

方式2️⃣: 使用增强 for:

for (Object obj: myList) {    System.out.println(obj);}

方式3️⃣: 使用 for:

for (int i = 0; i < myList.size(); i++) {    System.out.println(myList.get(i));}

🍎 结果:

Nezuko627
Whisper.❤
是你的大头吖
小丫么小牛马
小鹏Linux


2 ArrayList

2.1 ArrayList说明

1️⃣ ArrayList 可以加入 null
在这里插入图片描述

2️⃣ 底层是由数组实现存储的,具体看后面的源码解读;
3️⃣ ArrayList 基本等同 Vector,但是 ArrayList线程不安全的。

2.2 ArrayList扩容机制与源码解读

🐅1. ArrayList 中维护了一个 Object 类型的数组 elementData;

维护的数组用 transient 修饰,是瞬间短暂的,表示该属性不会被序列化。
在这里插入图片描述

🐅2. 当创建 ArrayList 对象时,如果使用的是无参构造器,则初始 elementData 容量为 0。当第一次添加的时候,扩容 elementData 容量为10,如果需要再次扩容,则扩容 1.5倍

🐰 源码解读:
示例代码如下,我们对该段代码进行 debug ,断点已经给出:
在这里插入图片描述
 当程序执行到无参构造器创建 ArrayList 时调用了如下的源码,即创建了一个空的 elementData 数组。
在这里插入图片描述
 当程序进入第一个 for 循环的时候,先对 i 进行了自动装箱, 相关源码如下:
在这里插入图片描述
 然后进入到了 add 方法,在该方法中 首先调用 ensureCapacityInternal 方法,确定容量是否够用,如果不够则进行扩容,够用则执行向 elementData 数组中添加元素的操作:
在这里插入图片描述
 那么,初始的容量10是如何计算的呢? 我们追进 ensureCapacityInternal 方法来看下相关源码,发现在该方法中 首先计算出 minCapacity,第一次扩容为10。modCount 则记录集合被修改的次数。当 elementData 的大小不够就调用 grow 去扩容:
在这里插入图片描述
 来具体看下 grow方法,在该方法中进行了容量的判别,第一次 newCapacity = 10,第二次及以后,按照1.5倍扩容。 扩容使用的是 Arrays.copyof()方法,保留了原来的数据:
在这里插入图片描述
 此时 elementData数组均为 null
在这里插入图片描述
  i = 1 放入 elementData索引为 0 的位置,往后的循环重复此操作(i = 2 放入索引为 1 的位置以此类推)。当进入第二个 for 循环时,执行扩容操作,新的容量为原来的 1.5倍。初始容量变为15,其数据初始为1~10与5个null。 后面就是上面过程的重复,不再赘述,读者们可以尝试自行 debug
在这里插入图片描述

🐅3. 如果使用的是指定大小的构造器,则初始容量为指定大小,当需要再次扩容时,扩容 1.5倍

🐰 源码解读:
与第二点的源码区别在于,这里使用了 有参构造器创建了一个指定大小的 elementData 数组,其余的与上述分析过的源码保持一致。 只不过是当初始容量不足以存储数据时,进行扩容操作。
在这里插入图片描述


3 Vector

3.1 Vector说明

🆔 基本介绍:

🚗 1. Vector 定义说明:
在这里插入图片描述
🚗 2. Vector 底层也是一个对象数组,protect Object[] elementData
🚗 3. Vector线程同步的,即线程安全,其方法带有 synchronized,在实际开发中,需要线程同步安全时,考虑使用 Vector:
在这里插入图片描述

3.2 Vector扩容机制与源码解读

🐑1. Vector中维护了一个 Object 类型的数组 elementData;

🐑2. 当创建 Vector对象时,如果使用的是无参构造器,则初始 elementData 容量为 10。如果需要再次扩容,则扩容 2倍

🐑3. 如果使用的是指定大小的构造器,则初始容量为指定大小,当需要再次扩容时,扩容 2 倍

🐰 源码解读:
 以无参构造为例,断点如下图,进行 debug:
在这里插入图片描述
 当程序执行到无参构造器创建 Vector时调用了如下的源码,此时默认赋值10,即初始容量为10:
在这里插入图片描述
  进入for循环,以第一次为例,此时 i = 0,同样进行了一个自动装箱的操作:
在这里插入图片描述
 然后进入到了 add 方法,与 ArrayList 类似,在该方法中 首先调用 ensureCapacityHelper 方法,确定容量是否够用,如果不够则进行扩容,够用则执行向 elementData 数组中添加元素的操作:
在这里插入图片描述
ensureCapacityHelper 方法中还是进行了判断,容量不够时调用 grow方法扩容:
在这里插入图片描述
  值得注意的是在grow方法中(在debug中需要添加元素超过容量10时才会进入该方法),当需要扩容时,则扩容至原容量的2倍:
在这里插入图片描述

3.3 小结——ArrayList与Vector横向对比

集合 底层结构 版本 线程与效率 扩容机制
ArrayList 可变数组 jdk1.2 线程不安全但是效率高 无参构造:初始10,每次扩容1.5倍;有参构造:每次扩容1.5倍
Vector 可变数组 jdk1.0 线程安全但是效率不高 无参构造:默认10,每次扩容2倍;有参构造:指定大小,每次扩容2倍

4 LinkedList

4.1 LinkedList说明

🆔 基本介绍:

🐍 1. LinkedList 实现了 双向链表和双端队列;
🐍 2. 可以 添加任意元素 ,元素可以重复,包括 null
🐍 3. 线程不安全,没有实现同步。

4.2 LinkedList底层操作机制

  1. LinkedList底层维护了一个双向链表;
  2. LinkedList中维护了两个属性 firstlast,分别指向 首节点和尾节点;
  3. 每个节点都是一个 Node对象,以内部类的形式,其内维护了 prevnextitem三个属性。prev指向前一个节点,next指向后一个节点,从而实现双向链表;
  4. 由于LinkedList不是通过数组实现的,进行 添加和删除操作时效率较高。 因为不需要数组的扩容,删除和添加。只需要更改 nextprev的指向关系即可。

🐘 示意图:
在这里插入图片描述

4.3 LinkedList源码解读

🐜 以添加元素为例:

🐰 源码解读:
  对下面的代码进行 debug
在这里插入图片描述
  首先 调用了无参构造器,但是没有任何作用。此时 linkedList 相关参数值如图:
在这里插入图片描述
在这里插入图片描述
 当进行 add 方法的时候,一如既往的先进行自动装箱:
在这里插入图片描述
  然后进入 add 方法中的 linkLast 方法 ,在该方法中,创建了一个新的节点用于存储 add 的参数,并且 prevnext 均为 null,此时 firstlast 都指向该节点: 简单的说,就是将一个新的节点添加到当前的表尾。
在这里插入图片描述
  如果此时再往后一步,比如 add(2); 则会继续执行上图的代码,此时,last 将指向新节点,而新节点的 prev 指向原表尾的最后一个节点,该节点再指向新节点:
在这里插入图片描述

4.4 小结——ArrayList与LinkedList横向对比

集合 底层结构 增删效率 改查效率
ArrayList 可变数组 较低,因为存在数组扩容 较高
LinkedList 双向链表 较高,通过链表追加 较低

写在最后

🌟以上便是本文的全部内容啦,后续内容将会持续免费更新,如果文章对你有所帮助,麻烦动动小手点个赞 + 关注,非常感谢 ❤️ ❤️ ❤️ !
如果有问题,欢迎私信或者评论区!
在这里插入图片描述

共勉:“你间歇性的努力和蒙混过日子,都是对之前努力的清零。”
在这里插入图片描述

【JavaSE】深入源码解读ArrayList、Vector与LinkedList 创作打卡挑战赛 【JavaSE】深入源码解读ArrayList、Vector与LinkedList 赢取流量/现金/CSDN周边激励大奖好看字体下载