前言

声明&＃xff0c;本文用得是jdk1.8

前一篇已经讲了Collection的总览&＃xff1a;Collection总览&＃xff0c;介绍了一些基础知识。

现在这篇主要讲List集合的三个子类&＃xff1a;

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

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

看这篇文章之前最好是有点数据结构的基础&＃xff1a;Java实现单向链表&＃xff0c;栈和队列就是这么简单&＃xff0c;二叉树就这么简单

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

一、ArrayList解析

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

首先&＃xff0c;我们来看一下ArrayList的属性&＃xff1a;

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

1.2构造方法

我们来看看构造方法来印证我们上面说得对不对&＃xff1a;

1.3Add方法

add方法可以说是ArrayList比较重要的方法了&＃xff0c;我们来总览一下&＃xff1a;

1.3.1add(E e)

步骤&＃xff1a;

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

首先&＃xff0c;我们来看看这个方法&＃xff1a;

public boolean add(E e) { ensureCapacityInternal(size &＃43; 1); // Increments modCount!! elementData[size&＃43;&＃43;] &＃61; e; return true; }

该方法很短&＃xff0c;我们可以根据方法名就猜到他是干了什么&＃xff1a;

• 确认list容量&＃xff0c;尝试容量加1&＃xff0c;看看有无必要
• 添加元素

接下来我们来看看这个小容量(&＃43;1)是否满足我们的需求&＃xff1a;

随后调用ensureExplicitCapacity()来确定明确的容量&＃xff0c;我们也来看看这个方法是怎么实现的&＃xff1a;

所以&＃xff0c;接下来看看grow()是怎么实现的~

进去看copyOf()方法&＃xff1a;

到目前为止&＃xff0c;我们就可以知道add(E e)的基本实现了&＃xff1a;

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

1.3.2add(int index, E element)

步骤&＃xff1a;

• 检查角标
• 空间检查&＃xff0c;如果有需要进行扩容
• 插入元素

我们来看看插入的实现&＃xff1a;

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

看到arraycopy()&＃xff0c;我们可以发现&＃xff1a;该方法是由C/C&＃43;&＃43;来编写的&＃xff0c;并不是由Java实现&＃xff1a;

总的来说&＃xff1a;arraycopy()还是比较可靠高效的一个方法。

参考R大回答&＃xff1a;https://www.zhihu.com/question/53749473

1.4 get方法

• 检查角标
• 返回元素

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

1.5 set方法

步骤&＃xff1a;

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

1.6remove方法

步骤&＃xff1a;

• 检查角标
• 删除元素
• 计算出需要移动的个数&＃xff0c;并移动
• 设置为null&＃xff0c;让Gc回收

1.7细节再说明

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

二、Vector与ArrayList区别

Vector是jdk1.2的类了&＃xff0c;比较老旧的一个集合类。

Vector底层也是数组&＃xff0c;与ArrayList最大的区别就是&＃xff1a;同步(线程安全)

Vector是同步的&＃xff0c;我们可以从方法上就可以看得出来~

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

如果想要ArrayList实现同步&＃xff0c;可以使用Collections的方法&＃xff1a;List list &＃61; Collections.synchronizedList(new ArrayList(...));&＃xff0c;就可以实现同步了~

还有另一个区别&＃xff1a;

• ArrayList在底层数组不够用时在原来的基础上扩展0.5倍&＃xff0c;Vector是扩展1倍。、

三、LinkedList解析

LinkedList底层是双向链表~如果对于链表不熟悉的同学可先看看我的单向链表(双向链表的练习我还没做)

理解了单向链表&＃xff0c;双向链表也就不难了。

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

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

3.1构造方法

LinkedList的构造方法有两个&＃xff1a;

3.2add方法

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

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

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

3.3remove方法

实际上就是下面那个图的操作&＃xff1a;

3.4get方法

可以看到get方法实现就两段代码&＃xff1a;

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

我们进去看一下具体的实现是怎么样的&＃xff1a;

3.5set方法

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

public E set(int index, E element) { checkElementIndex(index); Node x &＃61; node(index); E oldVal &＃61; x.item; x.item &＃61; element; return oldVal; }

……LinkedList的方法比ArrayList的方法多太多了&＃xff0c;这里我就不一一说明了。

四、总结

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

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

ArrayList&＃xff1a;

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

LinkedList&＃xff1a;

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

Vector&＃xff1a;

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

总的来说&＃xff1a;查询多用ArrayList&＃xff0c;增删多用LinkedList。

ArrayList增删慢不是绝对的(在数量大的情况下&＃xff0c;已测试)&＃xff1a;

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

但一般来说&＃xff1a;增删多还是用LinkedList&＃xff0c;因为上面的情况是极端的~

原文来源&＃xff1a;https://dwz.cn/R91iTN5B作者&＃xff1a; Java3y