『JAVA集合·学习之路』-List（包含底层源码实现）

深藏阁楼爱情的钟 2023-09-28 23:26 26阅读 0赞

#### List ####

*   *   *   *  List集合概述
             *  List集合特点
             *  List特有的方法
             *  ArrayList
             *   *  源码解析
             *  LinkedList
             *   *  LinkedList源码解析

##### List集合概述 #####

*  有序集合，这里的有序指的是存放顺序
 *  用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引访问元素，并搜索列表中的元素
 *  与Set集合不同，列表通常允许重复的元素

##### List集合特点 #####

*  有序：存储和取出的元素顺序一致
 *  有索引：可以通过索引操作元素
 *  可重复：存储的元素可以重复

##### List特有的方法 #####

![请添加图片描述][5993dd2c99fc43129f47ede869118bde.png]

##### ArrayList #####

*  ArrayList ：底层数据结构是数组，查询快，增删慢。

###### 源码解析 ######

**底层实现：当我们利用空参构造创建了一个ArrayList对象时，它在底层先创建了一个长度为0的数组**，当我们用add()方法添加第一个数据时，它会创建一个新的长度为10的数组，里面**默认初始化值都为NULL**，所以我们一般默认认为ArrayList底层的数组**默认长度为10**，这个数组在底层的名字叫做**elementData**.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

![请添加图片描述][ed30bc6ec947484fb07e87ce650816af.png]

并且ArrayList底层还有一个**变量**size（注意！是变量），默认指向**0索引**，这个变量有两层含义：①表示下一次要操作的索引，②表示当前数组中元素的个数。当size达到10时，集合会自动扩容1.5倍（新数组长度15），然后将元素拷贝到新数组。  
![请添加图片描述][5652386a552a4387a4aa09a0e944081f.png]  
**查询：** list.get(int index)如果获取的索引大于等于size，将会报错

**遍历：**

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

##### LinkedList #####

*  LinkedList：底层数据结构是链表，查询慢，增删快。

**LinkedList集合的特有功能**  
![请添加图片描述][ba424bbc0bfd4bb8a2845c24d83b347e.png]

###### LinkedList源码解析 ######

**底层实现：**

LinkedList底层是一个双向链表  
![请添加图片描述][20c1c699e89d45aab690cda652afc962.png]  
它的每一个节点有三个值 **itme**存储本结点应该存储的值，**next**存储下一个结点的地址值，**prev**存储上一个结点的地址值  
![请添加图片描述][fb48fc1b8b9d4c62a43aba3f8ed6d257.png]  
当我们 **new LinkedList<>()** 时，相当于在堆内存中开辟了一块小空间，开辟完空间之后，LinkedList会维护两个变量 **Node first**（头结点）和 **Node last**（最后一个结点）。

当我们利用**add()** 方法添加元素时，**add()** 方法会将元素传递给 **linkedLast()** 方法，linkedList()方法里面会利用 **Node newNode = new Node<>(l, e, null)** 在堆内存里面开辟新的小空间创建一个新结点

此处存的就是**e**的值，而下一个结点的地址值又变成了null。  
![请添加图片描述][c3025878dccd4bbdbc6eafef55d90322.png]  
添加第二个元素  
![请添加图片描述][4c6def0103fe412899b30c3cad51802c.png]  
后面的元素类似![请添加图片描述][f7143825bd044756b34b78233e4b212d.png]

[5993dd2c99fc43129f47ede869118bde.png]: https://img-blog.csdnimg.cn/5993dd2c99fc43129f47ede869118bde.png
[ed30bc6ec947484fb07e87ce650816af.png]: https://img-blog.csdnimg.cn/ed30bc6ec947484fb07e87ce650816af.png
[5652386a552a4387a4aa09a0e944081f.png]: https://img-blog.csdnimg.cn/5652386a552a4387a4aa09a0e944081f.png
[ba424bbc0bfd4bb8a2845c24d83b347e.png]: https://img-blog.csdnimg.cn/ba424bbc0bfd4bb8a2845c24d83b347e.png
[20c1c699e89d45aab690cda652afc962.png]: https://img-blog.csdnimg.cn/20c1c699e89d45aab690cda652afc962.png
[fb48fc1b8b9d4c62a43aba3f8ed6d257.png]: https://img-blog.csdnimg.cn/fb48fc1b8b9d4c62a43aba3f8ed6d257.png
[c3025878dccd4bbdbc6eafef55d90322.png]: https://img-blog.csdnimg.cn/c3025878dccd4bbdbc6eafef55d90322.png
[4c6def0103fe412899b30c3cad51802c.png]: https://img-blog.csdnimg.cn/4c6def0103fe412899b30c3cad51802c.png
[f7143825bd044756b34b78233e4b212d.png]: https://img-blog.csdnimg.cn/f7143825bd044756b34b78233e4b212d.png