【容器源码篇】List容器（LinkedList，ArrayList，Vector的特点）

超、凢脫俗 2024-04-17 06:45 77阅读 0赞

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

*  ⭐容器继承关系
 *   *  ?List容器
     *   *  ?️LinkedList源码解析
         *   *  LinkedList采用双向链表实现的列表
             *  构造函数
             *  获取第一个元素和最后一个元素
             *  移除第一个并返回第一个元素，移除最后一个并返回最后一个元素
             *  remove()方法
             *  add()方法
             *  get()获取元素
             *  遍历
             *  ?三种遍历方式的耗时
         *  ?️ArrayList源码解析
         *   *  ArrayList底层基于数组实现
             *  add()方法
             *  set() 赋值操作
             *  get() 取值操作
             *  remove() 方法
             *  遍历
             *  toArray()
             *  Fail-Fast机制
             *  ?三种遍历方式耗时
         *  ?️Vector

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

## ⭐容器继承关系 ##

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

### ?List容器 ###

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

#### ?️LinkedList源码解析 ####

`双向链表`结构：LinkedList 内部以双向链表的形式存储元素，每个节点包含对前后节点的引用。这种结构使得在链表中插入和删除元素的操作效率较高，因为不需要像数组那样移动大量元素。

`非同步（非线程安全）`：LinkedList 不是线程安全的，如果需要在多线程环境下使用，需要手动进行同步处理，或者考虑使用线程安全的容器类。

`插入和删除效率高`：由于双向链表的特性，对于大量的插入和删除操作，LinkedList 的效率通常比 ArrayList 更高。

`随机访问效率低`：与 ArrayList 不同，LinkedList 的随机访问（根据索引查找元素）效率较低，因为需要从头或尾开始遍历链表，直到找到目标位置。

`空间开销较大`：相比于数组，`链表结构本身会带来一定的额外空间开销`，因为需要存储节点之间的引用关系。

##### LinkedList采用双向链表实现的列表 #####

![在这里插入图片描述][68bd45c6dda14005a824942168b50cda.png]其中Node是私有的内部类  
![在这里插入图片描述][a690adb6e9b5471d87e161c50d50537b.png]

##### 构造函数 #####

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

##### 获取第一个元素和最后一个元素 #####

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

##### 移除第一个并返回第一个元素，移除最后一个并返回最后一个元素 #####

![在这里插入图片描述][e8907c3de6bf484a98efaa3cddacb452.png]unlinkFirst()方法 和 unlinkLast()方法  
![在这里插入图片描述][f523a31a204a46e8afaab005403e92d2.png]

首先获取`第一个节点存储的元素和下一个节点的引用`。  
将当前节点的`item和next置为null，帮助垃圾回收`。（如果不将其引用设为null，尽管该节点已经从链表结构中移除，但由于可能存在其他地方仍持有对该节点的`引用`，导致垃圾回收器无法正确判断其是否可回收）  
更新链表的第一个节点为下一个节点。  
如果下一个节点为空，则更新最后一个节点为null；否则更新下一个节点的prev(前一个)为null。  
减少链表的大小并更新 修改次数(modCount++)。  
返回被删除节点存储的元素。

##### remove()方法 #####

![在这里插入图片描述][c2ca986fd0c44273ba5d83788a8a1e12.png]![在这里插入图片描述][092cb5f3a062496b9320cc4a07c01bd2.png]  
首先保存节点`x存储的元素`、`下一个`节点、`上一个`节点的引用。  
如果节点x没有上一个节点，则说明它是链表的`第一个节点`，将链表的`第一个节点指向下一个节点`。  
如果节点x没有下一个节点，则说明它是链表的`最后一个节点`，将链表的`最后一个节点指向上一个节点`。  
更新节点x的上一个节点和下一个节点的`引用为null。`  
将节点x的元素`引用设置为null`，减少内存占用。  
更新链表的大小和修改次数。  
返回节点x存储的元素。

##### add()方法 #####

![在这里插入图片描述][7f1663f8f6d74724ba2b7c5b123a1f38.png]![在这里插入图片描述][da1bd6ffd8bb4bd5925fea94cc44d713.png]  
首先，函数`获取当前链表的最后一个节点last`。  
创建一个新的节点newNode，将其`值设置为e`，`并将其next指向null`。  
将last指向新节点newNode。  
如果`链表为空（即last为null）`，则将first也指向新节点newNode。  
如果链表不为空，则将last的next指向新节点newNode。

##### get()获取元素 #####

![在这里插入图片描述][77d0f1f1496e4c209558863a955db214.png]![在这里插入图片描述][7b251147df4741409269a9d458eda276.png]  
该函数用于获取链表中指定索引位置的节点。若`索引值小于链表长度的一半`，则从头节点开始遍历，若`索引值大于等于链表长度的一半`，则从尾节点开始遍历，最后返回找到的节点

![在这里插入图片描述][9e8050ddc525443fa41dc8803a22ab83.png]![在这里插入图片描述][0442de1325ab4c22bc0bf27865302e6a.png]![在这里插入图片描述][6f705ccd14f545caabadea15e64c7228.png]

##### 遍历 #####

![在这里插入图片描述][1cf3157f71fe42008b2584f09e3ba407.png]  
![在这里插入图片描述][1564f638bd9543dc800547a2ac96b944.png]

##### ?三种遍历方式的耗时 #####

package List;
    
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class LinkedListDemo {
        
        public static void main(String[] args) {
        
            LinkedList<Integer> list=new LinkedList<>();
            for(int i=0;i<10;i++){
        
                list.add(i);
            }
            System.out.println(list.size());
            list.addFirst(10);
            list.add(3,20);
            list.remove(3);
            LinkedList<Integer>list1=new LinkedList<>();
            for(int i=0;i<100000;i++){
        
                list.add(i);
            }
            traverseByIterator(list);
            traverseByIndex(list);
            traverseByFor(list);
        }
        public static void traverseByIterator(LinkedList<Integer> list){
        
            long start=System.currentTimeMillis();
            Iterator<Integer>iterator=list.iterator();
            while(iterator.hasNext()){
        
                iterator.next();
            }
            long end=System.currentTimeMillis();
            System.out.println("迭代器: "+(end-start));
        }
        public static void traverseByIndex(LinkedList<Integer> list){
        
            long start=System.currentTimeMillis();
            for(int i=0;i<list.size();i++){
        
                list.get(i);
            }
            long end=System.currentTimeMillis();
            System.out.println("随机索引: "+(end-start));
        }
        public static void traverseByFor(LinkedList<Integer> list){
        
            long start=System.currentTimeMillis();
            for(Integer i:list){
        
                i.intValue();
            }
            long end=System.currentTimeMillis();
            System.out.println("for-each: "+(end-start));
        }
    }

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

#### ?️ArrayList源码解析 ####

基于`数组`：ArrayList 内部通过数组来存储元素，可以根据需要自动调整大小。

随机访问效率高：由于基于数组，ArrayList 支持通过索引进行快速的随机访问，获取指定位置的元素效率较高。

`非同步（非线程安全）`：ArrayList 不是线程安全的，如果需要在多线程环境下使用，需要手动进行同步处理，或者考虑使用线程安全的容器类。

插入和删除效率较低：相对于 LinkedList，在中间插入或删除元素的效率较低，因为需要移动后续元素。

空间管理：由于 ArrayList 的底层是数组，数组的大小是固定的，当元素数量超出数组容量时，会触发扩容操作，这时会重新分配一个更大的数组，并将原数组中的元素复制到新数组中。这种机制可能会带来一定的性能开销。

##### ArrayList底层基于数组实现 #####

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

##### add()方法 #####

![在这里插入图片描述][b04a3ea40370452295841df0a62bd8ce.png]![在这里插入图片描述][38b657345a1a437b8a6a69db93628fec.png]  
![在这里插入图片描述][5352c04fb25d4cc78596a7070bc01bda.png]  
![在这里插入图片描述][3bd6341885d140a9aaa8652f5a380d4f.png]![在这里插入图片描述][9af0a4b11edc47509d7c1f62c8d4ddb2.png]

![在这里插入图片描述][8b9fab7b6af046bc915c6a6a5495d96d.png]向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容，扩容操作最终都是通过grow()方法完成的。

##### set() 赋值操作 #####

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

##### get() 取值操作 #####

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

##### remove() 方法 #####

![在这里插入图片描述][2de755dea7ac4220a92b41085ede01b9.png]首先，函数进行索引检查，确保指定的索引在有效范围内，否则抛出IndexOutOfBoundsException异常。  
然后，更新列表的修改次数modCount。  
接着，`获取要移除的元素的值并存储在oldValue变量中`。  
然后，判断`要移除的元素` `后面`还有多少个元素，如果大于0，则使用System.arraycopy方法`将后续元素左移，以填补移除元素后留下的空位。`  
最后，将列表的大小减1，并将最后一个元素置为null，以便垃圾回收器将其回收。  
最后，返回被移除的元素的值oldValue。  
![在这里插入图片描述][3df28a4a49204293b9a4b735fbc28604.png]

##### 遍历 #####

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

##### toArray() #####

![在这里插入图片描述][b3e1c475b3824e14975727b7a04cfead.png]![在这里插入图片描述][15d814d891254a498a11bda681048814.png]

##### Fail-Fast机制 #####

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现，在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

##### ?三种遍历方式耗时 #####

package List;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    
    public class ArrayListDemo {
        
        public static void main(String[] args) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0;i<5;i++){
        
                list.add(i);
            }
            list.add(0); //允许有相同的元素
            list.remove(2);
            list.add(3,9);
    
            //遍历
            ArrayList<Integer>list1=new ArrayList<>();
            for(int i=0;i<100000;i++){
        
                list1.add(i);
            }
            traverseByIterator(list1);
            traverseByIndex(list1);
            traverseByFor(list1);
        }
    
        public static void traverseByIterator(ArrayList<Integer> list) {
        
            long start = System.currentTimeMillis();
            Iterator<Integer> iterator=list.iterator();
            while(iterator.hasNext()){
        
                iterator.next();
            }
            long end = System.currentTimeMillis();
            System.out.println("迭代器 "+(end-start));
        }
        public static void traverseByIndex(ArrayList<Integer> list) {
        
            long start = System.currentTimeMillis();
            for(int i=0;i<list.size();i++){
        
                list.get(i);
            }
            long end = System.currentTimeMillis();
            System.out.println("索引 "+(end-start));
        }
        public static void traverseByFor(ArrayList<Integer> list) {
        
            long start = System.currentTimeMillis();
            for(Integer i:list){
        
                i.toString();
            }
            long end = System.currentTimeMillis();
            System.out.println("for "+(end-start));
        }
    }

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

#### ?️Vector ####

`线程安全`：Vector 是线程安全的，所有方法都使用 synchronized 进行同步，这意味着多个线程可以安全地访问 Vector 的内容而不会出现数据竞争问题。

基于`数组`：Vector 内部同样使用数组来存储元素，可以根据需要自动调整大小。

插入和删除效率较低：与 ArrayList 类似，在中间插入或删除元素的效率较低，因为需要移动后续元素。同时，由于线程安全性的考虑，Vector 的操作可能比 ArrayList 慢一些。

空间管理：Vector 与 ArrayList 一样，在元素数量超出数组容量时，会触发扩容操作，重新分配更大的数组并将原数组中的元素复制到新数组中。

[31f2679668504157ba10b718cc500696.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/97a9b2b54d104264b8823af38d509670.png
[89060d892914434faf465338724c9851.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c970c6f4566c44b09cd67f7ab66c6f2b.png
[67ff1a2b0ff74282966ef5c8cb695a46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6f1dd39e898647fca4f15ec4e84680a8.png
[68bd45c6dda14005a824942168b50cda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/63bd4af9d30b4a9e832c37bff5f5a42c.png
[a690adb6e9b5471d87e161c50d50537b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/8cbe5c3e287146e298a67113f9b582c9.png
[551939ba03d04298a66bf7e7e8214a17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/041cc0db7ec144cd9a39174caca5fb36.png
[b7a55c89747e49eb9bf72b0b518c9215.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/8b4bd0e2f7e74bd291abaa688237ee3d.png
[e8907c3de6bf484a98efaa3cddacb452.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/7f2ac5c82d264b06b48c826d44b316fd.png
[f523a31a204a46e8afaab005403e92d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/2220921336ac45d0a56abe5948d02ed0.png
[c2ca986fd0c44273ba5d83788a8a1e12.png]: https://img-blog.csdnimg.cn/direct/c2ca986fd0c44273ba5d83788a8a1e12.png
[092cb5f3a062496b9320cc4a07c01bd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3fa029990d664ccfa4f17762a21f46c0.png
[7f1663f8f6d74724ba2b7c5b123a1f38.png]: https://img-blog.csdnimg.cn/direct/7f1663f8f6d74724ba2b7c5b123a1f38.png
[da1bd6ffd8bb4bd5925fea94cc44d713.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/888c8ea6556d413bb9f048afaa13c17e.png
[77d0f1f1496e4c209558863a955db214.png]: https://img-blog.csdnimg.cn/direct/77d0f1f1496e4c209558863a955db214.png
[7b251147df4741409269a9d458eda276.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/bd432086f6ef4baf995c4400eabe2e42.png
[9e8050ddc525443fa41dc8803a22ab83.png]: https://img-blog.csdnimg.cn/direct/9e8050ddc525443fa41dc8803a22ab83.png
[0442de1325ab4c22bc0bf27865302e6a.png]: https://img-blog.csdnimg.cn/direct/0442de1325ab4c22bc0bf27865302e6a.png
[6f705ccd14f545caabadea15e64c7228.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/2b0047f18e3d4d7489386cabf829b70e.png
[1cf3157f71fe42008b2584f09e3ba407.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0d7152471fb34108bda20698f4b2b40f.png
[1564f638bd9543dc800547a2ac96b944.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/22a84e2e7b8e41f8b460ab4bc75474a9.png
[d9846cb7eeaf487eaad7f19005fbb2c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/cfb6de5dc8054b01bb184e858694e6b1.png
[d7e6fd23adba4736916e8aa598e918db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6a173ff4e2594ea688151ce296901d7c.png
[b04a3ea40370452295841df0a62bd8ce.png]: https://img-blog.csdnimg.cn/direct/b04a3ea40370452295841df0a62bd8ce.png
[38b657345a1a437b8a6a69db93628fec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/66908015005e47dc9ba032d2595543b1.png
[5352c04fb25d4cc78596a7070bc01bda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/58105cee26284aa0af6e0d2523051db6.png
[3bd6341885d140a9aaa8652f5a380d4f.png]: https://img-blog.csdnimg.cn/direct/3bd6341885d140a9aaa8652f5a380d4f.png
[9af0a4b11edc47509d7c1f62c8d4ddb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/907391cfbcdb48bdbf441db2eac769fc.png
[8b9fab7b6af046bc915c6a6a5495d96d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3a280aee559943b6a200eebe0e2b7144.png
[cec89b30a08842f68a40621f69bdb176.png]: https://img-blog.csdnimg.cn/direct/cec89b30a08842f68a40621f69bdb176.png
[cf3d361c2672449c8f60458b20982e8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4ec5b9f892cb4ab690cc5969e6545fa4.png
[fc33e253580a470089116842bc7f0d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/734539aee7a4477eb701b238dc7093ac.png
[d388b72a6dd443d48c88376a66c693fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/cc8a7da839cf4c669aa4dda77d987fec.png
[2de755dea7ac4220a92b41085ede01b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/a4fcf84926fb424bb2766a4a5cb4d675.png
[3df28a4a49204293b9a4b735fbc28604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4f61cf1522ad4a8d9a5a9921b7031f4c.png
[d918bc4ee85b419dae5d4b480e008619.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/f440dc43d16741ea82e522c3cfbf512d.png
[b3e1c475b3824e14975727b7a04cfead.png]: https://img-blog.csdnimg.cn/direct/b3e1c475b3824e14975727b7a04cfead.png
[15d814d891254a498a11bda681048814.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/02fe198414ef40b885522ab3525653a1.png
[aa9f709d85094369bed0c876f11e31a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3c76680346fb421d80ba24fd16cb8e75.png