一文学懂List附带超详细ArrayList，Vector，LinkedList底层源码解析

以你之姓@ 2024-04-07 14:12 107阅读 0赞

#### 文章目录 ####

*   *   *  1.为什么要用集合
         *  2.认识集合
         *  3. 集合体系
         *  4.Collection接口
         *   *  4.1 Collection接口特点
             *  4.2 Collection接口常用方法
         *  5.List接口
         *   *  5.1 List接口基本介绍
             *  5.2 List的三种遍历方式
             *  List数组如下
             *   *  1.迭代器遍历
                 *  2.增强for
                 *  3.普通for
         *  6. ArrayList
         *   *  6.1 ArrayList特点
             *  6.2 ArrayList常用方法
             *  6.3 ArrayList底层机制
             *  6.4 ArrayList源码分析
         *  7. Vector
         *   *  7.1 Vector特点
             *  7.2 Vector使用注意
             *  7.3 Vector源码解析
         *  8. LinkedList
         *   *  8.1 LinkedList特点
             *  8.2 LinkedList底层机制
             *  8.3 LinkedList源码解读
             *  8.3 LinkedList常用方法
             *  8.4 遍历 LinkedList
             *   *  8.4.1遍历迭代器
                 *  8.4.2 增强for
                 *  8.4.3 普通for
         *  9. 结语

#### 1.为什么要用集合 ####

之前我们保存多个数据使用的都是数组，这有很多的局限性

1.  长度必须直接指定，而且一旦指定，不能更改。
2.  保存的必须为同一类型的元素
3.  使用数组进行增加/删除元素十分麻烦，浪费内存空间。

因此Java为我们提供了更方便的数组，**集合**。

#### 2.认识集合 ####

1.  可以动态保存多个对象，使用方便。
2.  提供了一系列方便的操作对象的方法，如add，remove等。
3.  使用集合添加，删除新元素十分便捷。

#### 3. 集合体系 ####

集合分为两组，**单列集合与双列集合**，分别对应Collection和Map，前者以元素形式存储数据，后者以键值对方式存储（key-value）。

![在这里插入图片描述][bb0879f38e1d4671b75e16dac95a5d3e.png]

#### 4.Collection接口 ####

##### 4.1 Collection接口特点 #####

1.  collection实现子类可以存放多个元素，每个元素可以是Object。
2.  Collection的实现类有些可以存放重复元素，有些不可以。
3.  Collection的实现类，有些存放元素是有序的（LIst），有些不是有序（Set）。
4.  Collection接口并没有直接的实现子类，是通过它的子接口Set和List来实现的。

##### 4.2 Collection接口常用方法 #####

这里用List集合演示

List list = new ArrayList();//创建集合对象
    // add:添加单个元素
    list.add("jack");
    list.add(10);//list.add(new Integer(10))
    list.add(true);
    System.out.println("list=" + list);
    // remove:删除指定元素
    list.remove(0);//删除第一个元素
    list.remove(true);//指定删除某个元素
    //contains:查找元素是否存在
    System.out.println(list.contains("jack"));
    // size:获取元素个数
    System.out.println(list.size());//2
    //isEmpty:判断是否为空
    System.out.println(list.isEmpty());//F
    // clear:清空
    list.clear();
    //addAll:添加多个元素，也就是类似两个集合合并
    ArrayList list2 = new ArrayList();
    list2.add("红楼梦");
    list2.add("三国演义");
    list.addAll(list2);
    // containsAll:查找多个元素是否都存在
    System.out.println(list.containsAll(list2));
    // removeAll：删除多个元素
    list.removeAll(list2);

#### 5.List接口 ####

##### 5.1 List接口基本介绍 #####

1.  List接口是Collection接口子接口
2.  List集合类中的元素是**有序的**（添加顺序和取出顺序一致），且可以重复。
3.  List集合类中的每个元素都有其对应的顺序索引，即支持索引。
4.  List容器中的元素都对应一个整数类型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

//1. List 集合类中元素有序(即添加顺序和取出顺序一致)、且可重复 
    List list = new ArrayList();
    list.add("jack");
    list.add("tom");
    list.add("mary");
    list.add("bobo");
    list.add("tom");//可以重复
    //2. List 集合中的每个元素都有其对应的顺序索引，即支持索引，索引是从 0 开始的
    System.out.println(list.get(3));//bobo

##### 5.2 List的三种遍历方式 #####

> ##### List数组如下 #####

List list = new LinkedList();
    list.add("jack");
    list.add("tom");
    list.add("mary");
    list.add("lucy");

###### 1.迭代器遍历 ######

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

###### 2.增强for ######

for (Object o : list) {
        
    	System.out.println("o=" + o);
    }

###### 3.普通for ######

for (int i = 0; i < list.size(); i++) {
        
    	System.out.println("对象=" + list.get(i));
    }

#### 6. ArrayList ####

##### 6.1 ArrayList特点 #####

1.  ArrayList可以加入null，且可以加入多个。
2.  ArrayList是由数组来实现数据存储的
3.  ArrayList基本等同于Vector，除了 ArrayList是线程不安全的，但执行效率高，多线程情况下，不建议使用 ArrayList

##### 6.2 ArrayList常用方法 #####

List list = new ArrayList();
    list.add("张三");
    list.add("李四");
    // void add(int index, Object ele):在 index 位置插入 ele 元素
    //在 index = 1 的位置插入一个对象
    list.add(1, "可爱的波波");
    // boolean addAll(int index, Collection eles):从 index 位置开始将 eles 中的所有元素添加进来
    List list2 = new ArrayList();
    list2.add("jack");
    list2.add("tom");
    list.addAll(1, list2);
    System.out.println("list=" + list);
    // Object get(int index):获取指定 index 位置的元素
    //说过
    // int indexOf(Object obj):返回 obj 在集合中首次出现的位置
    System.out.println(list.indexOf("tom"));//2
    // int lastIndexOf(Object obj):返回 obj 在当前集合中末次出现的位置
    list.add("可爱的波波");
    System.out.println(list.lastIndexOf("可爱的波波"));
    // Object remove(int index):移除指定 index 位置的元素，并返回此元素
    list.remove(0);
    // Object set(int index, Object ele):设置指定 index 位置的元素为 ele , 相当于是替换. list.set(1, "玛丽");
    System.out.println("list=" + list);
    // List subList(int fromIndex, int toIndex):返回从 fromIndex 到 toIndex 位置的子集合
    // 注意返回的子集合 fromIndex <= subList < toIndex
    List returnlist = list.subList(0, 2);
    System.out.println("returnlist=" + returnlist);

##### 6.3 ArrayList底层机制 #####

1.  ArrayList中维护了一个Object类型的数组elementData。
2.  当创建 ArrayList对象时，如果使用的是无参构造器，则初始elementData的容量为0，第一次添加，将其扩容为10，如果 还需要添加，则按elementData的1.5倍扩容。
3.  如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容1.5倍。

##### 6.4 ArrayList源码分析 #####

> 当 ArrayList使用无参构造器时，首先创建的是空的elementData数组

![在这里插入图片描述][22bb2e75bc47448ca75fa07805a9930d.png]

> 加入元素时

![在这里插入图片描述][2b080da02e5040559ec84108dd45d6bb.png]

> 进行扩容

![在这里插入图片描述][b66630b427e74fb6aa24c470fdba8f31.png]

> 判断是否需要扩容

![在这里插入图片描述][f7b78c34f62f4786907a7beb74e9d0c5.png]

> 进一步判断其大小，如果是数组则返回10
> 
> 如果数组大小将大于当前容量，则进行1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1);

![在这里插入图片描述][b02d9bdc9ebc4cd6806a93ac06fd4e12.png]

#### 7. Vector ####

##### 7.1 Vector特点 #####

1.  Vector底层是一个对象数组，Object\[\] elementData;
2.  Vector是线程同步的，即线程安全，Vector的操作方法带有**锁**
3.  在开发中，需要考虑线程安全，则使用Vector，其速度不如ArrayList

##### 7.2 Vector使用注意 #####

1.  其中方法与ArrayList一致
2.  在扩容时按2倍进行扩容

##### 7.3 Vector源码解析 #####

> 与ArrayList类似，Vector使用无参构造时就会拥有10个空间大小  
> ![在这里插入图片描述][0b04a572e3f14b0eae4cc72615c78328.png]

> 先判断是否需要扩容，如果需要扩容则会以2倍大小扩容

![在这里插入图片描述][ab8e2555071a429fbda01ce5ac9a87db.png]

![在这里插入图片描述][b1872f24e67c46aba632336dc2516c8e.png]

#### 8. LinkedList ####

##### 8.1 LinkedList特点 #####

1.  LinkedList底层实现了双向链表和双端队列特点。
2.  可以添加任意元素（元素可以重复），包括null。
3.  线程不安全，没有实现同步。

> 增加元素的原理

![在这里插入图片描述][c7654642c461417699739bd3c3533bcf.png]

##### 8.2 LinkedList底层机制 #####

1.  LinkedList底层维护的是一个双向链表。
2.  LinkedList中维护了两个属性first和last分别指向 首节点和尾节点。
3.  每个结点（Node对象），里面又维护了prev，next，item 三个属性。其中通过prev指向前一个，通过next指向后一个节点 。最终实现双向链表。
4.  LinkedList中元素的添加和删除不是通过数组完成的，效率较高。

##### 8.3 LinkedList源码解读 #####

> 首先通过构造器产生一个大小为0的链表，，并且头尾都指向null

![在这里插入图片描述][d1790fb557c34e2aa6db98a029c2f1d8.png]

> 执行add（）方法

![在这里插入图片描述][0ac4fd3992164869818fb82d8fbea48e.png]

> 关键的节点连接

![在这里插入图片描述][ab8051f70f894e13b562e885a08ac4b3.png]  
![在这里插入图片描述][a263a5d30bc44c6e9938a9dd8ee1924f.png]

![在这里插入图片描述][3bc848efd7f142bc8688a1226ee70647.png]

##### 8.3 LinkedList常用方法 #####

LinkedList linkedList = new LinkedList();
    linkedList.add(1);
    linkedList.add(2);
    linkedList.add(3);
    System.out.println("linkedList=" + linkedList);
    //演示一个删除结点的
    linkedList.remove(); // 这里默认删除的是第一个结点
    linkedList.remove(2);//删除第三个结点，从0开始
    //修改某个结点对象
    linkedList.set(1, 999);
    //得到某个结点对象
    //get(1) 是得到双向链表的第二个对象
    Object o = linkedList.get(1);
    System.out.println(o);//999

##### 8.4 遍历 LinkedList #####

###### 8.4.1遍历迭代器 ######

//因为 LinkedList 是 实现了 List 接口, 遍历方式
    System.out.println("===LinkeList 遍历迭代器====");
    Iterator iterator = linkedList.iterator();
    while (iterator.hasNext()) {
        
    Object next = iterator.next();
    System.out.println("next=" + next);
    }

###### 8.4.2 增强for ######

System.out.println("===LinkeList 遍历增强 for====");
    for (Object o1 : linkedList) {
        
    System.out.println("o1=" + o1);
    }

###### 8.4.3 普通for ######

System.out.println("===LinkeList 遍历普通 for====");
    for (int i = 0; i < linkedList.size(); i++) {
        
    System.out.println(linkedList.get(i));
    }

#### 9. 结语 ####

> **Java集合的应用极其广泛，面试也常问，想完全了解集合的实现，建议还是自己亲手去debug源码追一下，这样的印象最为深刻，map的讲解将会放在下一篇，谢谢观看。**

[bb0879f38e1d4671b75e16dac95a5d3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/06d4f5ea1a4f4b718886779f1d13976d.png
[22bb2e75bc47448ca75fa07805a9930d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/43a23aacce544cef9940f08bf24ee5c7.png
[2b080da02e5040559ec84108dd45d6bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/eb31b9fa47724eff966143e6370b57ab.png
[b66630b427e74fb6aa24c470fdba8f31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/40153cc1f6e94afd955b41415e94954f.png
[f7b78c34f62f4786907a7beb74e9d0c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a125cf59c24041c59ceb156d9dfa575b.png
[b02d9bdc9ebc4cd6806a93ac06fd4e12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9201d51ddf974950b657529a0d45daeb.png
[0b04a572e3f14b0eae4cc72615c78328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ac64ba46064c4da088b8194d6e3d072b.png
[ab8e2555071a429fbda01ce5ac9a87db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4576d95e523743f68399e7b5068ec259.png
[b1872f24e67c46aba632336dc2516c8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/30ca9e0e5d9f4043a9366dfbee1bf22f.png
[c7654642c461417699739bd3c3533bcf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8ddf84883faa4e53b4f32de4852bfb1e.png
[d1790fb557c34e2aa6db98a029c2f1d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ac2f7c68f27c467e8895a275eef49121.png
[0ac4fd3992164869818fb82d8fbea48e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a5bc1ffe83f5432dbb19f34c9d84daf3.png
[ab8051f70f894e13b562e885a08ac4b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/973e590bc96c4beb957fbbb696cd84ba.png
[a263a5d30bc44c6e9938a9dd8ee1924f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/23829370406c42f2b9aa739bd1bcf6ae.png
[3bc848efd7f142bc8688a1226ee70647.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b17dd7900e71441285538f44c622ccd8.png