List 常见实现类源码解析：ArrayList、LinkedList、Vector

尚硅谷JavaSE笔记合集

一、相关面试题

• 比较ArrayList、LinkedList、Vector三者的异同？

/**
 *	相同点：都实现了List接口，存储有序的、可重复的数据
 *
 *	不同点：
 *   ArrayList：作为List的主要实现类，把ArrayList作为缺省选择
 *      - 线程不安全，效率高。
 *      - 作为List的主要实现类，ArrayList()懒汉式(jdk8)创建集合。默认容量为10
 *      - 底层使用数组存储
 *      - 扩容是原来的1.5倍
 *   Vector：
 *      - 线程安全，效率低总是比ArrayList低。尽量避免使用。
 *      - 作为古老的实现类，Vector()饿汉式创建集合。默认容量为10
 *      - 底层使用数组存储
 *      - 扩容是原来的2倍
 *   LinkedList：
 *      - 底层使用双向链表存储
 *		- 对于频繁的插入、删除操作，建议使用LinkedList，效率比ArrayList高。
 *
 */

二、ArrayList 源码分析

• 建议开发中使用带参的构造器，减少扩容次数
• jdk7：ArrayList() --> this.elementData = new Object[initialCapacity]

//==============================以jdk8为例===========================
//1.实例化集合时：创建空数组 --> this.elementData={}
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//2.添加元素时：
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
	//2.1 根据需要的最小容量判断是否需要扩容
	private void ensureCapacityInternal(int minCapacity) {
	    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
	}
		//2.1.1 作用：让空数组进入扩容逻辑
		//如果当前数组为空，返回默认大小10。否则返回数组元素长度
		private static int calculateCapacity(Object[] elementData, int minCapacity) {
		    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		        return Math.max(DEFAULT_CAPACITY, minCapacity);
		    }
		    return minCapacity;
		}
		//2.1.2 作用：扩容
		//如果10-0>0，即还没创建数组则进行数组扩容。如果需要的最小容量-数组大小>0，则进行数组扩容
    	private void ensureExplicitCapacity(int minCapacity) {
    	    modCount++;
    	    if (minCapacity - elementData.length > 0)
    	        grow(minCapacity);
    	}
			//扩容为原来的1.5倍
			private void grow(int minCapacity) {
			    int oldCapacity = elementData.length;
			    int newCapacity = oldCapacity + (oldCapacity >> 1);
                //数组为空时进入：将新容量设置为10
			    if (newCapacity - minCapacity < 0)
			        newCapacity = minCapacity;
                //容量大于可接受范围时进入
			    if (newCapacity - MAX_ARRAY_SIZE > 0)
			        newCapacity = hugeCapacity(minCapacity);
                //使用数组拷贝：将原数组拷贝到新容量的数组中
			    elementData = Arrays.copyOf(elementData, newCapacity);
			}
	//2.2 进行赋值
	elementData[size++] = e;

三、LinkedList 源码分析

/**
  * LinkedList的源码分析：
  *    1.内部声明了Node类型的first和last属性，默认值为null。用于记录首末元素
  *
  *    2.Node定义：作为LinkedList中保存数据的基本结构。体现了LinkedList的双向链表的说法
  *       private static class Node {
  *            E item;
  *            Node next;
  *            Node prev;
  *
  *            Node(Node prev, E element, Node next) {
  *            this.item = element;
  *            this.next = next;     //next变量记录下一个元素的位置
  *            this.prev = prev;     //prev变量记录前一个元素的位置
  *            }
  *        }
  */
//1.实例化集合
public LinkedList() {
}
//2.添加元素
public boolean add(E e) {
    linkLast(e);
    return true;
}
	//2.1 链接到尾部
    void linkLast(E e) {
        //（1）保存尾节点
        final Node<E> l = last;
        //（2）创建新节点：传入尾节点
        //	 2.1 将新节点的prev指针指向尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        //（3）将尾指针指向新节点
        last = newNode;
        //（4）如果一开始链表为空，则将头指针指向头节点
        if (l == null)
            first = newNode;
        //（5）如果链表不为空，将尾节点的next指针指向新节点。新节点成为尾节点
        else
            l.next = newNode;
        size++;
        modCount++;
    }

四、Vector 源码分析

//1.实例化集合：调用一个int型参数的构造器
public Vector() {
    this(10);
}
//2.调用两个int型参数的构造器
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
//3.创建容量为10的Object数组
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
//4.添加元素
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
	//4.1 判断是否需要扩容：如果需要的容量大于当前容量则扩容
	private void ensureCapacityHelper(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
		//扩容
		private void grow(int minCapacity) {
        	int oldCapacity = elementData.length;
            //扩大为原来的两倍
        	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
        	                                 capacityIncrement : oldCapacity);
        	if (newCapacity - minCapacity < 0)
        	    newCapacity = minCapacity;
        	if (newCapacity - MAX_ARRAY_SIZE > 0)
        	    newCapacity = hugeCapacity(minCapacity);
        	elementData = Arrays.copyOf(elementData, newCapacity);
    	}
	//4.2 赋值
	elementData[elementCount++] = e;