集合框架-List集合深入剖析（重点详细讲解）

目录

前言

一、认识List集合

二、 List集合提供的常用API

2.1 初始化List数组

2.2 void add(int index,E element)——在此集合中的指定位置插入指定的元素

2.3 E remove(int index)——删除指定索引处的元素，返回被删除的元素

2.4 E set(int index,E element)——修改指定索引处的元素，返回被修改的元素

2.5 E get(int index)——返回指定索引处的元素

三、 ArrarList集合底层原理

3.1 ArrarList扩容机制（重点）

四、LinkedList底层原理

4.1 LinkedList提供常用的API

4.2 应用场景——可以用来设计队列

4.3 应用场景——可以用来设计栈

前言

博主计划使用CSDN来记录Java后端开发的学习经历，并分享自己的编程心得和知识，期望能为那些有需求的朋友提供帮助。

博主也期望能与那些持续努力学习的朋友们共同进步！编程之路是一条充满艰辛与挑战的路，需要我们付出更多的心血，才能走得更远。只有通过不懈的研究和深入的思考，以及勤于实践，我们才能在编程的道路上取得真正的成就

一、认识List集合

上一章我们刚刚讲到了Collection集合，不明白什么是集合的小伙伴建议可以先去看看我的上一篇博文《集合框架-Collection》再来看本篇效果会更好~，好的，接下来，我们正式进入到本章的主题《集合框架-List集合》。List它作为单列集合Collection的继承泛型接口之一，它的本质其实就是内存空间连续的数组，每个元素大小占用内存空间是一样的，它的特定是有序，可重复，有索引，另一个是Set集合，它也是一个泛型接口，这个我们下一章再详细的介绍。什么是有序呢？有序的意思是说添加元素后，最终打印出来的元素顺序是按照添加元素的顺序有关的。可重复就是字面意思，添加元素是可以重复的。有索引的意思是说添加完这个元素，它就有一个索引下标的，可以通过这个索引来访问到这个元素。

二、 List集合提供的常用API

List集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection的功能List也都继承了。回顾一下，Collection提供的API

但是我们仔细查看，Collection提供的API中存在很多缺陷，它并没有根据索引来插入元素，它只能在数组的末尾来添加元素，不够灵活，第二个就是Collection也并没有提供根据指定索引来删除元素，它只提供了根据具体元素的值类删除，这一点也并不好。第三个也并没有提供修改指定索引来修改元素和获取指定索引位置的元素

对于上述问题，List继承了Collection接口 ，在它基础上进行添加了独有API，进一步提高单列集合的灵活性

接下来，我们一个一个为大家演示一遍

2.1 初始化List数组

public static void main(String[] args) {

// 目标：掌握List系列集合独有的功能。

//1. 声明List集合

List list = new ArrayList<>(); // 多态 一行经典代码

//2. 添加元素

list.add("Java");

list.add("Css");

list.add("HTML");

list.add("Java");

list.add("Java");

//3. 打印原始数据

System.out.println(list); // [Java, Css, HTML, Java, Java]

}

运行结果

2.2 void add(int index,E element)——在此集合中的指定位置插入指定的元素

public static void main(String[] args) {

// 目标：掌握List系列集合独有的功能。

//1. 声明List集合

List list = new ArrayList<>(); // 多态 一行经典代码

//2. 添加元素

list.add("Java");

list.add("Css");

list.add("HTML");

list.add("Java");

list.add("Java");

//3. 打印原始数据

System.out.println(list); // [Java, Css, HTML, Java, Java]

// 1、插入数据到指定索引。add(索引,元素)

list.add(3, "Python");//在索引为3的元素那里添加Python

System.out.println(list);

}

通过上面，我们在索引为3的元素那里添加Python，然后重新打印数组，注意这里说的是索引，索引是从0开始的，索引3的位置是Java，会在该位置插入Python，其他元素会往后移

运行结果

2.3 E remove(int index)——删除指定索引处的元素，返回被删除的元素

public static void main(String[] args) {

// 目标：掌握List系列集合独有的功能。

//1. 声明List集合

List list = new ArrayList<>(); // 多态 一行经典代码

//2. 添加元素

list.add("Java");

list.add("Css");

list.add("HTML");

list.add("Java");

list.add("Java");

//3. 打印原始数据

System.out.println(list); // [Java, Css, HTML, Java, Java]

// // 1、插入数据到指定索引。add(索引,元素)

list.add(3, "Python");//在索引为3的元素那里添加Python

System.out.println(list);

// 2、根据索引删除数据。remove(索引)

list.remove(4);// 索引为4的元素删除Java

System.out.println(list);//[Java, Css, HTML, Python, Java]

}

这里我们删除了索引为4的下标元素，这里索引4的元素是第一个Java，那么后面那个Java元素要往前移动一个位置，然后重新打印数组。

运行结果

2.4 E set(int index,E element)——修改指定索引处的元素，返回被修改的元素

public static void main(String[] args) {

// 目标：掌握List系列集合独有的功能。

//1. 声明List集合

List list = new ArrayList<>(); // 多态 一行经典代码

//2. 添加元素

list.add("Java");

list.add("Css");

list.add("HTML");

list.add("Java");

list.add("Java");

//3. 打印原始数据

System.out.println(list); // [Java, Css, HTML, Java, Java]

// // 1、插入数据到指定索引。add(索引,元素)

list.add(3, "Python");//在索引为3的元素那里添加Python

System.out.println(list);//[Java, Css, HTML, Python, Java]

// 2、根据索引删除数据。remove(索引)

list.remove(4);// 索引为4的元素删除Java

System.out.println(list);

// 3、修改某个索引位置处的数据 set(索引,修改后的数据)

list.set(2, "JavaScript");// 索引为2的元素修改为JavaScript

System.out.println(list);//[Java, Css, JavaScript, Python, Java]

}

这里我们修改索引为2的元素修改为JavaScript，这里索引为2的元素是HTML，所以HTML会被替换成JavaScript，然后打印数组

运行结果

2.5 E get(int index)——返回指定索引处的元素

public static void main(String[] args) {

// 目标：掌握List系列集合独有的功能。

//1. 声明List集合

List list = new ArrayList<>(); // 多态 一行经典代码

//2. 添加元素

list.add("Java");

list.add("Css");

list.add("HTML");

list.add("Java");

list.add("Java");

//3. 打印原始数据

System.out.println(list); // [Java, Css, HTML, Java, Java]

// // 1、插入数据到指定索引。add(索引,元素)

list.add(3, "Python");//在索引为3的元素那里添加Python

System.out.println(list);//[Java, Css, HTML, Python, Java]

// 2、根据索引删除数据。remove(索引)

list.remove(4);// 索引为4的元素删除Java

System.out.println(list);

// 3、修改某个索引位置处的数据 set(索引,修改后的数据)

list.set(2, "JavaScript");// 索引为2的元素修改为JavaScript

System.out.println(list);//[Java, Css, JavaScript, Python, Java]

// 4、根据索引取数据。get(索引)

System.out.println(list.get(1));// 获取索引为1的元素Css

}

这里我们获取索引为1的元素，这里索引为1的元素是CSS，然后打印元素

运行结果

三、 ArrarList集合底层原理

ArrayList是List接口的实现类，它也是一个泛型，ArrayList的特点也是有序，可重复，有索引。ArrayList底层是基于数组存储数据的。在内存空间是连续存储的。数组中每个元素的地址空间是一样，因此可以通过地址值和索引定位要查询的元素(注意：是根据索引查询数据快)。查询任意数据耗时相同，但是增删数据效率低，因为增加数据时，后面很多元素需要往后移，删除数据时，后面很多元素需要往前移

3.1 ArrarList扩容机制（重点）

刚刚我们讲到，ArrayList它的底层就是一个数组，那么数组就应该有个初始大小，而且它只能存储一定量的数据，但我们又说它是一个集合，它可以无限制（不爆参情况）添加元素，那么它必定是可以扩容的，我们来看看它的扩容机制是什么

第一步，获取ArrarList对象

List list1 = new ArrayList<>();

第二步，按住ctrl+鼠标点击ArrayList，进入它的源码

这里可以看到，它是对elementData进行一个赋值，而elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA分别代表着什么呢，我们接着往下看，按住ctrl+鼠标点击elementData

这里我们可以看到，它初始化的这两个值，分别一个是空元素，另一个是一个数组，所以我们这里可以得到一个结论，就是我们初始化ArrayList的那一刻，它的数组长度大小是0

那我们添加完第一个元素的时候，它的大小会是多少呢，我们来看看它提高添加元素add方法的源码

List list1 = new ArrayList<>();

list1.add("Python");

这里同理，按住ctrl + 鼠标点击add方法，进入它的源码，并找到它的实现类

这里我们可以看到，它首先是对modCount遍历进行累加，这个我们上一章节有说过，其实是有一个方法对它和expectedModCount判断是否相等来抛出异常的，感兴趣可以看看我上一章节《集合框架-Collection》，这里就不用管它。它实质就是调用add方法来添加我们的元素，这里需要传三个参数，第一个是我们的元素，第二个是它的数组，第三个是size，它其实是来获取数组的初始化大小的，我们可以按住ctrl+鼠标点击来查看它

这里只是初始化了它，并没有对它进行赋值，所以它这里的就是0。好的，接下来我们继续进入到add方法里面，按住ctrl+鼠标点击add方法

可以看到这个add方法先会对s的值和数组elementData的长度进行比较，这里的话，我们知道s是0，然后数组的长度也是0，所以这个条件是成立的，会进入到它的grow方法里面进行

这里做了自增，然后继续进入到grow方法，我们接着往下看

这里我们看到，它首先是新建了个临时oldCapacity赋值elementData数组的长度给它，它的初始值就是0，然后接着判断，oldCapacity>0是不成立的，然后DEFAULTCAPACITY_EMPTY_ELEMENTDATA默认也是空（按住ctrl+鼠标悬停可以发现），所以elementData是等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以这个判断条件是不成立的，会进行到它的else分支，这里会新建了object数组，大小是取DEFAULT_CAPACITY和minCapacity之间的最大值，我们知道minCapacity其实就是1，DEFAULT_CAPACITY默认值是10，所以这里会取到10作为object数组的长度并重新赋值给elementData数组，最终我们得出一个结论，就是ArrayList数组第一遍扩容，它的大小是10

讲完了它的第一遍扩容，我们知道它的首次扩容后，它的数组长度是10，那么，当我们元素达到临界点的时候，添加第11个元素时，它的扩容又是怎么样的呢？我们继续往下看

还是老套路，我们进入到它的add方法

当我们添加第11个元素时，此时它的size大小会是10，elementData数组长度也是10，会继续进入到它的grow方法

这里我们可以发现，

minCapacity就是我们自增后的size，这里是11，oldCapacity取了数组的长度，这里是10，然后接着判断，oldCapacity是大于0的，所以成立，elementData不等于空，也是成立的，则会调用到newLength扩容方法，这里传了三个参数，第一个就是oldCapacity，这里就是10，第二个是minCapacity - oldCapacity，用11-10得出是1，第三个参数是oldCapacity右移了一位，我们计算出是5，我们接着进入到newLength方法

这里首先是把参数传了进来，由上一步我们知道oldLength是10，minGrowth是1，prefGrowth是5，所以它这里做了oldLength + minGrowth和prefGrowth取大值，这里是取到了5，所以合并起来就是15，然后它会判断这个扩容后的值是否大于21亿，这里明显是没有大于，所以给他正常返回。所以我们这里得到一个结论，就是第二次扩容，它的扩容长度是15，是原来的1.5倍

我们刚刚看了ArrayList结合的源码，可以明确的知道，在ArratList初始化时，它的长度是0，第一次添加元素时，它会进行首次扩容，长度是10，当达到第二次扩容条件是，也就是第11个元素时，它的扩容会是原来的1.5倍，在之后的扩容当作，如果集合长度达到了SOFT_MAX_ARRAY_LENGTH，那么它就不会是1.5倍扩容，而是做另外的处理，这里的话我直接和大家说结论，SOFT_MAX_ARRAY_LENGTH的值是Integer最大值-8的值，当数组长度大于SOFT_MAX_ARRAY_LENGTH时候，它会将原本集合大小加上minGrowth（这里是1），然后判断之后的值是否小于0（这里是爆参了），会抛出"Required array length " + oldLength + " + " + minGrowth + " is too large"异常，如果它的值是小于或等于 SOFT_MAX_ARRAY_LENGTH时会直接返回SOFT_MAX_ARRAY_LENGTH的值作为当前的集合长度，如果继续添加元素，则会是一个元素大小一个元素大小的扩容，直到到达爆参

四、LinkedList底层原理

LinkedList底层是基于双向链表存储结构的，结点在内存中是不连续的，每个结点包含数据值和下一个结点的地址，链表中的数据是一个一个独立的结点组成的，因此，链表查询速度慢，无论查询哪个元素都要从头节点或尾节点开始逐个查找

注意，因为LinkedList它的底层并不是数组，也就没有所谓的扩容机制

得益于LinkedList底层是基于双向链表存储结构的，所以说LinkedList像一串可拆卸的手链，增删珠子只需调整相邻珠子的链接（指针修改），无需动其他节点。所以它链表增删相对快

LinkedList对首尾元素进行增删改查的速度是极快的。为什么这么说呢，我带大家看看LinedList的源码就知道了，首先，新建LinkedList集合

List