从源码中学习Java集合中的List集合，详细而透彻，一步到位

零基础学习Java之List集合

概述

List是一个有序集合（也被称为序列）。此接口的用户在列表中的每个元素都被插入的地方有精确的控制。用户可以通过它们的整数索引（在列表中的位置）访问元素，并在列表中搜索元素。 说是List集合，其实只是习惯说法，因为它是Collection接口的一个子接口（Collection有很多的子接口，这是其中三个主要的子接口之一，另外两个后面都会说到），所以Collection接口中定义的方法在List接口中也是可以使用的，另外还根据List的特点，又引入了其他的方法。

List接口的特点：

• 元素是以一种线性方式进行存储的
• 元素存取有序，即元素的存入顺序和取出顺序一致。
• 元素带有索引，通过索引就可以精确的操作集合中的元素（与数组类似）
• 元素可以重复，通过元素的equals方法，来比较是否为重复的元素

List的使用

List的常用方法

基本介绍

这里说的常用方法是指除了实现Collection接口之外的。前面说到List集合中的元素是可以通过索引来操作集合中的元素的，所以List 集合里添加了一些根据索引来操作集合元素的方法。下面对这些方法进行简单介绍：

• void add(iint index, E element)： 在列表中指定的位置上插入指定的元素
• boolean addAll(int index, Collection<? extends E> c)： 将指定的集合中的所有元素插入到指定位置的列表中
• E get(int index)：返回此列表中指定位置的元素
• List subList(int fromIndex, int toIndex)：返回List中一部分对象的集合，即返回的集合是List的子集合，并是以下标索引取值。父集合List以fromIndex开始(包含)，到toIndex结束(不包含)的 部分为返回的子集合
• int indexOf(Object obj)：返回此列表中指定元素的第一个出现的索引，如果此列表不包含元素，返回- 1
• int lastIndexOf(Object obj)：返回此列表中指定元素的最后一个发生的索引，如果此列表不包含元素，返回- 1
• E remove(int index)：移除此列表中指定位置的元素
• E set(int index, E element)：用指定元素替换此列表中指定位置的元素

代码示例

publicclassListDemo{publicstaticvoidmain(String[] args){// 通过List的实现类ArrayList创建List集合对象List<String> list =newArrayList<String>();// 指定位置添加元素
        list.add(0,"jack");
        list.add(1,"rose");    
        list.add(2,"marry");System.out.println(list);// 删除索引位置为2的元素 
        list.remove(2);System.out.println(list);// 指定元素替换此列表中指定位置的元素
        list.set(0,"老王");System.out.println(list);// 获取指定位置元素(也遍历输出下)    for(int i =0;i<list.size();i++){System.out.println(list.get(i));}//还可以使用增强forfor(String string : list){System.out.println(string);}}}

List的实现类

作为一个接口，List的实现类才是我们创建对象时候使用的（上面代码示例里面用到了ArrayList实现类）。在List接口里，有三个常用的实现类：ArrayList、Vector、LinkedList。下面从源码中分析和介绍它们。

ArrayList

ArrayList底层通过数组实现，ArrayList可以随着元素的增加而动态扩容。它是一个数组队列，是Java集合框架中使用最多的一个类，但是它是线程不安全的。

• 特点：以数组的形式进行存储，因此随机访问速度较快，所有它适用于查询
• 缺点：不适用于插入和删除的操作 因为每次操作都需要移动数组中的元素；线程不安全

下面看下ArrayList的源码

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{/**
     * Default initial capacity. 初始化的时候如果没有指定长度的话，使用默认长度10
     */privatestaticfinalint DEFAULT_CAPACITY =10;/**
     * Shared empty array instance used for empty instances. 空数组
     */privatestaticfinalObject[] EMPTY_ELEMENTDATA ={};/**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.  空数组
     */privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={};/**
     * Constructs an empty list with an initial capacity of ten.构造一个初始容量为10
     */publicArrayList(){this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组}publicbooleanadd(E e){//查看当前数组是否够多存一个元素ensureCapacityInternal(size +1);// Increments modCount!!//存入新元素到[size]位置，然后size自增1
        elementData[size++]= e;returntrue;}privatevoidensureCapacityInternal(int minCapacity){ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}privatestaticintcalculateCapacity(Object[] elementData,int minCapacity){//如果当前数组还是空数组if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值returnMath.max(DEFAULT_CAPACITY, minCapacity);}//查看是否需要扩容return minCapacity;}privatevoidensureExplicitCapacity(int minCapacity){
        modCount++;//修改次数加1// 如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容if(minCapacity - elementData.length >0)grow(minCapacity);}privatevoidgrow(int minCapacity){// overflow-conscious codeint oldCapacity = elementData.length;//当前数组容量int newCapacity = oldCapacity +(oldCapacity >>1);//新数组容量是旧数组容量的1.5倍//看旧数组的1.5倍是否够if(newCapacity - minCapacity <0)
            newCapacity = minCapacity;//看旧数组的1.5倍是否超过最大数组限制if(newCapacity - MAX_ARRAY_SIZE >0)
            newCapacity =hugeCapacity(minCapacity);//复制一个新数组
        elementData =Arrays.copyOf(elementData, newCapacity);}publicbooleanremove(Object o){//先找到o在当前ArrayList的数组中的下标//分o是否为空两种情况讨论if(o ==null){for(int index =0; index < size; index++)if(elementData[index]==null){//null值用==比较fastRemove(index);returntrue;}}else{for(int index =0; index < size; index++)if(o.equals(elementData[index])){//非null值用equals比较fastRemove(index);returntrue;}}returnfalse;}privatevoidfastRemove(int index){
        modCount++;//修改次数加1//需要移动的元素个数int numMoved = size - index -1;//如果需要移动元素，就用System.arraycopy移动元素if(numMoved >0)System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
        elementData[--size]=null;// clear to let GC do its work}publicEremove(int index){rangeCheck(index);//检验index是否合法

        modCount++;//修改次数加1//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素E oldValue =elementData(index);//需要移动的元素个数int numMoved = size - index -1;//如果需要移动元素，就用System.arraycopy移动元素if(numMoved >0)System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
        elementData[--size]=null;// clear to let GC do its workreturn oldValue;}publicEset(int index,E element){rangeCheck(index);//检验index是否合法//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素E oldValue =elementData(index);//用element替换[index]位置的元素
        elementData[index]= element;return oldValue;}publicEget(int index){rangeCheck(index);//检验index是否合法returnelementData(index);//返回[index]位置的元素}publicintindexOf(Object o){//分为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;}publicintlastIndexOf(Object o){//分为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;}

从上面的源码中我们可以看到：

• ArrayList 在初始化的时候如果我们没有指定长度的话，它会有一个默认长度10，每次扩容的时候为增加1.5倍
• 然后是ArrayList 的一些常见的方法的源码介绍

Vector

Vector的底层也是通过数组实现，方法与ArrayList基本一致,。但是Vector是线程安全的. 这是因为其加上了 synchronized 关键字, 用来保证线程安全。

• 优点: 以数组的形式进行存储，因此随机访问速度较快，所有它适用于查询；线程安全
• 缺点: 不适用于插入和删除的操作 因为每次操作都需要移动数组中的元素

下面看下Vector的源码

/**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     */publicVector(){this(10);//指定初始容量initialCapacity为10}publicVector(int initialCapacity){this(initialCapacity,0);//指定capacityIncrement增量为0}publicVector(int initialCapacity,int capacityIncrement增量为0){super();//判断了形参初始容量initialCapacity的合法性if(initialCapacity <0)thrownewIllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);//创建了一个Object[]类型的数组this.elementData =newObject[initialCapacity];//默认是10//增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量this.capacityIncrement = capacityIncrement;}//synchronized意味着线程安全的   publicsynchronizedbooleanadd(E e){
        modCount++;//看是否需要扩容ensureCapacityHelper(elementCount +1);//把新的元素存入[elementCount]，存入后，elementCount元素的个数增1
        elementData[elementCount++]= e;returntrue;}privatevoidensureCapacityHelper(int minCapacity){// overflow-conscious code//看是否超过了当前数组的容量if(minCapacity - elementData.length >0)grow(minCapacity);//扩容}privatevoidgrow(int minCapacity){// overflow-conscious codeint oldCapacity = elementData.length;//获取目前数组的长度//如果capacityIncrement增量是0，新容量 = oldCapacity的2倍//如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;int newCapacity = oldCapacity +((capacityIncrement >0)?
                                         capacityIncrement : oldCapacity);//如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacityif(newCapacity - minCapacity <0)
            newCapacity = minCapacity;//如果新容量超过了最大数组限制，那么单独处理if(newCapacity - MAX_ARRAY_SIZE >0)
            newCapacity =hugeCapacity(minCapacity);//把旧数组中的数据复制到新数组中，新数组的长度为newCapacity
        elementData =Arrays.copyOf(elementData, newCapacity);}publicbooleanremove(Object o){returnremoveElement(o);}publicsynchronizedbooleanremoveElement(Object obj){
        modCount++;//查找obj在当前Vector中的下标int i =indexOf(obj);//如果i>=0，说明存在，删除[i]位置的元素if(i >=0){removeElementAt(i);returntrue;}returnfalse;}publicintindexOf(Object o){returnindexOf(o,0);}publicsynchronizedintindexOf(Object o,int index){if(o ==null){//要查找的元素是null值for(int i = index ; i < elementCount ; i++)if(elementData[i]==null)//如果是null值，用==null判断return i;}else{//要查找的元素是非null值for(int i = index ; i < elementCount ; i++)if(o.equals(elementData[i]))//如果是非null值，用equals判断return i;}return-1;}publicsynchronizedvoidremoveElementAt(int index){
        modCount++;//判断下标的合法性if(index >= elementCount){thrownewArrayIndexOutOfBoundsException(index +" >= "+
                                                     elementCount);}elseif(index <0){thrownewArrayIndexOutOfBoundsException(index);}//j是要移动的元素的个数int j = elementCount - index -1;//如果需要移动元素，就调用System.arraycopy进行移动if(j >0){//把index+1位置以及后面的元素往前移动//index+1的位置的元素移动到index位置，依次类推//一共移动j个System.arraycopy(elementData, index +1, elementData, index, j);}//元素的总个数减少
        elementCount--;//将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收
        elementData[elementCount]=null;/* to let gc do its work */}

从上面的源码中我们可以看到：

• Vector在初始化的时候如果我们没有指定长度的话，它会有一个默认长度10，每次扩容的时候为增加2倍
• 然后是Vector的一些常见的方法的源码介绍

LinkedList

LinkedList底层的数据存储结构是链表结构，而且还是一个双向链表，可以实现双向操作。此外，LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用，如peek 、push、pop等方法。

• 优点: 以链表形式进行存储，因此随机访问速度查询慢，增删快。
• 缺点: 线程不安全

下面看一下源码

int size =0;Node<E> first;//记录第一个结点的位置Node<E> last;//记录最后一个结点的位置privatestaticclassNode<E>{E item;//元素数据Node<E> next;//下一个结点Node<E> prev;//前一个结点Node(Node<E> prev,E element,Node<E> next){this.item = element;this.next = next;this.prev = prev;}}publicbooleanadd(E e){linkLast(e);//默认把新元素链接到链表尾部returntrue;}voidlinkLast(E e){finalNode<E> l = last;//用l 记录原来的最后一个结点//创建新结点finalNode<E> newNode =newNode<>(l, e,null);//现在的新结点是最后一个结点了
        last = newNode;//如果l==null，说明原来的链表是空的if(l ==null)//那么新结点同时也是第一个结点
            first = newNode;else//否则把新结点链接到原来的最后一个结点的next中
            l.next = newNode;//元素个数增加
        size++;//修改次数增加
        modCount++;}publicbooleanremove(Object o){//分o是否为空两种情况if(o ==null){//找到o对应的结点xfor(Node<E> x = first; x !=null; x = x.next){if(x.item ==null){unlink(x);//删除x结点returntrue;}}}else{//找到o对应的结点xfor(Node<E> x = first; x !=null; x = x.next){if(o.equals(x.item)){unlink(x);//删除x结点returntrue;}}}returnfalse;}Eunlink(Node<E> x){//x是要被删除的结点// assert x != null;finalE element = x.item;//被删除结点的数据finalNode<E> next = x.next;//被删除结点的下一个结点finalNode<E> prev = x.prev;//被删除结点的上一个结点//如果被删除结点的前面没有结点，说明被删除结点是第一个结点if(prev ==null){//那么被删除结点的下一个结点变为第一个结点
            first = next;}else{//被删除结点不是第一个结点//被删除结点的上一个结点的next指向被删除结点的下一个结点
            prev.next = next;//断开被删除结点与上一个结点的链接
            x.prev =null;//使得GC回收}//如果被删除结点的后面没有结点，说明被删除结点是最后一个结点if(next ==null){//那么被删除结点的上一个结点变为最后一个结点
            last = prev;}else{//被删除结点不是最后一个结点//被删除结点的下一个结点的prev执行被删除结点的上一个结点
            next.prev = prev;//断开被删除结点与下一个结点的连接
            x.next =null;//使得GC回收}//把被删除结点的数据也置空，使得GC回收
        x.item =null;//元素个数减少
        size--;//修改次数增加
        modCount++;//返回被删除结点的数据return element;}

从上面的源码中我们可以看到：

• LinkedList是基于链表的，所以没有扩容方法，默认加入元素是尾部自动扩容
• 然后是LinkedList的一些常见的方法的源码介绍

ArrayList与Vector的区别

它们的底层结构都是数组，我们称为动态数组。

• ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
• 动态数组的扩容机制不同，ArrayList扩容为原来的1.5倍，Vector扩容增加为原来的2倍。
• 数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK1.6及之前的版本也是10，而JDK1.7之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。