0
0

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

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

本篇学习目标：

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

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

文章目录

写在前面

本篇内容为单列集合中的 

ArrayList

、

LinkedList

与 

Vector

。 在下一篇中将讲述 

HashSet

与 

TreeSet

，敬请期待。实验环境为 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 =newArrayList();
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中维护了两个属性 first 与 last，分别指向 首节点和尾节点；
  3. 每个节点都是一个 Node对象，以内部类的形式，其内维护了 prev、next、item三个属性。prev指向前一个节点，next指向后一个节点，从而实现双向链表；
  4. 由于LinkedList不是通过数组实现的，进行 添加和删除操作时效率较高。 因为不需要数组的扩容，删除和添加。只需要更改 next、prev的指向关系即可。

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

4.3 LinkedList源码解读

🐜 以添加元素为例：

🐰 源码解读：
  对下面的代码进行 

debug

：
在这里插入图片描述
  首先 调用了无参构造器，但是没有任何作用。此时 

linkedList

相关参数值如图：
在这里插入图片描述
在这里插入图片描述
 当进行 

add

方法的时候，一如既往的先进行自动装箱：
在这里插入图片描述
  然后进入 

add

方法中的 

linkLast

方法 ，**在该方法中，创建了一个新的节点用于存储 

add

的参数，并且 

prev

与 

next

均为 

null

，此时 

first

与 

last

都指向该节点：** 简单的说，就是将一个新的节点添加到当前的表尾。
在这里插入图片描述
  如果此时再往后一步，比如 

add(2);

则会继续执行上图的代码，此时，**

last

将指向新节点，而新节点的 

prev

指向原表尾的最后一个节点，该节点再指向新节点：**
在这里插入图片描述

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

集合底层结构增删效率改查效率

ArrayList

可变数组较低，因为存在数组扩容较高

LinkedList

双向链表较高，通过链表追加较低

写在最后

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

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

标签： java 面试 开发语言
本文转载自: https://blog.csdn.net/m0_60353039/article/details/124795486
版权归原作者 Nezuko627 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【JavaSE】深入源码解读ArrayList、Vector与LinkedList”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

盘点10款顶级加密软件，让你的数据更安全

2024ICPC网络赛第一场

cmake应用：集成gtest进行单元测试_cmake 使用 gtest

ubuntu20.04 安装vscode 并且配置环境

Windows下如何查看一个dll依赖的其他dll库

【C++】—— list 模拟实现

离线 VisualStudio2022 安装包在无互联网的环境下安装

文章导航