java之List集合----ArrayList、LinkedList、Vector详解（底层源码分析+常见面试题）
前言
Java集合就像是一个容器，用来存放java对象。在java.util包中提供了一些集合，常用的有List、Set、Map。本章内容会详细介绍List接口及其三大实现类的使用及特点，并给出相关实际面试题进行分析，通过阅读本文，再看这些面试题也是十分简单了。
常用集合继承关系如图所示：
一、Collection接口
Collection接口是List接口和Set接口的父接口，通常情况下不被直接使用，不过Collection接口定义了一些通用方法，通过这些方法可以实现对集合的基本操作，因为List接口实现了Collection接口，所以这些方法对List集合和Set集合是通用的。
二、List集合
List集合为列表类型，列表主要特征是以线性方式存储对象
List接口常用实现类有ArrayList、LinkedList和Vector
2.1 List接口定义的常用方法及功能
| 方法名称 | 功能简介 |
|---|---|
| add(int index, Object obj) | 用来向集合的指定索引位置添加对象，其他对象索引位置从0开始的索引位置相对后移一位。 |
| addAll(int, Collection coll) | 用来向集合的指定索引位置添加指定集合中的所有对象 |
| remove(int index) | 用来清除集合中指定索引位置的对象 |
| set(int index, Object obj) | 用来将集合中指定索引位置的对象修改为指定的对象 |
| get(int index) | 用来获得指定索引位置的对象 |
| indexOf(Object obj) | 用来获得指定对象的索引位置。当存在多个时，返回第一个的索引位置；当不存在时，返回-1 |
| lastIndexOf(Object obj) | 用来获得指定对象的索引位置。当存在多个时，返回最后一个的索引位置；当不存在时，返回-1 |
| listIterator() | 用来获得一个包含所有对象的ListIterator型实例 |
| listIterator(int index) | 用来获得一个包含从指定索引位置到最后的ListIterator型实例 |
| subList(int fromIndex, int toIndex) | 通过截取从起始索引位置fromIndex(包含)到终止索引位置toIndex(不包含)的对象，重新生成一个List集合并返回 |
2.2 三种遍历List集合的方式
/*
* ArrayList三种遍历方式
* */
public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("苹果");
list.add("香蕉");
list.add("菠萝");
//第一种:for循环遍历
for (int i = 0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
System.out.println();
//第二种:foreach-增强for循环
for (String s : list){
System.out.print(s+" ");
}
System.out.println();
//第三种:Iterator-迭代器遍历
Iterator<String> it = list.iterator();
while (it.hasNext()){
System.out.print(it.next()+" ");
}
}
}
运行结果：
苹果 苹果 菠萝
苹果 苹果 菠萝
苹果 苹果 菠萝
那么这三种遍历方式如何选取呢，请往下看
2.3 三种遍历List集合的区别
(1)for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。
(2)迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。
(3)foreach循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。
2.4 RandomAccess接口
为什么要讲这个接口呢？你会发现ArrayList实现了这个接口，而LinkedList却没有↓
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
官方对这个接口的解释是：List实现使用的标记接口表明它们支持快速（通常是恒定时间）随机访问。 此接口的主要目的是允许通用算法在应用于随机或顺序访问列表时改变其行为以提供良好的性能。
用于操作随机访问列表（例如ArrayList）的最佳算法在应用于顺序访问列表（例如LinkedList）时会产生二次行为。 鼓励通用列表算法在应用算法之前检查给定列表是否是此接口的实例，如果将其应用于顺序访问列表会提供较差的性能，并在必要时更改其行为以保证可接受的性能。
众所周知，随机访问和顺序访问之间的区别通常是模糊的。 例如，如果某些List实现变得很大，则提供渐近线性访问时间，但在实践中访问时间是恒定的。 这样的List实现一般应该实现这个接口。 根据经验，如果对于类的典型实例，如果出现以下循环，则List实现应该实现此接口：
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
运行速度比这个循环快：
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
也就是说，
（1）实现了该接口，如ArrayList，建议用for循环遍历列表
（2）没有实现该接口，如LinkedList，表示不支持 Random Access，不建议使用for循环，因为链式结构LinkedList，for基于下标访问会每次从头查询，而foreach循环使用指针直接偏移的高效的地址运算，效率会高非常多。
三、ArrayList类
ArrayList类实现了List接口，内部是采用数组的形式存储对象，所以它有以下特点：
①查找快。底层是数组结构，内存是连续的空间，这意味着，当用get(index)的时候，可以根据数组的（首地址+偏移量），直接计算出想访问的第index个元素在内存中的位置，从而实现对集合元素的随机访问。
②增删较慢。因为它实现增删操作，会同时将索引位置及之后的所有对象相应地前移或后移一位。
3.1 ArrayList存储方式
ArrList底层的存储方式是数组，访问方式是通过下标访问的。所以它查询效率高，增删效率低（对比LinkedList）
底层源码如下：
/**
* 默认初始容量为10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例。 我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
从源码中可以看出
①ArrayList默认初始容量为10
②ArrayList底部存储的方式是数组
另外：EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别是：无参构造函数的空数组会用DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值，有参构造函数的空数组会用EMPTY_ELEMENTDATA赋值（下面有实例）
3.2 ArrayList构造函数
ArrayList构造函数一共有三种形式
第一种：带参构造
/**
* 构造一个具有指定初始容量的空列表
*
* 参数：initialCapacity - 列表的初始容量
* 抛出：IllegalArgumentException – 如果指定的初始容量为负
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; //如果参数>0，初始化指定大小容量
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; //参数等于0，默认空数组
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity); //抛异常
}
}
从源码中可以看出，有参构造方法根据用户传入的参数来给定数组的初始容量
第二种：无参构造
/**
* 构造一个初始容量为 10 的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //返回空数组
}
很多人看到这里会疑问，注解说的是初始化容量为10的空列表，可这里明明把DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋给了elementData(存储 ArrayList 元素的数组缓冲区,ArrayList 的容量就是这个数组缓冲区的长度)，而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object[]，长度为什么会是10呢？这里留个悬念，我们留到接下来ArrayList扩容机制里会详细解答！！！嘿嘿
第三种：构造一个包含指定 collection 的元素的列表
/**
* 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的
* 参数：c – 其元素要放入此列表的集合
* 抛出：NullPointerException – 如果指定的集合为空
*/
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray(); //把指定集合放到Object对象数组中
if ((size = a.length) != 0) { //集合大小不为空
if (c.getClass() == ArrayList.class) { //class对象类型和ArrayList类型一样
elementData = a; //数据传给elementData数组里，elementData是存储 ArrayList 元素的数组缓冲区
} else {
//因为有些to.Array()方法不会返回Object类型，如果类型不一样，就要把这个集合类型强转为Object类型
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 替换为空数组
elementData = EMPTY_ELEMENTDATA;
}
}
简单的说就是把指定Collection元素放进ArrayList里，如果类型不一，就要进行转换
3.3 ArrayList主要方法
（1）indexOf()
作用：查找列表中第一次出现该元素的索引
/**
返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。 更正式地说，返回满足(o==null ? get(i)==null : o.equals(get(i)))的最低索引i ，如果没有这样的索引，则返回 -1。
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
不难，o不为空的时候遍历数组，找到第一个等于o的下标为i的元素
（2）lastIndexOf()
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
其实就是换了个方向遍历，从数组最后开始遍历
（3）toArray()
看源码会发现，ArrayList中有两个toArray()方法，他们之间有什么区别呢？
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
很显然，一个带参一个不带参。
1）共同点是，都以正确的顺序（从第一个元素到最后一个元素）返回包含此列表中所有元素的数组。
2）不同点是，不带参返回的是Object类型；带参返回的是指定数组的运行时类型，如果列表适合指定的数组，则在其中返回。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。要注意的是public <T> T[] toArray(T[] a)会抛出ArrayStoreException异常——如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类
（4）add()
add方法是集合添加元素要用到的，所以比较重要，有两种add方式，一种是带参的，一种是带两个参的，让我们一起来分析下
/**
* 将指定元素附加到此列表的末尾
*
* 参数：e – 要附加到此列表的元素
* 返回：true （由Collection.add指定）
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; //元素放进ArrayList缓冲数组中
return true;
}
/**
* 在此列表中的指定位置插入指定元素。 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）。
*
* 参数：index – 要插入指定元素的索引
* element - 要插入的元素
* 抛出：IndexOutOfBoundsException –
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
显而易见，两种带参的add方法区别在于一个是添加到列表末尾，一个是添加到指定位置，也就是插入，插入动态过程如图所示：
从中可以看出，插入一个元素后，后面的所有元素要进行后移操作。后移实际上就是调用System.arraycopy方法实现自身覆盖。
仔细发现，这两种add方法中都调用了ensureCapacityInternal()方法，其实这个方法的作用就是用来检查是否需要扩容的，也就是为什么之前说初始化数组默认为10，就是通过这里来实现的（见扩容机制详解）
（5）remove()
remove()方式用于列表元素的删除，它的实现方法是通过拿到索引位置，找到指定元素删除，也有如下两种删除方法
/**
* 移除此列表中指定位置的元素。 将任何后续元素向左移动（从它们的索引中减去 1） *
*
* 参数：index - 要删除的元素的索引
* 回报：从列表中删除的元素
* 抛出：IndexOutOfBoundsException –
*/
public E remove(int index) {
rangeCheck(index); //查看索引是否在size范围内
modCount++; //结构性修改次数+1
E oldValue = elementData(index); //oldValue-要删除的元素
int numMoved = size - index - 1; //删除索引位置元素其后面元素需要移动的次数
if (numMoved > 0)
//源数组在指定位置上自我复制，参数（源数组，源数组起始位置，目标数组，目标数组起始位置，复制长度）
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 从此列表中删除第一次出现的指定元素（如果存在）。 如果列表不包含该元素，则它不变。 更正式地说，删除具有最低索引i的元素，使得(o==null ? get(i)==null : o.equals(get(i))) （如果存在这样的元素） get(i)==null : o.equals(get(i)))</tt>
* 如果此列表包含指定的元素（或等效地，如果此列表因调用而更改），则返回true
*
* 参数：o – 要从此列表中删除的元素（如果存在
* 回报：如果此列表包含指定元素，则为true
*/
public boolean remove(Object o) {
//o不存在时，不变
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//o存在，调用fastRemove方法删除元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
与add()方法相反，remove()动态删除如图所示：
第一种remove()方法，从图中可以看出，删除一个元素，后面的所有元素要进行前移操作，这个前移操作是通过自身复制(覆盖)来实现的，用的是System.arraycopy，所以说ArrayList的增删会慢，因为要不断的进行copy操作。
第二种remove方法，返回的类型是boolean型，找到元素直接调用fastRemove()方法删除，fastRemove()和第一种remove()原理相似，它没有返回类型。第二种remove方法需要注意的是它是删除第一个出现的指定元素（如果存在的话）。我特地测试了一下，如下
public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("苹果");
list.add("苹果");
list.add("菠萝");
list.remove("苹果");
for (int i = 0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
输出结果：苹果 菠萝
确实只删除了第一个出现的指定元素，那么如果要删除内容相同的所有元素要怎么进行呢？
public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("苹果");
list.add("苹果");
list.add("菠萝");
Iterator<String> it = list.iterator();
while(it.hasNext()){
String e = it.next();
if(e.equals("苹果")){
it.remove();
}
}
for (int i = 0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
输出结果：菠萝
循环遍历数组删除即可
3.3 ArrayList扩容机制
终于要揭晓为什么空列表private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
的初始化容量为10了！！
让我们看看elementData的官方定义
意思是：数组elementData是存储ArrayList元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。重点：当添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY=10。
也就是说，在添加元素的时候，如果是空列表，其容量都会扩容到10！
具体是怎么实现的，请往下看。顺便了解ArrayList扩容机制。
1）第一步，回顾之前在add方法中，调用的ensureCapacityInternal方法。因为空列表初始size为0，所以此时minCapacity为size+1=1。
/**
* 查看是否需要扩容
* minCapacity – 所需的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
2）第二步，调用calculateCapacity方法，若创建ArrayList时调用的是无参构造，那么就在10和minCapacity中返回一个最大值，在这里，该方法直接返回了10
/**
* 判断是否为无参构造，并返回minCapacity值
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
3）第三步，调用ensureExplicitCapacity方法，这里是重点，涉及到了扩容。当minCapacity - elementData.length > 0，会调用grow(minCapacity)，因为之前说过无参构造默认容量为10，我们不方大胆猜测grow就是实际进行扩容的操作。此时满足条件10 - 0 > 0，调用grow方法。
/**
* 最终判断是否需要扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //列表在结构上被修改次数增加
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
4）再来看grow方法执行过程，来验证下之前的猜测。见代码详细注解
/**
* 要分配的数组的最大大小。 一些 VM 在数组中保留一些标题字。 尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超过 VM 限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 增加容量以确保它至少可以容纳最小容量参数指定的元素数量
*
* 参数：minCapacity – 所需的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组的大小为原来的1.5倍
if (newCapacity - minCapacity < 0) //如果新容量小于所小需要容量，就把最小需要容量当做新数组容量
newCapacity = minCapacity;
//如果新容量大于ArrayList定义的最大容量，就调用hugeCapacity()来
//比较minCapacity和MAX_ARRAY_SIZE，如果minCapacity大于MAX_ARRAY_SIZE，
//则新容量则为Interger.MAX_VALUE(一个保持int可以具有的最大值的常数，2^31-1)
//否则，新容量大小则为MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
最后调用Arrays.copyOf方法使原数组转变为长度更大的新数组，至此，完成扩容操作。
四、LinkedList类
LinkedList类实现了List接口，内部是采用链表结构（JDK1.6之前是双向循环链表、JDK1.7之后取消了循环）存储对象，所以它有以下特点：
①查找慢。底层是一个由相互引用的节点组成的双向链表，在内存中不是一个连续的存储空间。所以在查找的时候会根据index值选择遍历方向，指针要一个个移动来查找，速度较慢。
②增删较快。因为插入和删除对象时，只需要简单地修改链接位置就可以实现，不需要修改其他元素。
LinkedList相比ArrayList，它多实现了一个Deque接口，意味着LinkedList支持两端元素插入和移除的线性集合
4.1 LinkedList存储方式
LinkedList底层的存储方式是双向链表，链表中的每个节点都包含了对前一个和后一个元素的引用。如图所示：
LinkedList有最基本的三个属性
size：集合的长度
first：指向第一个节点的指针
last：指向最后一个结点的指针
/**
* 集合的长度，初始为0
*/
transient int size = 0;
/**
* 指向第一个节点的指针
*/
transient Node<E> first;
/**
* 指向最后一个节点的指针
*/
transient Node<E> last;
4.2 LinkedList构造函数
LinkedList一个有两种构造函数，一种是空构造，不带参；另一种是带参构造，作用是初始化链表为已有的Collection类型的列表。
/**
* 构造一个空列表
*/
public LinkedList() {
}
/**
* 按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表
*
* 参数：c – 其元素要放入此列表的集
* 抛出：NullPointerException – 如果指定的集合为空
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
4.3 LinkedList主要方法
（1）get()
为什么说LinkedList相比ArrayList的查询效率低呢，让我们来结合源码一起分析
1）查询链表，调用get(index)方法，查询指定索引位置元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
2）调用checkElementIndex方法，判断参数是否是现有元素的索引，不是则抛出IndexOutOfBoundsException异常
这里需要提一点，LinkedList是双向链表结构，它不用初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好。
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
3）判断索引是否越界这件事做完了之后就要执行return node(index).item这段代码，node(index)方法返回了指定位置结点的信息
/**
* 返回指定元素索引处的（非空）节点。
*/
Node<E> node(int index) {
//index < size/2，从头部开始查询
//index > size/2，从尾部开始查询
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从node方法可以很明显看出，LinkedList查询时，会将index与集合长度size/2进行对比，小于则从前往后遍历，反之从后往前遍历，这是一种优化查询效率的算法，但是如果指定元素在中间位置的话，遍历的次数也会多。所以这是为什么ArrayList查询效率比LinkedList效率高的原因之一。
（2）remove()
LinkedList中删除元素的方法有很多，这里只说下remove方法，有兴趣可以自行去翻翻源码~
remove()实现删除对象步骤如下（学过数据结构双链表可以跳过，思想一样）：
1）第一步，判断元素是否存在，存在时从first指针指的位置往后遍历，如果找到值相同的item值，调用unlink取消非空节点 x 的链接。
/**
* 从此列表中删除第一次出现的指定元素
*
* 参数：o – 要从此列表中删除的元素（如果存在）
* 返回：如果此列表包含指定元素，则为true
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 取消非空节点 x 的链接。
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; //把该节点数据赋给element
final Node<E> next = x.next; //获得下一个节点
final Node<E> prev = x.prev; //获得上一个节点
if (prev == null) { //如果没有上一个节点，意味着删除的是头节点
first = next; //头指针指向下一个节点
} else {
prev.next = next; //不为空，则把上一个节点的next域指向当前节点next域指向的下一个节点(有点绕，请看后面图解。相当于p->next=q->next，学过c数据结构应该懂)
x.prev = null; //把当前节点的prev置空，会被java虚拟机自动回收
}
if (next == null) { //如果是尾节点
last = prev; //尾指针指向前一个节点，意思是把前一个结点变成了尾节点
} else {
next.prev = prev; //不为空，把下一个节点的pre域指向当前节点的上一个节点
x.next = null; //把当前节点的next置空
}
x.item = null; //item也置空
size--; //链表大小-1
modCount++; //修改+1
return element; //返回节点数值
}
现在来结合图例解析，删除双链表中的元素，其内部结构的变化
（3）add()
添加元素的实现方法也有很多，这里分析讲解实现AbstractList接口中的add()方法
/**
* 将指定元素附加到此列表的末尾
* 此方法等效于addLast
*
* 参数：e – 要附加到此列表的元素
* 回报：true （由Collection.add指定）
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 链接 e 作为最后一个元素
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); //建立一个新节点（prev,item,next）
last = newNode; //新节点作为最后一个尾节点
if (l == null)
first = newNode; //如果没有尾节点，也就是空链表
else
l.next = newNode; //有尾节点，则尾节点后插入新节点
size++; //链表大小+1
modCount++; //修改+1
}
这种add方法是直接加载链表末尾的，就不做细谈
请看下一种
/**
* 在此列表中的指定位置插入指定元素。 将当前位于该位置
* 的元素（如果有）和任何后续元素向右移动（将其索引加一）。
*
* 参数：index – 要插入指定元素的索引
* element - 要插入的元素
* 抛出：IndexOutOfBoundsException –
*/
public void add(int index, E element) {
checkPositionIndex(index); //检查越界
if (index == size)
linkLast(element); //如果索引大小和链表大小相同，把元素放到末尾
else
linkBefore(element, node(index)); //反之，插入到链表中
}
/**
* 在非空节点 succ 之前插入元素 e
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; //得到插入目标前一个节点
final Node<E> newNode = new Node<>(pred, e, succ); //在目标节点前创立一个新节点
succ.prev = newNode; //目标节点prev域指向新节点
if (pred == null) //如果目标节点是首节点
first = newNode; //把头指针指向新节点
else
pred.next = newNode; //若不是，则把目标节点的前一个结点的next指向新节点
size++;
modCount++;
}
过程图解如图所示：
图就不再写那么细了，分析思路和remove差不多，作图不易TT
从两个方法add(int index, E element)和add(E e)的代码实现看出，它们都是通过新建一个Node实体，同时指定其prev和next来实现，不同点在于需要调用node(int index)通过传入的index来定位到要插入的位置
五、Vector
Vector不推荐使用，它是线程安全的，因此效率也会低，而且只能在尾部进行插入和删除操作，更加造成效率低。它的底层实现和ArrayList很多地方都是很像的。所以这里就只将其与ArrayList对比进行一下线程安全的说明
5.1 Vector与ArrayList对比
依旧从底层源码来看
（一）Vector线程安全，Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
查看源码会发现，Vector很多实现方法都是加了synchronized ，保证了线程安全性，而ArrayList却没有上锁。
扩展：如何让ArrayList变为线程安全呢？
List list = Collections.synchronizedList(new ArrayList(...));
面试案例1：遍历一个List有哪些不同的方式？
主要的遍历方式主要有三种：
1）for循环遍历：遍历者自己在集合外部维护一个计数器，依次读取每一个位置的元素
2）Iterator遍历：基于顺序存储集合的Iterator可以直接按位置访问数据。基于链式存储集合的Iterator，需要保存当前遍历的位置，然后根据当前位置来向前或者向后移动指针
3）foreach遍历：也就是增强for循环，foreach内部也是采用了Iterator的方式实现，但使用时不需要显示地声明Iterator
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43569.html
面试案例2：三种遍历方式如何选取呢？
在Java集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常用来标记List的实现是否支持RandomAccess。所以在遍历时，可以先判断是否支持RandomAccess
( list instanceof RandomAccess)，如果支持可用for循环遍历，否则建议用Iterator或foreach遍历。
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43569.html
面试案例3：说说ArrayList 的扩容机制？
1、当使用add方法的时候首先调用ensureCapacityInternal方法，传入 size+1进去，检查是否需要扩容
2、如果空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10，获取“默认的容量”和要扩容的大小两者之间的最大值
3、和当前数组长度比较，如果 if (minCapacity - elementData.length > 0)执行grow扩容方法
4、将数组扩容为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
5、检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
6、再检查新容量newCapacity 是否超出了ArrayList所定义的最大容量，若超出了，则调用hugeCapacity()来比较minCapacity和
MAX_ARRAY_SIZE，如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为
MAX_ARRAY_SIZE（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
7.ArrayList 中copy数组的核心就是System.arraycopy方法，将original数组的所有数据复制到copy数组中，这是一个本地方法
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43569.html
面试案例4：Array和ArrayList有何区别？什么时候更适合使用Array？
- Array可以容纳基本类型和对象，而ArrayList只能容纳对象
- Array是指定大小的，ArrayList 的容量是根据需求自动扩展
- ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等
- 如果列表的大小已经指定，大部分情况下是存储和遍历它们可以使用Array 对于基本类型数据，ArrayList 使用自动装箱来减少编码工作量；而当处理固定大小的基本数据类型的时候，这种方式相对比较慢，这时候应该使用Array
如果你要使用多维数组，使用[][]比 List更容易原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43569.html
面试案例5：详细说说 Arraylist 和 LinkedList的区别?
- ArrayList：底层是基于数组实现的，查找快，增删较慢。LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
- LinkedList：底层是基于链表实现的。确切的说是循环双向链表(JDK1.6之前是双向循环链表、JDK1.7之后取消了循环)，查找慢、增删快。LinkedList链表由一系列表项连接而成，一个表项包含3个部分︰元素内容、前驱表和后驱表。因此内存空间占用比ArrayList更多。
面试官追问：ArrayList的增删一定比LinkedList要慢吗？
不一定的。
- 如果增删都是在末尾来操作（每次调用的都是 remove() 和 add()），此时ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时，速度是会比 LinkedList 要快的。
- 如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上，ArrayList的消耗主要是在移动和复制上(底层调用的是arrayCopy()方法，是native方法)。LinkedList的遍历速度是要慢于ArrayList的复制移动速度的。如果数据量有百万级的时，还是ArrayList要快。
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43569.html
面试案例6：说一下 ArrayList 的优缺点
ArrayList的优点如下：
(1)ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess
接口，因此查找的时候非常快。
(2)ArrayList 在顺序添加一个元素的时候非常方便。
ArrayList 的缺点如下：
(1)删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
(2)插入元素的时候，也需要做一次元素复制操作，缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43571.html
面试案例7：如何实现数组和 List 之间的转换？
数组转 List：使用 Arrays. asList(array) 进行转换。
List 转数组：使用 List 自带的 toArray() 方法。
实例代码：
arrayList list = new ArrayList();
list.add(“123”);
list.add(“456”);
list.toArray();
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43571.html
面试案例8：ArrayList 和 Vector 的区别是什么？
这两个类都实现了 List 接口(List 接口继承了 Collection 接口)，他们都是有序集合
(1)线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
(2)性能：ArrayList 在性能方面要优于 Vector。
(3)扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而ArrayList 只会增加 50%。
Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43571.html
面试案例9：插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？
ArrayList、LinkedList、Vector
底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
1）Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较ArrayList差。
2） LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以LinkedList 插入速度较快。
原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43571.html
面试案例10：多线程场景下如何使用 ArrayList？
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList
方法将其转换成线程安全的容器后再使用。例如像下面这样：
ArrayList<String>()); synchronizedList.add("aaa"); synchronizedList.add("bbb"); for (int i = 0;i<synchronizedList.size();i++){ System.out.println(synchronizedList.get(i)); } ``` //原文链接：https://www.cdsy.xyz/computer/programme/java/230513/cd43571.html
面试案例11：为什么 ArrayList 的 elementData 加上 transient 修饰？
ArrayList 中的数组定义如下：
private transient Object[] elementData;
再看一下 ArrayList 的定义：
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable,java.io.Serializable
可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现：
java.io.IOException{ *// Write out element count, and any hidden stuff* int expectedModCount = modCount; s.defaultWriteObject(); *// Write out array length* s.writeInt(elementData.length); *// Write out all elements in the proper order.* for (int i=0; i<size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); }每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历
elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。
湘公网安备 43102202000103号