List集合就这么简单【源码剖析】

女爷i 2021-09-15 04:44 367阅读 0赞

# 前言 #

> 声明，本文用得是jdk1.8

前一篇已经讲了Collection的总览：[Collection总览][Collection]，介绍了一些基础知识。

现在这篇主要讲List集合的三个子类：

*  ArrayList  
    
    
     *  底层数据结构是数组。线程不安全
 *  LinkedList  
    
    
     *  底层数据结构是链表。线程不安全
 *  Vector  
    
    
     *  底层数据结构是数组。线程安全

这篇主要来看看它们比较重要的方法是如何实现的，需要注意些什么，最后比较一下哪个时候用哪个～

看这篇文章之前最好是有点数据结构的基础：[Java实现单向链表][Java]，[栈和队列就是这么简单][Link 1]，[二叉树就这么简单][Link 2]

![162a47ff8aa0d652_w_1213_h_556_f_bmp_s_2023894][]

![162a47ff8fdf1b62_w_1213_h_556_f_bmp_s_2023894][]

当然了，如果讲得有错的地方还请大家多多包涵并不吝在评论去指正～

# 一、ArrayList解析 #

![162a47ff9010e432_w_987_h_527_f_png_s_19181][]

首先，我们来讲解的是ArrayList集合，它是我们用得非常非常多的一个集合~

首先，我们来看一下ArrayList的属性：

![Iclajir.png][]

根据上面我们可以清晰的发现：**ArrayList底层其实就是一个数组**，ArrayList中有**扩容**这么一个概念，正因为它扩容，所以它能够**实现“动态”增长**

## 1.2构造方法 ##

我们来看看构造方法来印证我们上面说得对不对：

![162a47ff903d247c_w_874_h_717_f_png_s_49435][]

## 1.3Add方法 ##

add方法可以说是ArrayList比较重要的方法了，我们来总览一下：

![162a4842e35deb9b_w_957_h_642_f_png_s_41396][]

### 1.3.1add(E e) ###

步骤：

*  **检查是否需要扩容**
 *  **插入元素**

首先，我们来看看这个方法：

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

该方法很短，我们可以根据方法名就猜到他是干了什么：

*  **确认list容量，尝试容量加1，看看有无必要**
 *  **添加元素**

接下来我们来看看这个小容量(+1)是否满足我们的需求：

![162a47ffce5e519d_w_1048_h_237_f_png_s_16138][]

随后调用`ensureExplicitCapacity()`来确定明确的容量，我们也来看看这个方法是怎么实现的：

![162a47ffdfdce509_w_1111_h_260_f_png_s_22235][]

所以，接下来看看`grow()`是怎么实现的~

![162a47fff99d4ae1_w_1235_h_793_f_png_s_64651][]

进去看`copyOf()`方法：

![162a48001c426601_w_1260_h_290_f_png_s_18128][]

到目前为止，我们就可以知道`add(E e)`的基本实现了：

*  首先去检查一下数组的容量是否足够  
    
    
     *  足够：直接添加
     *  不足够：扩容  
        
        
         *  **扩容到原来的1.5倍**
         *  第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。

### 1.3.2add(int index, E element) ###

步骤：

*  **检查角标**
 *  **空间检查，如果有需要进行扩容**
 *  **插入元素**

我们来看看插入的实现：  
![162a4800231ba6fe_w_1099_h_499_f_png_s_38920][]

我们发现，与扩容相关ArrayList的add方法底层其实都是`arraycopy()`来实现的

看到`arraycopy()`，我们可以发现：**该方法是由C/C++来编写的**，并不是由Java实现：

![162a480046336dd0_w_1024_h_126_f_png_s_8667][]

总的来说：`arraycopy()`还是比较可靠高效的一个方法。

参考R大回答：[https://www.zhihu.com/question/53749473][https_www.zhihu.com_question_53749473]

## 1.4 get方法 ##

*  **检查角标**
 *  **返回元素**

![162a48004fb8e759_w_963_h_337_f_png_s_20381][]

// 检查角标
       private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        // 返回元素
        E elementData(int index) {
            return (E) elementData[index];
        }

## 1.5 set方法 ##

步骤：

*  **检查角标**
 *  **替代元素**
 *  **返回旧值**

![162a47fd7115715d_w_1013_h_453_f_png_s_38341][]

## 1.6remove方法 ##

步骤：

*  **检查角标**
 *  **删除元素**
 *  **计算出需要移动的个数，并移动**
 *  设置为null，让Gc回收

![162a47fd72d05022_w_1163_h_638_f_png_s_35905][]

## 1.7细节再说明 ##

*  ArrayList是**基于动态数组实现的**，在**增删时候，需要数组的拷贝复制**。
 *  **ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍**
 *  删除元素时不会减少容量，**若希望减少容量则调用trimToSize()**
 *  它不是线程安全的。它能存放null值。

![162a47fd7372e624_w_1060_h_378_f_png_s_18257][]

参考资料：

*  [https://blog.csdn.net/panweiwei1994/article/details/76760238][https_blog.csdn.net_panweiwei1994_article_details_76760238]
 *  [https://zhuanlan.zhihu.com/p/27878015][https_zhuanlan.zhihu.com_p_27878015]

# 二、Vector与ArrayList区别 #

Vector是jdk1.2的类了，比较老旧的一个集合类。

![ThBGx1L.png][]

Vector底层也是数组，与ArrayList最大的区别就是：**同步(线程安全)**

Vector是同步的，我们可以从方法上就可以看得出来~

![162a47fd756c6822_w_1768_h_829_f_png_s_116649][]

在要求非同步的情况下，我们一般都是使用ArrayList来替代Vector的了~

如果想要ArrayList实现同步，可以使用Collections的方法：`List list = Collections.synchronizedList(new ArrayList(...));`，就可以实现同步了~

还有另一个区别：

*  **ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。**、

![162a47fd7863dcf9_w_1092_h_292_f_png_s_14770][]

![162a47fdc940ee72_w_1184_h_378_f_png_s_22956][]

Vector源码的解析可参考：

*  [https://blog.csdn.net/panweiwei1994/article/details/76972890][https_blog.csdn.net_panweiwei1994_article_details_76972890]
 *  [https://zhuanlan.zhihu.com/p/28241176][https_zhuanlan.zhihu.com_p_28241176]

# 三、LinkedList解析 #

![162a47fdcc0c1095_w_902_h_565_f_png_s_23073][]

LinkedList底层是**双向链表**~如果对于链表不熟悉的同学可先看看我的**单向链表**(双向链表的练习我还没做)【[Java实现单向链表][Java]】

理解了单向链表，双向链表也就不难了。

![162a47fdcc30ca90_w_1787_h_688_f_png_s_81323][]

从结构上，我们还看到了**LinkedList实现了Deque接口**，因此，我们可以**操作LinkedList像操作队列和栈一样**~

![162a47fde94ebaec_w_580_h_842_f_png_s_53096][]

LinkedList变量就这么几个，因为我们操作单向链表的时候也发现了：有了头结点，其他的数据我们都可以获取得到了。(双向链表也同理)

![cBw4BQp.png][]

## 3.1构造方法 ##

LinkedList的构造方法有两个：

![bu9iEUN.png][]

## 3.2add方法 ##

如果做过链表的练习，对于下面的代码并不陌生的~

*  **add方法实际上就是往链表最后添加元素**

public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

## 3.3remove方法 ##

![162a4842e381e45f_w_873_h_452_f_png_s_23841][]

![4NNKxcg.png][]

实际上就是下面那个图的操作：

![26oDYiF.jpg][]

## 3.4get方法 ##

可以看到get方法实现就两段代码：

public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }

我们进去看一下具体的实现是怎么样的：

![dGMp3ws.png][]

## 3.5set方法 ##

set方法和get方法其实差不多，**根据下标来判断是从头遍历还是从尾遍历**

public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }

--------------------

……LinkedList的方法比ArrayList的方法多太多了，这里我就不一一说明了。具体可参考：

*  [https://blog.csdn.net/panweiwei1994/article/details/77110354][https_blog.csdn.net_panweiwei1994_article_details_77110354]
 *  [https://zhuanlan.zhihu.com/p/24730576][https_zhuanlan.zhihu.com_p_24730576]
 *  [https://zhuanlan.zhihu.com/p/28373321][https_zhuanlan.zhihu.com_p_28373321]

# 四、总结 #

其实集合的源码看起来并不是很困难，遇到问题可以翻一翻，应该是能够看懂的~

ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结：

**ArrayList：**

*  底层实现是数组
 *  ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
 *  在**增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)**

**LinkedList：**

*  底层实现是**双向链表**\[双向链表方便实现往前遍历\]

**Vector：**

*  底层是数组，现在已少用，被ArrayList替代，原因有两个：  
    
    
     *  Vector所有方法都是同步，**有性能损失**。
     *  Vector初始length是10 超过length时 以100%比率增长，**相比于ArrayList更多消耗内存**。
     *  参考资料：[https://www.zhihu.com/question/31948523/answer/113357347][https_www.zhihu.com_question_31948523_answer_113357347]

**总的来说：查询多用ArrayList，增删多用LinkedList。**

**ArrayList增删慢不是绝对**的(**在数量大的情况下，已测试**)：

*  如果增加元素一直是使用`add()`(增加到末尾)的话，那是ArrayList要快
 *  一直**删除末尾的元素也是ArrayList要快**【不用复制移动位置】
 *  至于如果**删除的是中间的位置的话，还是ArrayList要快**！

但一般来说：**增删多还是用LinkedList，因为上面的情况是极端的~**

参考资料：

*  [https://blog.csdn.net/panweiwei1994/article/details/76555359][https_blog.csdn.net_panweiwei1994_article_details_76555359]
 *  [https://zhuanlan.zhihu.com/p/28216267][https_zhuanlan.zhihu.com_p_28216267]
 *  《Core Java》

![Io1X3R2.jpg][]

**文章的目录导航**：[https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li][https_zhongfucheng.bitcron.com_post_shou-ji_gong-zhong-hao-wen-zhang-zheng-li]

> 如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以**关注微信公众号:Java3y**。为了大家方便，刚新建了一下**qq群：742919422**，大家也可以去交流交流。

[Collection]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484122&idx=1&sn=c3bd6436b3e661ae15cb9d7154d82b89&chksm=ebd743dbdca0cacdcb272576f4be48c466bd73160a87227314e8fb21d5e4f9156c23902198ab#rd
[Java]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484086&idx=1&sn=24127ceb5e0fed7f832f82579c4fbc19&chksm=ebd743b7dca0caa1dce912d47251548225aa59b4b48742a963ac52b05e13ec923a738ebcb836#rd
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484090&idx=1&sn=d46205eed74e9b253ec08796124192c1&chksm=ebd743bbdca0caad2129f0d76f002b7e14e125900ecac1fa9a3a433e3a9bcd2831275a1e260c#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484064&idx=1&sn=ba783e3e83b8007fcdf129ec0839b6c2&chksm=ebd743a1dca0cab7eed0ba42d1c5d343d88858c17e90a803e0ce9e6644187e5297b29ffbb020#rd
[162a47ff8aa0d652_w_1213_h_556_f_bmp_s_2023894]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ff8aa0d652?w=1213&h=556&f=bmp&s=2023894
[162a47ff8fdf1b62_w_1213_h_556_f_bmp_s_2023894]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ff8fdf1b62?w=1213&h=556&f=bmp&s=2023894
[162a47ff9010e432_w_987_h_527_f_png_s_19181]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ff9010e432?w=987&h=527&f=png&s=19181
[Iclajir.png]: https://i.imgur.com/Iclajir.png
[162a47ff903d247c_w_874_h_717_f_png_s_49435]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ff903d247c?w=874&h=717&f=png&s=49435
[162a4842e35deb9b_w_957_h_642_f_png_s_41396]: https://user-gold-cdn.xitu.io/2018/4/8/162a4842e35deb9b?w=957&h=642&f=png&s=41396
[162a47ffce5e519d_w_1048_h_237_f_png_s_16138]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ffce5e519d?w=1048&h=237&f=png&s=16138
[162a47ffdfdce509_w_1111_h_260_f_png_s_22235]: https://user-gold-cdn.xitu.io/2018/4/8/162a47ffdfdce509?w=1111&h=260&f=png&s=22235
[162a47fff99d4ae1_w_1235_h_793_f_png_s_64651]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fff99d4ae1?w=1235&h=793&f=png&s=64651
[162a48001c426601_w_1260_h_290_f_png_s_18128]: https://user-gold-cdn.xitu.io/2018/4/8/162a48001c426601?w=1260&h=290&f=png&s=18128
[162a4800231ba6fe_w_1099_h_499_f_png_s_38920]: https://user-gold-cdn.xitu.io/2018/4/8/162a4800231ba6fe?w=1099&h=499&f=png&s=38920
[162a480046336dd0_w_1024_h_126_f_png_s_8667]: https://user-gold-cdn.xitu.io/2018/4/8/162a480046336dd0?w=1024&h=126&f=png&s=8667
[https_www.zhihu.com_question_53749473]: https://www.zhihu.com/question/53749473
[162a48004fb8e759_w_963_h_337_f_png_s_20381]: https://user-gold-cdn.xitu.io/2018/4/8/162a48004fb8e759?w=963&h=337&f=png&s=20381
[162a47fd7115715d_w_1013_h_453_f_png_s_38341]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fd7115715d?w=1013&h=453&f=png&s=38341
[162a47fd72d05022_w_1163_h_638_f_png_s_35905]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fd72d05022?w=1163&h=638&f=png&s=35905
[162a47fd7372e624_w_1060_h_378_f_png_s_18257]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fd7372e624?w=1060&h=378&f=png&s=18257
[https_blog.csdn.net_panweiwei1994_article_details_76760238]: https://blog.csdn.net/panweiwei1994/article/details/76760238
[https_zhuanlan.zhihu.com_p_27878015]: https://zhuanlan.zhihu.com/p/27878015
[ThBGx1L.png]: https://i.imgur.com/ThBGx1L.png
[162a47fd756c6822_w_1768_h_829_f_png_s_116649]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fd756c6822?w=1768&h=829&f=png&s=116649
[162a47fd7863dcf9_w_1092_h_292_f_png_s_14770]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fd7863dcf9?w=1092&h=292&f=png&s=14770
[162a47fdc940ee72_w_1184_h_378_f_png_s_22956]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fdc940ee72?w=1184&h=378&f=png&s=22956
[https_blog.csdn.net_panweiwei1994_article_details_76972890]: https://blog.csdn.net/panweiwei1994/article/details/76972890
[https_zhuanlan.zhihu.com_p_28241176]: https://zhuanlan.zhihu.com/p/28241176
[162a47fdcc0c1095_w_902_h_565_f_png_s_23073]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fdcc0c1095?w=902&h=565&f=png&s=23073
[162a47fdcc30ca90_w_1787_h_688_f_png_s_81323]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fdcc30ca90?w=1787&h=688&f=png&s=81323
[162a47fde94ebaec_w_580_h_842_f_png_s_53096]: https://user-gold-cdn.xitu.io/2018/4/8/162a47fde94ebaec?w=580&h=842&f=png&s=53096
[cBw4BQp.png]: https://i.imgur.com/cBw4BQp.png
[bu9iEUN.png]: https://i.imgur.com/bu9iEUN.png
[162a4842e381e45f_w_873_h_452_f_png_s_23841]: https://user-gold-cdn.xitu.io/2018/4/8/162a4842e381e45f?w=873&h=452&f=png&s=23841
[4NNKxcg.png]: https://i.imgur.com/4NNKxcg.png
[26oDYiF.jpg]: https://i.imgur.com/26oDYiF.jpg
[dGMp3ws.png]: https://i.imgur.com/dGMp3ws.png
[https_blog.csdn.net_panweiwei1994_article_details_77110354]: https://blog.csdn.net/panweiwei1994/article/details/77110354
[https_zhuanlan.zhihu.com_p_24730576]: https://zhuanlan.zhihu.com/p/24730576
[https_zhuanlan.zhihu.com_p_28373321]: https://zhuanlan.zhihu.com/p/28373321
[https_www.zhihu.com_question_31948523_answer_113357347]: https://www.zhihu.com/question/31948523/answer/113357347
[https_blog.csdn.net_panweiwei1994_article_details_76555359]: https://blog.csdn.net/panweiwei1994/article/details/76555359
[https_zhuanlan.zhihu.com_p_28216267]: https://zhuanlan.zhihu.com/p/28216267
[Io1X3R2.jpg]: https://i.imgur.com/Io1X3R2.jpg
[https_zhongfucheng.bitcron.com_post_shou-ji_gong-zhong-hao-wen-zhang-zheng-li]: https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li