文章目录

List相关

List相关

我们从最简单的List开始入手，一步步往下分析。List是一个列表，是一个顺序容器，对容器中对象的get和set都可以在常数级别时间内完成。

1. List接口

List接口如下,这里只分析了一些主要的函数。

public interface List<E> extends Collection<E> {
    // 返回当前列表容器中对象的数量
    int size();
    // 判断容器是否是空的
    boolean isEmpty();
    // 判断容器中是否存在指定对象
    boolean contains(Object o);
    // 返回迭代器
    Iterator<E> iterator();
    // toArray
    Object[] toArray();
   
    // get
    E get(int index);
    // set
    E set(int index, E element);
    // 往容器中添加一个对象
    void add(int index, E element);
    // 移除一个元素
    boolean remove(Object o);
    // 清空容器
    void clear();
    
    
    // 对容器排序，指定一个comparator
    // Java8 中支持用default关键字来对接口中的一些方法进行默认实现
    default void sort(Comparator<? super E> c)； 
    
}

2.ArrayList实现

ArrayList底层是用数组来实现的，每个ArrayList对象有个Capacity，这个容量的默认大小为10，随着对象的不断添加，这个容量会增加。

ArrayList一般的用法是这样的：

List<String> list= new ArrayList<>();
list.add("andy");
list.add("jack");
list.add("rose");

System.out.println(list.toString());  // 输出 [andy, jack, rose]

list.remove("andy");
list.remove(1);

System.out.println(list.toString());  // 输出 [jack]

2.1 构造函数

ArrayList的构造函数有两个，即ArrayList()和ArrayList(Collection <? extends E>),下面分别看下它们的源码。

ArrayList()就很简单了，把capacity和size都初始化为0就OK了。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access
private int size; // 容器中对象的数量，这和capacity是不一样的概念！

public ArrayList() {
    // 初始化容量为空
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(Collection <? extends E> c)相对来说就复杂一点，需要判断一下入参的状况，也就是会按照入参c的当前size去初始化容量。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {  // 如果c不为空，则按照c的size扩容好
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {  // 如果c为空，那就和ArrayList()一样，初始化为空
        // replace with empty array.  
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

注意，构造函数执行完后，只是初始化了容量（也就是说，我们大概准备好了即将分配多大的容量），并没有实际去扩容！

2.2 add()方法

Okay，初始化好了，肯定就是添加元素了。添加也有2个重载的方法boolean add(E e)和void add(int index, E e),二者的功能分别是在最后面追加一个对象，和，在指定位置加一个对象（这个位置必须在范围[0,size]之间）。注意，两个方法的返回值类型不一样。

我们先看下add(E e)的源码：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!  // 开始扩容，列表结构被修改的次数加1
    elementData[size++] = e;  // 把待添加的对象放到最后
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {    // 如果容器当前为空容器
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  // 最小的capacity为10
    }

    ensureExplicitCapacity(minCapacity);  // 显式地确保容器容量
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 列表的结构性修改次数

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)  // 如果容器当前的capacity小于待扩容后的容量
        grow(minCapacity);  // 扩容！
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;  // 原来的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新容量扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)  // 如果扩容1.5倍后还达不到想要的容量
        newCapacity = minCapacity;  // 那直接扩到想要的容量
    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);  // 数组扩容
}

有个地方需要注意一下，就是modCount这玩意儿(这个变量是在抽象类AbstractList中声明的)，我们看下文档是怎么说的：

The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.

哦，这个变量指的是list结构被修改的次数，用来到时候迭代器遍历的途中确保list没被修改过。恍然大悟！这让我想起了一点，原来不太会用的时候，曾经这么干过：用迭代器遍历一个list，如果中途发现一个想要删除的对象，则删除它，呵呵！大错特错！！！遍历的途中是不能修改list本身的样子的。

每次add()或remove()，modCount都会自增1。不妨通过例子来验证一下：

List<String> list= new ArrayList<>();
list.add("andy");
list.add("jack");
list.add("rose");

经过上述3次add，modCount=3,size=3,capacity=10(即 elemData.length=10)，debug验证了这个结果。

看了源码，我们知道了，其实ArrayList这玩意儿默认的最小容量是10，也就算说，如果我显式地初始化它的容量为5，最后代码还是会最开始就分配10个容量（想一下？怎么做到显式地初始化？对的，用带参数的构造函数呀！因为带参的构造函数会按照当前的size初始化容量）；随着对象不断添加进来，总有一天它容量不够，会要扩容，而且每次扩容后的容量为原来的1.5倍！

为了再次验证可以通过调用带参的构造函数来使得初始化的容量不为10，我们设计如下test case:

   List<String> list= new ArrayList<>();
   list.add("andy");
   list.add("jack");
   list.add("rose");

   System.out.println(list.toString());  // 输出 [andy, jack, rose]

   List<String> list2= new ArrayList<>(list);
// list2此时的size为3，容量也为3，
list2.add("whut"); // add前肯定是会扩容的，扩容后容量为 (3>>1)+3 = 4，size也为4
   list2.add("cs"); // add前再次扩容，扩容后容量为 (4>>1)+4 = 6，size为5
   list2.add("java");  // 此时不会扩容，add后容量为6，size为6
   
   System.out.println(list2.toString());  // 输出 [andy, jack, rose, whut, cs, java]
   
   list2.remove("andy");
   list2.remove(1);

单步debug很容易验证，这里就不放图了。

有了上面的基础，再看add(int index, E e)就比较简单了。

比方说，现在list中有3个元素为["andy","jack","rose"]，那我们只能add(0~3,"WHUT")。如果add(1,"WHUT")的话，操作后的list为["andy","WHUT","jack","rose"]。

源码如下，主要是多了一个检查下标范围的代码。

 public void add(int index, E element) {
    rangeCheckForAdd(index); // 范围检查

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);  // 把index后面的元素全部右移一个单位
    elementData[index] = element;  // e被放到指定的位置
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

总结:ArrayList在末尾add()的时间复杂度为O(1)；而在指定位置add()的时间复杂度随插入的位置不同而不同，最差情况是在添加在第一个位置，需要右移size个元素，最好情况自然就是一个都不要移动了，时间复杂度为O(N)。

2.3 remove()方法

remove()方法同样也重载了两个，分别是E remove(int index)和boolean remove(Object o),各种功能为删除指定下标处的对象和删除指定的对象（如果该对象不存在，返回false），前者是List接口中的方法，而后者是Collection接口中的方法。

E remove(int index)方法的源码：

public E remove(int index) {
    rangeCheck(index);  // 范围检查

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;  // 要移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved); // 向前平移一个量
    // 把最后一个赋值为null，并且让GC发现，从而回收空间
    elementData[--size] = null; // clear to let GC do its work  

    return oldValue; // 返回删除的值
}

关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

boolean remove(Object o)方法的源代码：

public boolean remove(Object o) {
    if (o == null) {  // 允许容器中存放null对象
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);  // 执行删除操作
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}


private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

移除的过程比较简单，就是遍历，看看待移除的对象是否的确存在，如果存在就删除掉，返回true,否则返回false，这里有2个点我们需要考虑：

如果同时存在多个相同的对象（我这里说的相同指的是equals()）,那么代码会删掉第一个；
从源码我们可以知道，ArrayList()支持插入的时候插入null。

同样，我们设计下述的test case：

List<String> list= new ArrayList<>();
list.add("andy");
list.add("jack");
list.add(null);
list.add("rose");
System.out.println(list.toString());  // 输出 [andy, jack, null, rose]


list.remove(null);
System.out.println(list.toString());  // 输出 [andy, jack, rose]

总结：在list的末尾执行remove()方法执行的时间复杂度为O(1)，而在其他位置移除的时间复杂度为O(N)，而且，如果调用的是remove(Objetc o)方法，除了移动元素之外，还需要遍历原list，直到遇到一个和oequal的对象。

2.4 其他方法

ArrayList里面还有一些其他的方法，比方说clear()、indexOf()、set()，这些都比较简单，就不在这里贴代码了。

3.LinkedList

LinkedList是一个顺序访问的列表，而ArrayList则是一个任意访问的列表。LinkedList同时实现了Deque接口，因此又可以作为队列Queue来使用。继承关系如下：

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList底层是用双向链表实现的，分别是用了first和last来指向第一个和最后一个结点，且实现中是没带头结点的（即Dummy Node）。

LinkedList一般的用法和ArrayList其实没有太大的区别，只不过作为用户的我们，应该对它的操作性能了如执掌：

List<String> list = new LinkedList<>();
list.add("andy");
list.add(0,"jack");
list.add("rose");
System.out.println(list.toString());  // 输出 [jack, andy, rose]

System.out.println(list.remove("java")); // 因为链表中没有java这个结点，故输出false
list.remove("andy");
System.out.println(list.toString());  // 输出 [jack, rose]

list.remove(1);
System.out.println(list.toString());  // 输出 [jack]

3.1 内部结点

private static class Node<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;
    }
}

这个很简单，没什么好说的。

3.2 构造函数

构造函数也有两个，LinkedList()和LinkedList(Collection <? extends E> c)，这两个方法其实和ArrayList的两个构造函数差不多，只不过LinkedList是没有capacity这个概念的。LinkedList()初始化size为0，而LinkedList(Collection <? extends E> c)则会初始化为c的大小。

3.3 add()方法

LinkedList的add()方法也是有两个的，即boolean add(E e)和void add(int index, E element),前者是尾插法插在链表的最后，而后者则会把新的元素插入到index位置，这里肯定会存在遍历链表，找到第index处的元素了，下面我们来看下各自的实现方式。

boolean add(E e)的源代码：

public boolean add(E e) {
    linkLast(e);
    return true;
}

// 尾插法
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;  // 尾插法
    if (l == null) // 如果当前是空链表
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

这就是典型的链表的尾插法，注意要考虑当前链表为空的情况。

void add(int index, E element)的源代码如下：

public void add(int index, E element) {
    checkPositionIndex(index); // 检查下标是否合法

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// 得到链表的第index个结点
Node<E> node(int index) {
    // assert isElementIndex(index);
	
    // 如果index在当前链表的前半段，就从first指针开始遍历
    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;
    }
}

// 在某个结点之前插入一个新的元素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;  // 在中间某处插入
    size++;
    modCount++;
}

个人感觉add()这部分的代码也比较朴素，唯一觉得需要关注的就是在根据index找到指定的node的时候，代码中有一个trick，即if (index < (size >> 1))这个判断，这个操作会视链表为前后两半，如果index在前半段，那就从first开始从前往后找；否则就从last指针开始从后往前找。

总结：LinkedList()的add(E e)方法的时间复杂度为O(1),用的是尾插法；而void add(int index, E element)方法的时间复杂度为O(N/2)，$N$为链表当前的size，这个地方最多只需要遍历一半，也就是上面说到的trick。

3.4 remove()

删除操作重载的方法就比较多了，我们将按照链表中的删除操作和队列中的删除操作进行分类：

链表中的删除操作

链表中的删除操作有boolean remove(Object o)和E remove(int index)，二者功能分别为删除指定的对象和删除指定位置的结点，即如下图所示。

再看下各自的源码：

   // 从前往后遍历，删除第一个和o相等的结点
   public boolean remove(Object o) {
        if (o == null) {  // 允许链表中存在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)) {  // 从前往后开始，找到第一个equals的元素
                    unlink(x);  // 断链
                    return true;
                }
            }
        }
        return false;
   }
   
   // 把指定的结点从链表中断链
   E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {   // 如果待删除的结点在第一个
            first = next;
        } else {
            prev.next = next; // 修改prev的next指针
            x.prev = null;
        }

        if (next == null) {  // 如果待删除的结点在最后一个
            last = prev;
        } else {
            next.prev = prev;  // 修改next的prev指针
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
}

随后就是E remove(int index)的源码了：

public E remove(int index) {
        checkElementIndex(index); // 确保下标合法
        return unlink(node(index)); // 断链掉指定位置的结点
}

总结：remove(Object o)的时间复杂度为O(N),因为不可避免地需要从前往后依次找到一个和o相等的结点；而remove(int index)的时间复杂度为O(N/2),这里同样会用到上面提到的trick。

队列中的删除操作

队列中的删除操作有比较多，例如removeFirst(),removeFirstOccurance(Object o),removeLast(),removeLastOcurrance()。功能分别是删除第一个结点、从前往后遍历删除第一个出现的结点、删除最后一个结点、从后往前遍历删除第一个出现的结点。这些操作的时间复杂度和上述分析类似。

3.5 其他方法

其他的一些方法包括get().clear()、indexOf()、set()，有了上面的源码解读基础，自然就很容易可以做类似的分析了。

4. 参考

部分图来源于网络，在此表示感谢。

Java集合—List篇

List、ArrayList、LinkedList