在上一篇文章中，壹哥 给大家分析了ArrayList的底层原理及其扩容机制，这个问题在面试时属于高频考点，大家要仔细看哦。上篇文章链接如下：

高薪程序员&面试题精讲系列32之说说ArrayList的底层原理及扩容机制_一一哥-CSDN博客

面试官在考察ArrayList时，经常会问我们另外2个相关的知识点，那就是LinkedList与Vector，比如他们会经常问我们：

说说ArrayList与LinkedList的区别？

请讲一下LinkedList的底层原理；

ArrayList与Vector的区别有哪些？

.......

所以本文会承接上文，继续给大家讲解另外的两个集合，即LinkedList与Vector，看看这两个集合有哪些特点。 

一. LinkedList

1. LinkedList简介

LinkedList是采用链表的方式来实现List接口的，它本身有自己特定的方法，如: addFirst()、addLast()、getFirst()、removeFirst()等。由于是采用链表实现的，因此在进行添加和删除操作时效率要比ArrayList高，且适合用来实现Stack(堆栈)、Queue(队列)、双端队列这样的数据结构。

接下来我们再来看看LinkedList与List之间的类关系，如下图所示。

从上图中可知，LinkedList继承于AbstractSequentialList，实现了List、Deque等接口，所以它也实现了List接口中所有未实现的方法。

2. LinkedList源码简析

2.1 LinkedList的重要属性

LinkedList中包含3个重要的成员属性：size、first、last。

size：表示双向链表中节点的个数；

first：是一个Node节点类型，从源码的注释中可知，first指向的是双向链表中的第一个节点；

last：也是一个Node节点类型，last指向的是双向链表中的最后一个节点。

2.2 Node的重要属性

其中Node表示双向链表中的每一个节点，这是定义在LinkedList内部的一个内部类，Node包含3个成员变量：prev、next、item。

prev：指向该节点的上一个节点；

next：指向该节点的下一个节点；

item：则是该节点所包含数据内容。

Node源码如下所示：

3. LinkedList的数据结构(重点)

LinkedList集合内部是基于一个双向链表，该链表中的每个元素都会通过对象的引用来记住它的前一个元素和后一个元素，从而将所有的元素彼此连接起来。当插入一个新元素时，只需要修改元素之间的引用关系即可，删除一个节点也是如此。我们可以参考下图：

所以LinkedList集合克服了ArrayList集合在增删元素时效率较低的局限性，但LinkedList集合的查询效率低(不支持随机访问)，比如我们要查询第n个元素，则必须从第一个元素开始，逐一的向后遍历，直到找到第n个元素。

4. LinkedList特点

• LinkedList 是一个实现了 List 接口，继承于AbstractSequentialList的双向链表；
• LinkedList 实现了 Deque 接口，所以可以被当作堆栈、队列或双端队列进行操作；
• LinkedList 实现了Cloneable接口，复写了clone()方法，可以进行克隆操作；
• LinkedList 实现了java.io.Serializable接口，支持序列化，能进行序列化传输；
• LinkedList 是非同步的。

5. LinkedList与ArrayList的区别(重点)

LinkedList与ArrayList的区别，是我们面试时的一个高频问题，经常会被面试官问到。但其实这道题目的难度并不大，主要是以记忆为主，我们可以从以下几个方面进行回答。

1.底层数据结构不同
ArrayList的底层基于可增长的Object[]动态数组，LinkedList的底层基于双向链表。

2.两者性能不同
当我们对集合进行随机的读取操作(get和set操作)时，ArrayList比LinkedList的效率更高。这是因为ArrayList中的每个数据元素都带有下标索引，而LinkedList是线性的数据存储方式，需要从前往后一个一个地移动指针依次查找。

但当对集合进行增加和删除操作(add和remove操作)时，LinkedList比ArrayList的效率更高。这是因为ArrayList是数组，当对其进行增删操作时，需要移动插入/删除点后面所有的数组元素，从而会重新调整索引的顺序进行索引重构，这就会消耗很多的时间。而LinkedList则不用，LinkedList只需要改变插入节点和其前后节点的指向位置关系即可，用不着修改节点的索引，因为每个节点根本就没有索引。

所以ArrayList查询快，增删慢；LinkedList查询慢，增删快。

3.两者的时间、空间复杂度不同

从时间复杂度来说，当我们进行随机访问时，ArrayList可以通过索引快速定位元素位置，时间复杂度可以是O(1)；而LinkedList则需要通过for循环进行查找，时间复杂度最大可能会达到O(n)，虽然现在Java对LinkedList的查找方法做了优化，当index < size / 2时，会从左边开始查找，反之则从右边开始查找，但还是要比ArrayList慢的多。所以ArrayList快于LinkedList。

对于插入/删除操作，ArrayList需要对数组重新排序，而且在数组装满的时候，要将所有的数据通过System.arraycopy()重新装入到一个新的数组中，会移动index后面所有的元素，这个很耗时，时间复杂度可能会达到O(n)；LinkedList只需添加一个新的Entry对象，时间复杂度可以为O(1)，所以LinkedList快于ArrayList。

从空间复杂度来说，LinkedList需要更多的内存，因为ArrayList每个索引的位置上都是实际的数据，而LinkedList每个节点中除了存储数据之外，还有额外存储前后节点的位置信息。

4.使用场景不同

ArrayList适用于经常需要快速的查找的场景下，但不适合进行频繁地增删；LinkedList更适用于经常地进行新增和删除，但查询较少的场景。

5.线程安全性问题

当ArrayList与LinkedList作为非共享变量使用时，比如说是在方法里面的局部变量时，是不会产生线程安全问题的。但当两者作为共享变量使用时，就会有线程安全问题出现。这是因为多线程环境下，多个线程可能会随时对数组和链表进行同时操作，可能会导致数据被覆盖，甚至混乱。这时有可能会产生ConcurrentModificationException异常，表示数组或链表的数据结构在迭代过程中被其它线程修改了。

为了避免出现集合的线程安全问题，我们可以使用Collections#synchronizedList进行解决。Collections#synchronizedList会产生一个List，该List的每个方法都加了synchronized锁，保证了在同一时刻，数组和链表只会被同一个线程所修改。另外我们也可以采用CopyOnWriteArrayList这种并发集合来避免线程安全性问题。

6.两者对null空值的处理策略不同

ArrayList中允许我们添加null值，也允许删除null值。当删除null值时，会从头开始，找到第一个是null的元素进行删除。而LinkedList也允许我们新增和删除null值，但对null值不做特殊校验，直接就删了。

7.两者的最大容量不同

ArrayList的最大容量是Integer的最大值，如果大于这个值，JVM就不会再为数组分配内存空间了。

而LinkedList的底层是双向链表，理论上可以无限大。但在源码定义中，LinkedList的size是int类型(前面源码讲解时有说明)，这也从侧面说明了LinkedList的实际空间，不能超过Integer的最大值，否则可能会造成内存溢出。

二. Vector(了解)

因为现在Vector已经不再推荐使用了，所以这个API仅做了解即可，开发时很少使用。

1. Vector简介

Vector 是一个矢量队列，它是在JDK 1.0版本中就添加的类，继承于AbstractList，实现了List、 RandomAccess、Cloneable这些接口。所以Vector是一个矢量队列，支持相关的添加、删除、修改、遍历等功能。

Vector的类关系如下所示：

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.Vector<E>

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

因为Vector 实现了RandmoAccess接口，具有随机访问的功能，使得List能够快速访问数据元素。在Vector中，我们可以通过元素的序号快速获取某个元素对象，这就是快速随机访问。

但和ArrayList不同的是，Vector中的操作是线程安全的。

2. Vector数据结构(重点)

Vector的数据结构其实和ArrayList差不多，内部包含了3个成员变量：elementData , elementCount， capacityIncrement。

• elementData：表示 Object[]类型的动态数组，它保存了添加到Vector中的每一个数据元素。elementData是个动态数组，如果初始化Vector时，没指定动态数组的>大小，则使用默认大小10。随着Vector中元素的增加，Vector的容量也会动态增长，capacityIncrement是与容量增长相关的增长系数。具体的增长方式，请参考源码分析中的ensureCapacity()函数。
• elementCount：表示动态数组的实际大小。
• capacityIncrement：表示动态数组的增长系数。如果在创建Vector时，指定了capacityIncrement的大小，则每次Vector中动态数组容量增加时，增加的大小都是capacityIncrement。

3. Vector原理概括(重点)

Vector内部是通过一个动态数组来保存数据的。当我们构造Vecotr对象时，如果使用的是默认的构造函数，Vector的默认容量大小是10。

当Vector容量不足以容纳全部元素时，Vector的容量会增加。若capacityIncrement容量增加系数 > 0，则将容量的值增加，否则将容量大小增加一倍，这就是所谓的“容量增加系数”。数组容量扩大后，Vector会使用克隆函数将全部元素克隆到一个新数组中。

三. 结语

最后，壹哥 再把本文的核心内容简单总结梳理一下，以方便各位记忆核心内容。

1. 扩容机制

• ArrayList每次扩容是原来的1.5倍；
• 数组进行扩容时，会将旧数组中得数据元素重新拷贝一份到新的数组中，每次数组容量的增长大于原容量的1.5倍；
• ArrayList扩容的代价是很高的，因此在实际使用时，我们应该尽量避免或者减少扩容的发生，可以在构造ArrayList集合时就尽可能的提前指定集合的初始容量。

2. ArrayList和LinkedList的区别

• ArrayList集合底层是Object[]数组，而LinkedList集合底层是链表。
• ArrayList集合查询数据很快，但是增删数据很慢；LinkedList集合增删数据很快，但是查询数据很慢。
• 但是ArrayList与LinkedList的性能比较，我们还是要看具体情况。如果数据量较少，其实两者效率差不多，没有显著区别。但当数据量较大时，ArrayList就比LinkedList效率高多了。

3. ArrayList和Vector的区别

• ArrayList性能比Vector好，因为Vector是线程安全的一个集合，方法加了同步，所以性能要低于ArrayList，安全性比ArrayList好。
• ArrayList和Vector都是默认自动增长的集合，然而ArrayList到了最大值，每次会增长百分之50，而Vector则增长一倍。
• Vector有一个可以作为栈来用的子类：Stack。栈是一种数据结构，表示只能在数据的一段进行操作，为先进后出的一种实现。Stack是Vector的一个子类，所以它也是线程安全的，性能比较低。

至此，壹哥 就给大家分析了ArrayList与LinkedList的区别、ArrayList与Vector的区别，以及这2种集合的底层原理。码字不易，请给 壹哥 点个赞呗！