Java 集合框架（3）---- List 相关类解析（下）

短命女 2022-05-20 23:13 230阅读 0赞

### 文章目录 ###

*   *  前言
     *  ArrayList
     *  LinkedList
     *  Vector
     *  Stack

## 前言 ##

在上篇文章中，我们主要看了 `AbstractCollection` 抽象类 `List` 接口下的 `AbstractList` 抽象类，介绍了他们实现了 `Collection` 中一些抽象方法。在这篇文章中，我们来看一下 `List` 接口下的一些具体类，也就是我们平常经常使用的一些类：

## ArrayList ##

这个类算的上是我们平常开发中最常用的类之一了。翻译过来意思是 `数组列表` ，不过比起这个名称，我更喜欢叫它 `动态数组`（受 C++ STL 模板的 `vector` 模板类的影响）。不过不管怎么叫它，它的功能不会遍，我们经常会用它作为动态管理数组元素的集合类。  
我们先来看一下它的类继承图：

![ArrayList 类的继承结构图][ArrayList]

我们可以看到，`ArrayList` 类继承于 `AbstractList` 抽象类，这个抽象类我们在上篇文章中已经仔细介绍过了，它继承于 `AbstractCollection` 抽象类，实现了 `List` 接口，并且实现了一些 `AbstractCollection` 接口没有实现的抽象方法（`size()` 、 `iterator()` 等方法）。官方文档对它的描述是：该类提供了 `List` 接口的骨架实现，以最大限度地减少实现由 “随机访问” 数据存储（如数组）所支持的接口所需的工作量。对于顺序访问数据（如链接列表），应该优先使用 `AbstractSequentialList` 类 。`ArrayList` 类本身就是表示一种线性结构的类，那么继承于 `AbstractList` 类也是理所当然。此外，`ArrayList` 类还实现了 `Serializable` 、`RandomAccess`、`Cloneable` 接口。其中 `Serializable` 接口是用于将对象序列化以储存在文件中或者通过流的形式在网络中传输的接口，`RandomAccess` 接口是一个没有声明任何方法的空接口，`cloneable` 接口是一个对象复写 `Object` 类中 `clone()` 方法必须实现的接口，它也是一个没有声明任何方法的空接口，但是它却是一个很重要的接口。我们知道 `Object` 类对象的 `clone()` 方法用于生成一个和这个对象的完全相同的拷贝对象，但是调用一个对象的 `clone()` 方法的前提是这个对象的类必须实现 `Cloneable` 接口，否则的话调用者就会得到一个 `CloneNotSupportedException` 异常，有兴趣小伙伴们去做个小实验就明白了。

关于 `ArrayList` 提供的一些方法相信你已经不陌生了，其提供的大多数方法都是 `AbstractList` 类中声明的，下面我们从源码的角度上来看其中的一些方法细节：

先从构造方法开始：

/**
     * 指定数组容量的构造方法
     */
    public ArrayList(int initialCapacity) {
        
            if (initialCapacity > 0) {
        
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
        
                // 将保存元素的数组指向一个默认为空的数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
        
                // 指定的数组容量小于 0 ，抛出一个异常
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
        /**
         * Constructs an empty list with an initial capacity of ten.
         * 构造一个初始容量为 10 的空数组列表
         */
        public ArrayList() {
        
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        /**
         * 构造一个包含了参数指定的集合中包含的所有元素的数组列表
         */
        public ArrayList(Collection<? extends E> c) {
        
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
        
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
        
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

我们在其中看到了一些对象的成员变量，我们来看看它们在类中的声明：

/**
         * 默认的数组初始容量为 10 
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * 代表没有任何元素的空数组实例对象
         */
        private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
        /**
         * 默认构造方法中赋值给 elementData 引用的数组对象，是一个空元素数组
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
        /**
         * 储存当前 ArrayList 对象包含的元素数组，当第一个元素通过 add 方法添到数组中时，
         * 如果当前的 elementData 引用指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，
         * 即如果 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
         * 这个 elementData 数组将会被扩展至具有默认容量（10）的数组
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * 记录数组列表中元素的个数
         */
        private int size;

看到这里可能有些小伙伴们会问了：不是说 `ArrayList` 类默认的构造方法会构造出一个容量为 10 的数组吗，为什么在 `ArrayList` 类默认的构造函数中只看到了一句 `this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;` 的代码，并且在后面的代码中也显示出这个 `DEFAULTCAPACITY_EMPTY_ELEMENTDATA;` 是一个容量为 0的空数组啊。难道官方说明出错了？

其实并不是这样的，在 `elementData` 字段上的注释中解释的很清楚：当第一个元素通过 `add` 方法添加到当前 `ArrayList` 对象中时，如果 `elementData` 字段和 \`\`DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA`相等时，`elementData`会被扩展至具有默认容量的数组。好了，这么说的还是有点虚，我们不妨来看看`ArrayList`类的`add\` 方法：

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

我们看到先调用了 `ensureCapacityInternal(int )` 方法，我们继续跟进：

private void ensureCapacityInternal(int minCapacity) {
        
        // 当 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的时候，
        // 将数组容量设置为 DEFAULT_CAPACITY 和参数 minCapacity 中较大的一个
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

在出现了 `elementData` 和 `DEFAULTCAPACITY_EMPTY_ELEMENTDATA` 的相等性比较之后，方法又调用了 `ensureExplicitCapacity(int )` 方法，我们还是继续跟进：

private void ensureExplicitCapacity(int minCapacity) {
        
        // 该字段定义在 AbstractList 中，定义代码为：
        // protected transient int modCount = 0;
        // 代表了列表元素的更改次数，此时明显这个值要加 1
        modCount++;
        // overflow-conscious code
        // 如果要求的最小容量大于当前元素数组的长度，那么进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在这里调用了 `grow(int )` 方法来进行扩容，还是继续看一下 `grow(int )`方法吧：

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 可以看到：新的数组容量为前一次数组容量的 1.5 倍，
        // 即每次储存元素的数组容量扩大的倍数为 1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果计算出扩容后的容量小于参数指定的容量，那么将容量调整为参数指定的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果计算出扩容后的容量大于允许分配的最大容量值，那么进行溢出判断处理，
        // MAX_ARRAY_SIZE 为 AbstractList 中定义的一个字段，代码：
        // private static final int 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);
    }

这里通过 `hugeCapacity(int )` 方法来进行判断溢出，我们来看看这个方法：

private static int hugeCapacity(int minCapacity) {
        
        // int 类型为 32 位有符号整数，并且计算机内部通过补码来保存数字，
        // 最高位为符号位，如果为 0，代表为正数，如果为 1，代表为负数。
        // 如果 minCapacity 发生溢出，那么其最高位必定为 1 ，
        // 整个数字就是一个负数，此时抛出 OutOfMemoryError 异常。
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

关于计算机中数字的表示方法这里再解释一下：我们知道，计算机通过二进制补码来表示整数，对于有符号的整数，用其最高位的那一位来表示当前数字的正负，如果最高位为 0，那么这个数为正数，如果最高位为 1，那么这个数为负数，这里举个例子：

int a = 0b11000000000000000000000000000000; // 11 后面跟 30 个 0
    System.out.println(a);
    System.out.print(-(1 << 30));

此时 a 的值是多少呢？按照我们之前的理论：此时 a 的最高位为 1 ，那么就是一个负数，第二个 1 后面跟了 30 个 0，那么 a 的值应该是 `-2^30` ，后面的那个输出我将1 向左移 30 位在取相反数，那么此时两个结果应该相同。事实真的如此吗，我们来看看结果：

![这里写图片描述][70]

我们看到确实是这样的。其实关于补码还有一点特殊的规则，比如 0 和对应数据类型的最大负值是怎么表示的，有兴趣的小伙伴可以自己查阅一些资料。

我们回到上面的 `grow(int )` 方法中来，在调用了 `hugeCapacity(int )` 方法之后，会调用 `Array.copyOf` 方法来进行扩容处理，我们继续跟进：

@SuppressWarnings("unchecked")
    public static <T> T[] copyOf(T[] original, int newLength) {
        
        return (T[]) copyOf(original, newLength, original.getClass());
    }

直接返回了 `copyOf` 重载方法的返回值，继续看这个方法吧：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        
        @SuppressWarnings("unchecked")
        // 如果数组储存的元素类型为 Object 类型，那么创建一个新的扩容后的 Object 数组，
        // 否则创建一个和数组储存的元素类型相同的扩容后的数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        // 将原数组中的元素值拷贝到新数组中
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

在这里我们终于看到了创建新的数组的操作代码。好了，这样的话我们就把 `ArrayList` 的添加元素的整个流程过了一遍，主要流程也不复杂：

**先判断元素数组是否需要扩容 ⇒ 确定扩容后的容量（第一次将容量调整为默认容量（10），之后 以1.5 倍数进行扩容）⇒ 判断扩容后容量是否溢出 ⇒ 进行数组扩容并复制原数组元素到新数组中。**

同时我们也知道：进行扩容操作的代价是很大的，尤其是当你的 `ArrayList` 的元素数量很大的时候，向虚拟机申请内存空间和进行元素拷贝的开销都很大，所以我们在使用的时候如果能够预知需要使用的最大容量，我们应该调用传入固定数值参数作为数组元素最大容量的构造方法，以最大化减小系统开销。

`ArrayList` 的 `add` 方法和扩容机制我们已经看完了，下面来看看获取元素值的 `get` 方法：

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        
        // 检查参数范围是否在数组允许的下标范围之内
        rangeCheck(index);
    
        return elementData(index);
    }

获取元素值得方法相对简单，先调用了 `rangeCheck(int )` 方法来检查参数范围，返回了 `elementData(int )` 方法的返回值，我们来看看这两个方法：

/**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

接下来是 `elementData(int )` 方法：

E elementData(int index) {
        
        return (E) elementData[index];
    }

好了。接下来我们再来看看 `ArrayList` 类中的一些其他的方法：

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        
        // 检测下标是否越界
        rangeCheckForAdd(index);
        
    	// 判断是否需要扩容，如果需要，那么进行扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        
        // 将 elementData 数组中从下标 index 开始的 size - index 个元素
        // 复制到 elementData 数组中从 index + 1 开始的 size - index 个元素中，
        // 即为将 elementData 数组中从 index  下标开始的所有元素向后移动一个位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 插入新元素
        elementData[index] = element;
        size++;
    }

这个方法用于在指定下标（index） 的位置插入一个新元素（element），可以看到这个方法的时间复杂度为 O(N)。

/**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        
        // 检查下标是否越界
        rangeCheck(index);
    
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

这个方法用于将指定下标（index） 的元素值设置为参数指定的新元素值（element），并返回旧元素值。

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        
        rangeCheck(index);
    
        modCount++;
    
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将数组中从 index + 1 下标开始的元素向前移动一个位置
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

这个方法用于移除元素数组中指定下标（index）的元素，并且返回旧元素。方法的时间复杂度为 O(N)。

好了，关于 `ArrayList` 类中的一些常用方法就介绍到这里了。到这里我们知道 `ArrayList` 采用数组来储存元素值，因此它的插入元素和删除元素操作的效率并不高（O(N) 的时间复杂度），所以它不适用于需要进行频繁插入和删除元素操作的场合中，那么如果我就需要频繁进行插入和删除元素等操作怎么办呢？此时就该 `LinedList` 类上场了，来看看这个线性结构类：

## LinkedList ##

这个类想必大家也很熟悉了，其实现就是一个双向链表，我们来看看这个类的继承图：

![这里写图片描述][70 1]

可以看到：`LinkedList` 类继承了 `AbstractSequentialList` 抽象类，同时实现了 `List` 、`Queue` 、`Deque` 、`Cloneable` 、`Serializable` 接口。其中，`Cloneable` 接口和 `Serializable` 接口我们在上面已经讲过了，前者是一个空接口，为 `clone()` 方法服务的，后者也是一个空接口，而其是为对象序列化而服务的。我们来看一下 `Queue` 接口，根据接口名我们大概能猜到这个接口声明了 队列 的相关方法：

public interface Queue<E> extends Collection<E> {
        
        /**
         * 插入一个元素到队列尾部，成功返回 true， 失败返回 false，
         * 如果队列有容量限制并且已经达到最大容量，
         * 那么抛出一个 IllegalStateException 异常
         */
        boolean add(E e);
    
        /**
         * 插入一个元素到队列尾部，成功返回 true， 失败（队列元素已满）返回 false，
         * 不抛出 IllegalStateException 异常
         */
        boolean offer(E e);
    
        /**
         * 取出队列头部元素，并且将这个元素从队列中移除，
         * 如果队列为空，那么抛出 NoSuchElementException  异常
         */
        E remove();
    
        /**
         * 取出队列头部元素，并且将这个元素从队列中移除，
         * 和 remove() 方法的区别是如果队列为空，那么返回 null ，而不是抛出异常
         */
        E poll();
    
        /**
         * 取出队列头部元素，但是不从队列中移出这个元素，返回取出的元素，
         * 如果队列为空，那么抛出一个 NoSuchElementException 异常
         */
        E element();
    
        /**
         * 取出队列头部元素，但是不从队列中移出这个元素，返回取出的元素，
         * 和 element() 方法的区别在于当队列为空时这个方法返回 null 而不抛出异常
         */
        E peek();
    }

可以看到，这个接口确实声明了一个 队列（元素从队尾进入队列、从队头出队列） 中应有的相关操作方法。我们再来看看 `Deque` 接口，这个接口声明了 双端队列 的相关操作方法：

public interface Deque extends Queue {
        
    	/**
    	 * 添加元素到双端队列头部，如果队列元素已满，那么抛出一个 IllegalStateException 异常
    	 */
    	void addFirst(E e);
    	
    	/**
    	 * 添加元素到双端队列尾部，如果队列元素已满，那么抛出一个 IllegalStateException 异常
    	 */
    	void addLast(E e);
    	
    	/**
    	 * 插入一个元素到双端队列头部，插入成功返回 true，否则（队列元素已满）返回 false
    	 */
    	boolean offerFirst(E e);
    	
    	/**
    	 * 插入一个元素到双端队列尾部，插入成功放回 true，否则（队列元素已满）返回 false
    	 */
    	boolean offerLast(E e);
    	
    	/**
    	 * 移除并返回双端队列的头部元素，如果队列已空，那么抛出一个 NoSuchElementException 异常
    	 */
    	E removeFirst();
    	
    	/**
    	 * 移除并返回双端队列的尾部元素，如果队列已空，那么抛出一个 NoSuchElementException 异常
    	 */
    	E removeLast();
    	
    	/**
    	 * 移除并返回双端队列头部的元素，如果队列已空，那么放回 null 而不抛出异常
    	 */
    	E pollFirst();
    	
    	/**
    	 * 移除并返回双端队列尾部的元素，如果队列已空，那么返回 null 而不抛出异常
    	 */
    	E pollLast();
    	
    	/**
    	 * 返回但不移除双端队列头部元素，如果队列已空，那么抛出 NoSuchElementException 异常
    	 */
    	E getFirst();
    	
    	/**
    	 * 返回但不移除双端队列尾部元素，如果队列已空，那么抛出 NoSuchElementException 异常
    	 */
    	E getLast();
    	
    	/**
    	 * 返回但不移除双端队列首部元素，如果队列已空，那么返回 null 而不抛出异常
    	 */
    	E peekFirst();
    	
    	/**
    	 * 返回但不移除双端队列尾部元素，如果队列已空，那么返回 null 而不抛出异常
    	 */
    	E peekLast();
    	
    	// ...
    	
    }

和 `Queue` 中的方法在逻辑上有点类似，只不过这里是 双端队列，可以对队列头部和尾部进行操作。  
由此我们也知道了，`LinkedList` 还可以充当队列 / 双端队列使用，因为其实现了 `Deque` 接口。而 `Deque` 接口又继承了 `Queue` 接口。下面再看看 `AbstractSequentialList` 抽象类，`LinkedList` 类继承了这个类，这个类继承了 `AbstractList` 抽象类，我们看看这个类的方法：

/**
     * 获取下标 index 所指向的元素，如果下标越界，抛出 IndexOutOfBoundsException 异常
     */
    public E get(int index) {
        
        try {
        
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
        
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    
    /**
     * 将下标为 index 的元素设置为参数 element 指定的元素，
     * 如果下标越界，抛出 IndexOutOfBoundsException 异常
     */
    public E set(int index, E element) {
        
        try {
        
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
        
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    
    /**
     * 插入一个元素到下标 index 的位置上，如果下标越界，抛出 IndexOutOfBoundsException 异常
     */
    public void add(int index, E element) {
        
        try {
        
            listIterator(index).add(element);
        } catch (NoSuchElementException exc) {
        
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    
    /**
     * 移除下标为 index 的元素，如果下标越界，抛出 IndexOutOfBoundsException 异常
     */
    public E remove(int index) {
        
        try {
        
            ListIterator<E> e = listIterator(index);
            E outCast = e.next();
            e.remove();
            return outCast;
        } catch (NoSuchElementException exc) {
        
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    
    
    // Bulk Operations
    
    /**
     * 将集合 c 中的所有元素按照集合 c 迭代器遍历顺序插入到当前 List 从 index 下标开始的位置，
     * 如果下标 index 越界，抛出 IndexOutOfBoundsException 异常
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        
        try {
        
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            Iterator<? extends E> e2 = c.iterator();
            while (e2.hasNext()) {
        
                e1.add(e2.next());
                modified = true;
            }
            return modified;
        } catch (NoSuchElementException exc) {
        
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

我们在上篇文章已经说过：`AbstractList` 抽象类实现了 `List` 接口声明的一些接口，包括 `iterator()` 方法用于返回一个当前 List 对象的迭代器， 但是其并没有实现诸如元素访问和修改的方法（`get(int index)`、`set(int index, E element)` 等）。那么这个类即通过 `AbstractList` 中实现的迭代器方法来实现这个对 List 对象中元素进行访问和修改的方法。这样的话在某个方面来说也是减轻了子类的负担（子类可以有选择性的复写父类的方法）。  
好了，说了这么多，我们来看看 `LinkedList` 类，先从其储存的元素类型开始，因为我们知道 `LinkedList` 内部其实是通过双向链表的形式来储存元素节点，那么我们来看看这个用于表示元素节点的类 `LinkedList.Node` ：

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;
        }
    }

可以看到，这个 `Node` 类实际上是 `LinkedList` 类的一个私有内部类。包含元素值、直接前驱、直接后继。即为一个双向链表节点。下面来看看 `LinkedList` 类的构造方法：

/**
     * Constructs an empty list.
     */
    public LinkedList() {
        
    }
    
    /**
     * 构造一个包含了 c 集合中所有元素的 LinkedList 对象（按照 c 的迭代器遍历顺序添加元素），
     * 如果 c 为 null，那么抛出 NullPointException 异常
     */
    public LinkedList(Collection<? extends E> c) {
        
        this();
        addAll(c);
    }

`LinkedList` 提供了两个构造方法，并且也没有什么默认容量的概念，也没有扩容的概念，仔细想想很容易理解：双向链表的特性便是来一个元素就储存一个元素，即每当添加一个新元素的时候，就将其插入到当前链表的结尾，它不像数组一样需要一开始就要确定数组的容量，并且当有新的元素需要储存的时候还需要考虑当前数组剩余空间是否能够储存新的元素进而考虑数组扩容。但是相对于数组其缺点也很明显：每个节点除了保存当前节点的元素值以外，还需要保存其对应的直接前驱结点对象和直接后继结点对象的引用。在某个方面来说，这是消耗了额外的储存空间。下面来看看 `LinkedList` 类中定义的相关字段：

// 保存 LinkedList 的元素数量，用 transient 关键修饰使其不参与序列过程
    transient int size = 0;
    
    /**
     * Pointer to first node.
     * 指向 LinkedList 第一个节点的引用
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    
    /**
     * Pointer to last node.
     * 指向 LinkedList 最后一个节点的引用
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

相比 `ArrayList` 来说，`LinkedList` 定义的字段相对简单。好了，接下来看看 `LinkedList` 类添加新元素的方法：

/**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        
        linkLast(e);
        return true;
    }

可以看到，通过这个方法将新的元素添加到 `LinkedList` 末尾。这里调用了 `linkLast(E )` 方法来进行添加元素，我们跟进这个方法：

/**
     * Links e as last element.
     */
    void linkLast(E e) {
        
        final Node<E> l = last;
        // 新建一个节点来保存要储存的元素值，并且将这个节点的直接前驱引用设置为 l（last）
        final Node<E> newNode = new Node<>(l, e, null);
        // 更新 last 引用（指针）
        last = newNode;
        // 如果当前 LinkedList 没有元素，那么将当前节点作为双向链表的头结点
        if (l == null)
            first = newNode;
        // 否则的话将 l.next 赋值为 newNode，即将 l（last）的直接后继节点设置为 newNode
        else
            l.next = newNode;
        // 元素个数 + 1
        size++;
        // 集合元素更改次数加 1，该变量在 AbstractList 中定义
        modCount++;
    }

这里涉及到数据结构中在双向链表末尾添加新元素的过程，即将新的末尾节点和旧的末尾结点通过直接前驱和直接后继的关系链接起来，然后更新末尾节点为新添加的这个节点（相当于末尾节点引用（指针）后移，这里的源码是先后移再建立链接）。再来看一个重载的方法：

/**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        
    	// 检测下标是否越界，越界则抛出 IndexOutOfBoundsException 异常
        checkPositionIndex(index);
    	
    	// 如果 index 和 size 相等，那么即直接在链表尾部插入新元素
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

我们看到，方法通过 `node(int index)` 方法来得到指定下标的元素，并且通过 `linkBefore` 来完成插入操作，我们先来看看 `node(int index)` 方法：

/**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        
        // assert isElementIndex(index);
    	
    	// 如果 index 不大于链表长度的 1/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;
        }
    }

在这个方法里面通过链表长度的 1/2 和 index 的值进行比较，进而判断是采用正向遍历链表还是反向遍历链表来找出指定下标的元素，最大化减少循环的执行次数，方法的设计者真大牛！接下来看看 `linkBefore(E , E )` 方法：

/**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        
        // assert succ != null;
        // 记录 succ 节点的直接前驱节点
        final Node<E> pred = succ.prev;
        // 新建 Node 对象保存要插入的元素，并且指定其直接前驱结点和直接后继节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        // succ 的直接前驱结点赋值为 newNode（在 succ 之前插入 newNode 节点）
        succ.prev = newNode;
        // 如果当前 LinkedList 没有任何元素，那么将这个节点作为 first 结点
        if (pred == null)
            first = newNode;
        // 否则将 succ 的直接前驱节点的直接后继结点设置为 newNode 完成插入
        else
            pred.next = newNode;
        // 元素个数加 1 
        size++;
        // LinkedList 更改次数加 1
        modCount++;
    }

这个操作其实就是双向链表中在某个元素（这里为 succ ）前插入一个新元素的操作，和插入元素到链表尾部差不多，不再陈述了。看完了主要的添加元素的方法，接下来看看获取元素的方法：

/**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        
    	// 判断下标是否越界，如果越界抛出一个 IndexOutOfBoundsException 异常
        checkElementIndex(index);
        return node(index).item;
    }

我们看到也是通过 `node(int index)` 来得到对应下标的节点并返回储存的元素值。  
下面来看看修改元素的相关方法：

先是 `set(int index, E element)` 方法：

/**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        
    	// 检测下标是否越界，如果越界，抛出一个 IndexOutOfBoundsException 异常
        checkElementIndex(index);
        // 获取 index 下标所指的元素节点
        Node<E> x = node(index);
        // 更新元素节点的 item 引用为要设置的新值
        E oldVal = x.item;
        x.item = element;
        // 返回被替换的旧值
        return oldVal;
    }

添加和修改元素看完了，接下来是移除元素的方法了：

/**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        
    	// 检测下标是否越界，越界抛出 IndexOutOfBoundsException 异常
        checkElementIndex(index);
        // 通过 node(int index) 方法找到要移除的元素，
        // 并且调用 unlink 方法来移除这个元素
        return unlink(node(index));
    }

`node(int index)` 方法我们已经讲过了，那么来看看 `unlink(E )` 方法：

/**
     * Unlinks non-null node x.
     */
    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;
    	
    	// 如果 x 的直接前驱节点为 null ，那么证明 x 为头结点，此时把 first 后移
        if (prev == null) {
        
            first = next;
        } else {
        
    	    // 否则将 x 的直接前驱结点的直接后继结点指向 x 的直接后继结点（有点绕，仔细理解一下）
            prev.next = next;
            // 断开 x 和其直接前驱结点的联系
            x.prev = null;
        }
    	
    	// 如果 x 的直接后继结点为 null，那么证明 x 为尾节点，此时把 last 前移
        if (next == null) {
        
            last = prev;
        } else {
        
    	    // 否则将 x 的直接后继结点的直接前驱结点指向 x 的直接前驱结点（仿造上面）
            next.prev = prev;
            // 断开 x 和其直接后继结点的联系
            x.next = null;
        }
    	
    	// x.item 置为空，方便 GC 回收对象
        x.item = null;
        // LinkedList 元素个数减 1
        size--;
        // LinkedList 修改次数加 1
        modCount++;
        // 返回被移除的节点的 item 元素值
        return element;
    }

`remove` 方法还有一个重载方法：

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    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;
    }

操作其实差不多，如果要移除的元素值 o 为 null，那么遍历链表找到 item 等于 null 的节点，之后就是调用 `unlink` 方法来移除这个节点了。当 o 不为 null 的时候就遍历链表并且通过 `equals` 方法来找到 item 等于 o 的节点，再调用 `unlink` 方法来移除这个节点。

OK，到这里我们就把 `LinkedList` 的相关方法介绍完了，`LinkedList` 内部通过双向链表实现，相对 `ArrayList` 来说，其插入元素、删除元素的效率更高。

## Vector ##

这个类其实和 `ArrayList` 类相当像，也是利用数组储存元素，同时也可以动态的管理元素，我们可以看看它的类继承结构图：

![这里写图片描述][70 2]

可以看到 `Vecctor` 类和 `ArrayList` 继承的类和实现的接口都一样，那么它们有什么地方不同吗？答案是肯定的，要不然 Java 没必要设计两个功能相同的类来添加开发者的负担，我们先看看 `Vector` 类的构造方法：

/**
     * 创建一个初始容量为 initialCapacity ，每次扩容量为 capacityIncrement 的 Vector 对象
     */
    public Vector(int initialCapacity, int capacityIncrement) {
        
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    
    public Vector(int initialCapacity) {
        
        this(initialCapacity, 0);
    }
    
    /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     * 创建具有默认个数（10）个容量的 Vector
     */
    public Vector() {
        
        this(10);
    }
    
    /**
     * 创建一个 Vector，并把集合 c 中的元素按照迭代器的遍历顺序将元素添加到 Vector 中
     * @since   1.2
     */
    public Vector(Collection<? extends E> c) {
        
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

我们可以看到 `Vector` 类的构造方法中多了一个带有 `capacityIncrement` 参数的方法，并且在代码中有一句：`this.capacityIncrement = capacityIncrement;` ，那么我们来看看这个 `capacityIncrement` 字段的定义:

/**
     * The amount by which the capacity of the vector is automatically
     * incremented when its size becomes greater than its capacity.  If
     * the capacity increment is less than or equal to zero, the capacity
     * of the vector is doubled each time it needs to grow.
     */
    protected int capacityIncrement;

从注释中我们可以得到如果这个值小于或等于 0，那么 `Vector` 每次扩容的倍数为 2 ，即每次扩容时容量增加一倍。  
关于这个，我们可以参考源码：

private void grow(int minCapacity) {
        
        // overflow-conscious code
        int oldCapacity = elementData.length;
    	
    	// 如果 capacityIncrement  大于 0，那么扩大 capacityIncrement 大小，
    	// 否则扩大 oldCapacity 大小（即扩大一倍）
        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);
    }

Ok，如果没有给 `Vector` 指定每次扩大的容量，那么其每次默认扩大的倍数为 2 ，我们再来看其中的一些方法：  
![这里写图片描述][70 3]  
我们可以看到，类中的一些关键方法用 `synchronized` 关键字修饰，关于 `synchronized` 关键字在本专栏前一个系列中的同步的文章中已经说过了，有兴趣的小伙伴可以看看：[Java 多线程（4） — 线程的同步（中）][Java _4_ _] 。回到这里，也就是说这些方法都是受同步控制的，即为多线程安全的方法。反观 `ArrayList` ，其并没有对方法加以同步控制，也就是说 `ArrayList` 是非线程安全的，我们取 `ArrayList` 中的一个 `add` 方法来看：

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++;
    }

现在假设有两个线程同时进入这个方法内执行，首先线程 1 执行的很顺利，一直执行，直到 `size++;` 这一句，我们知道 `sie++` 是没有原子性的，线程 1 先从主内存取到 size 的值，不巧的时候当线程 1 取到 size 的值之后被阻塞了，我们把此时线程 1 的私有工作内存中的 size 的值记为 oldSize，此时线程 2 得到 CPU 资源开始执行，线程 2 执行的很顺利，一次性就把 `add` 方法中的所有代码执行完了，并且把 size 的值更新到主内存中，那么此时主内存中 size 的值为 oldSize + 1，之后线程 2 让出 CPU 资源，线程 1 得到 CPU 资源从上次停止的位置继续执行，因为此时在线程 1 中的 size 的值还是为 oldSize ，那么执行完之后线程 1 中的 size 的值会变成 oldSize + 1，之后线程 1 将主内存中 size 的值更新为 oldSize + 1（其实线程 2 之前已经将主内存中 size 的值加一了），此时出现了明明添加了两个元素到 `ArrayList` 中，而 size 的值确只增加了 1。

对于 `Vector` 来说，这种情况就不存在了，因为方法用 `synchronized` 关键字修饰了，那么同一时刻只有一个线程能够进入方法中执行，即使这个线程被阻塞让出了 CPU，它所占用的锁资源并不会被释放，所以其他线程任然不能进入这个方法执行代码，这样就保证了该操作的多线程安全。

## Stack ##

最后来看看 `Stack` 类，这个类继承了 `Vector` 类，提供了数据结构中 **栈** 的实现。我们来看看它的类继承图：

![这里写图片描述][70 4]

这里没有出现新的类和接口，但是个人觉得这里的继承设计并不合理，为什么这么说？我们知道栈的操作无非就几种：入栈、出栈、查看栈顶元素、判断栈是否为空、得到栈中元素的个数。而 `Vector` 不仅支持这几种操作，同时支持随机访问、随机修改、随机添加。没有必要直接继承 `Vector` 类。我们知道类的继承层次越深，创建这个类所需要的内存空间就越大（创建子类对象之前得先创建其父类对象），而栈本身应该是一种轻量级的数据结构。个人觉得像 `Queue` 和 `Deque` 接口那样新建一个 `Stack` 接口并提供栈的相关操作方法，然后让 `LinkedList` 类实现这个 `Stack` 接口并且重写其中对应的方法就可以了。当然这里也只是我的个人看法，可能设计者有其他的目的吧。我们还是看一下 `Stack` 类中的一些方法：

/**
     * Creates an empty Stack.
     */
    public Stack() {
        
    }
    
    /**
     * 添加元素到栈顶
     */
    public E push(E item) {
        
        addElement(item);
    
        return item;
    }
    
    /**
     * 返回并弹出栈顶元素，如果栈为空，
     * 那么抛出一个 EmptyStackException 异常
     */
    public synchronized E pop() {
        
        E       obj;
        int     len = size();
    
        obj = peek();
        removeElementAt(len - 1);
    
        return obj;
    }
    
    /**
     * 返回但是不弹出栈顶元素，如果栈为空，
     * 那么抛出一个 EmptyStackException 异常
     */
    public synchronized E peek() {
        
        int     len = size();
    
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    
    /**
     * 判断栈是否为空
     */
    public boolean empty() {
        
        return size() == 0;
    }

可以看到这里面的一些方法也是使用了 `synchronized` 修饰，也就是说 `Stack` 类的方法也是线程安全的，可能设计想把 `Stack` 设计成线程安全的类，所以让其继承 `Vector` 类吧。  
好了，到这里我们就把 `List` 接口下的一些具体类解析完了。我们总结一下：

`ArrayList`：内部采用数组保存元素，初始默认容量为 10，之后添加元素时，如果数组容量不足，则以 1.5 倍的倍数扩容数组，溢出时抛出 `OutOfMemeryError` 异常。扩容操作即为新建一个更大的数组并将原数组中的元素拷贝到新数组中。在元素较多时扩容操作开销较大，如果一开始可以确定最大需要的容量，那么建议使用另一个构造方法来创建指定初始容量的 `ArrayList` 以提高效率。因为采用的数组储存元素，所以插入和删除元素操作较慢（时间复杂度为 O(N)）。 `ArrayList` 为非线程安全的类。

`LinkedList` ：内部采用双向链表来储存元素，每添加一个元素就新建一个 `Node` 并添加到对应的位置，就没有所谓的扩容机制，同时实现了 `Deque` 接口，可以作为队列 / 双端队列使用。插入元素、移除元素效率较高（时间复杂度为 O(1)），但是随机访问元素效率较低（时间复杂度为 O(N)）。`LinkedList` 非线程安全。

`Vector` ：和 `ArrayList` 相似，内部采用数组保存元素，默认容量为 10。创建时如果指定了 `capacityIncrement` 参数，那么每次扩容时数组容量增加 `capacityIncrement` ，否则扩容时数组容量变为原来的 2 倍。`Vector` 线程安全。

`Stack` ：继承于 `Vector` 类，提供了数据结构中 栈 的相关操作方法，线程安全。

好了，这篇文章我们一起看了一下 `ArrayList`、`LinkedList` 、`Vector` 、`Stack` 等 `List` 接口下的类，  
并且从源码的角度上分析了一些常用的方法和这些类各自的特性。下篇文章我们将继续探讨 `Map` 集合接口中的一些类和接口。  
如果博客中有什么不正确的地方，还请多多指点。如果这篇文章对您有帮助，请不要吝啬您的赞，欢迎继续关注本专栏。

谢谢观看。。。

[ArrayList]: /images/20220521/57b2ffceb60f46f8aadb5d1915848bc0.png
[70]: /images/20220521/5d77da786eb846d5bc596676f6287557.png
[70 1]: /images/20220521/b11ba932318d4d64a5abd13af7e323c6.png
[70 2]: /images/20220521/a3e1484c46cb4c00a6b457e202385129.png
[70 3]: /images/20220521/053c05a4db934fe59f2522fc9da27e04.png
[Java _4_ _]: https://blog.csdn.net/Hacker_ZhiDian/article/details/79645644
[70 4]: /images/20220521/c1ca65a408d74949a1a382f7001e87c4.png