Java集合知识总结（上）

本文部分内容节选自Java Guide, 地址: https://javaguide.cn/java/collection/java-collection-questions-01.html

🚀 基础（上） → 🚀 基础（中） → 🚀基础（下） → 🤩集合（上） → 🤩集合（下） → 🤗JVM专题1 → 🤗JVM专题2 → 🤗JVM专题3 → 🤗JVM专题4 →😋JUC专题1 → 😋JUC专题2

Java 集合概述

Java 集合, 也叫做容器, 主要是由两大类接口派生而来, 一个是 Collection 接口, 主要用于存放单一元素; 另一个是 Map 接口, 主要用于存放键值对. 对于 Collection , 下面又有三个主要的子接口 List , Set 和 Queue

Java 集合框架如下所示:

说说 List, Set, Queue, Map 四者的区别?

• List : 存储的元素是有序的可重复的
• Set : 存储的元素是不可重复的
• Queue : 队列. 存储元素是可重复的, 有序的
• Map : 使用键值对（key-value）存储, 类似于数学上的函数 y=f(x), “x” 代表 key, “y” 代表 value, key 是无序的, 不可重复的, value 是无序的, 可重复的, 每个键最多映射到一个值

List

ArrayList

ArrayList 是 Object[] 数组, 底层是数组数列, 相当于动态数组. 与 Java 的数组相比, 它的容量可以动态增长. 在添加大量元素前, 应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量. 这可以减少递增式再分配的数量

如果你有学过C++的话, 你应该会意识到 ArrayList 和 C++ 中的 Vector 非常相似. Vector 也是动态数组, 也能动态增长.

ArrayList 继承于 AbstractList , 实现了List, RandomAccess, Cloneable, java.io.Serializable 这些接口

• List 表明它是一个列表, 支持添加, 删除, 查找等操作, 并且可以通过下标进行访问
• RandomAccess 表明实现这个接口的 List 是支持快速访问的. 在 ArrayList 中, 我们可以通过元素的下标来直接获取元素, 这就是快速访问
• Cloneable 表明它具有拷贝能力, 可以进行深拷贝和浅拷贝操作
• Serializable 表明它可以序列化, 也就是可以把对象转换为字节流进行存储或进行网络传输

ArrayList 可以存储任何类型的对象, 但是不建议存储 null 值, 因为一方面 null 值没有意义, 另一方面存储 null 值可能会导致空指针异常

ArrayList 和 LinkedList 的区别?

• 线程安全 : ArrayList 和 LinkedList 都是不同步的, 也就是不保证线程安全
• 底层数据结构 : ArrayList 底层使用的是 Object 数组, LinkedList 底层使用的是双向链表
• 插入与删除 :
  • ArrayList 采用数组存储, 所以插入和删除元素受元素个数影响. 例如, 执行 add(E e) 方法时, ArrayList 会默认将元素插入到末尾, 时间复杂度就是$O(1)$ . 但是如果在指定位置插入 add(int index, E e) , 时间复杂度就是$O(n)$
  • LinkedList 采用链表存储, 所以在头尾插入删除元素不受元素个数影响, 时间复杂度为$O(1)$ . (如 add(E e) , addFirst(E e) , addLast(E e) , removeFirst() , removeLast()). 但是如果在指定位置插入或删除元素 (如 add(int index, E e) , remove(Object o) , remove(int index)) , 时间复杂度就是$O(n)$
• 快速随机访问 : LinkedList 不支持快速随机访问
• 内存占用 : ArrayList 的内存浪费体现在 ArrayList 的末尾会预留空间, 而 LinkedList 的内存浪费体现在 LinkedList 的每个元素都要有一个前驱指针和一个后缀指针

ArrayList 核心源码

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空数组（用于空实例）。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //用于默认大小空实例的共享空数组实例。
    //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 保存ArrayList数据的数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList 所包含的元素个数
     */
    private int size;

    /**
     * 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //如果传入的参数大于0，创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果传入的参数等于0，创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //其他情况，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }

    /**
     * 默认无参构造函数
     * DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
     */
    public ArrayList(Collection<? extends E> c) {
        //将指定集合转换为数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
            // 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）
            if (elementData.getClass() != Object[].class)
                //将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 其他情况，用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    /**
     * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA
                    : Arrays.copyOf(elementData, size);
        }
    }
//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能，如果每次只扩充一个，
//那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。

    /**
     * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
     *
     * @param minCapacity 所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        //如果是true，minExpand的值为0，如果是false,minExpand的值为10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
        //如果最小容量大于已有的最大容量
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    // 根据给定的最小容量和当前数组元素来计算所需容量。
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果当前数组元素为空数组（初始情况），返回默认容量和最小容量中的较大值作为所需容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 否则直接返回最小容量
        return minCapacity;
    }

    // 确保内部容量达到指定的最小容量。
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

    /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }

    //比较minCapacity和 MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    /**
     * 返回此列表中的元素数。
     */
    public int size() {
        return size;
    }

    /**
     * 如果此列表不包含元素，则返回 true 。
     */
    public boolean isEmpty() {
        //注意=和==的区别
        return size == 0;
    }

    /**
     * 如果此列表包含指定的元素，则返回true 。
     */
    public boolean contains(Object o) {
        //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
        return indexOf(o) >= 0;
    }

    /**
     * 返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-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++)
                //equals()方法比较
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。.
     */
    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;
    }

    /**
     * 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。）
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // 这不应该发生，因为我们是可以克隆的
            throw new InternalError(e);
        }
    }

    /**
     * 以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
     * 返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
     * 因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）;
     * 返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。
     * 否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。
     * 如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。
     * （这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。）
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 新建一个运行时类型的数组，但是ArrayList数组的内容
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //调用System提供的arraycopy()方法实现数组之间的复制
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回此列表中指定位置的元素。
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    /**
     * 用指定的元素替换此列表中指定位置的元素。
     */
    public E set(int index, E element) {
        //对index进行界限检查
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        //返回原来在这个位置的元素
        return oldValue;
    }

    /**
     * 将指定的元素追加到此列表的末尾。
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

    /**
     * 在此列表中的指定位置插入指定的元素。
     * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }

    /**
     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
     */
    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);
        elementData[--size] = null; // clear to let GC do its work
        //从列表中删除的元素
        return oldValue;
    }

    /**
     * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
     * 返回true，如果此列表包含指定的元素
     */
    public boolean remove(Object o) {
        if (o == 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 remove method that skips bounds checking and does not
     * return the value removed.
     */
    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
    }

    /**
     * 从列表中删除所有元素。
     */
    public void clear() {
        modCount++;

        // 把数组中所有的元素的值设为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    /**
     * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。
     * 将任何后续元素移动到左侧（减少其索引）。
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex - fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

    /**
     * 检查给定的索引是否在范围内。
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * add和addAll使用的rangeCheck的一个版本
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 返回IndexOutOfBoundsException细节信息
     */
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    /**
     * 从此列表中删除指定集合中包含的所有元素。
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //如果此列表被修改则返回true
        return batchRemove(c, false);
    }

    /**
     * 仅保留此列表中包含在指定集合中的元素。
     * 换句话说，从此列表中删除其中不包含在指定集合中的所有元素。
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }


    /**
     * 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
     * 指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
     * 返回的列表迭代器是fail-fast 。
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index);
        return new ListItr(index);
    }

    /**
     * 返回列表中的列表迭代器（按适当的顺序）。
     * 返回的列表迭代器是fail-fast 。
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * 以正确的顺序返回该列表中的元素的迭代器。
     * 返回的迭代器是fail-fast 。
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

ArrayList 扩容机制

根据上面的源码, 我们可以确定的一个事实是: 当以无参数构造方法构造一个新的 ArrayList 时, 实际上初始化赋值的是一个空数组, 只有插入一个新元素的时候, ArrayList 的容量才会扩容到10

初始扩容后, 容量一次扩张到10, 之后每次扩容都会将容量扩张到原来的1.5倍

举个例子, 给一个空 ArrayList 添加一个元素, ArrayList 发生第一次扩容, 此时 ArrayList 的容量变为 10. 之后添加第2, 3, … 9, 10个元素, 都不会再扩容了. 直到添加第11个元素, 容量不足, ArrayList 自动扩容, 扩容到原来的 1.5 倍, 容量变为15. 这里注意, 如果原来的容量是奇数, 那么原容量乘以1.5会出现小数, 实际上扩容会把小数位丢掉.

(如果你有学过C++的话, 可以拿 ArrayList 的扩容机制和 Vector 的扩容机制做个对比, 总体来讲还是比较相似的)

在扩容之后, 根据上面的源码, 我们可知: 如果新容量大于 MAX_ARRAY_SIZE , 就会执行 hugeCapacity() 方法比较 minCapacity 和 MAX_ARRAY_SIZE, 如果 minCapacity 大于 MAX_ARRAY_SIZE , 那么新容量为 Integer.MAX_VALUE , 否则, 新容量大小为 Integer.MAX_VALUE - 8

扩容的本质是新建一个更大的 ArrayList , 然后将老的 ArrayList 的元素拷贝到新的 ArrayList . 拷贝有两个方法: Arrays.copyOf() 和 System.arraycopy() . 根据上面的源码可知, Arrays.copyOf() 实际上调用了 System.arraycopy() . 但两者存在区别, arraycopy() 需要目标数组, 将原数组拷贝到目标数组(重新定义的数组或者原数组), 可以选择拷贝的起点和长度以及放到目标数组的位置. copyOf() 是新建一个数组, 拷贝完成以后返回新数组

Vector

底层实现为Object[] 数组

LinkedList

底层实现为双向链表

LinkedList 插入删除的时间复杂度?

• 头部插入/删除, 尾部插入/删除:$O(1)$
• 除了头尾部的插入/删除:$O(n)$

LinkedList 为什么不能实现 RandomAccess ?

LinkedList 的底层数据结构是链表, 而链表中元素的内存位置不一定是连续的, 只能依赖于指针进行定位, 所以不能实现 RandomAccesss

LinkedList 源码分析

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

以上是 LinkedList 的类定义

由代码可知, LinkedList 继承了 AbstractSequentialList , 实现了 List , Deque , Cloneable , Serializable 接口

• List : 表明它是一个列表
• Deque : 继承自 Queue , 表明它具有双端插入/删除的特性
• Cloneable : 表明它具有拷贝能力, 可以进行深拷贝和浅拷贝操作
• Serializable : 表明它可以序列化, 也就是可以把对象转换为字节流进行存储或进行网络传输

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

以下是 LinkedList 的构造函数

// 创建一个空的链表对象
public LinkedList() {
}

// 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

插入元素使用 add() 方法. add() 方法有两个版本

• add(E e) , 将元素添加到 LinkedList 的末尾, 时间复杂度为 O(1)
• add(int index, E e) , 将元素添加到指定位置. 这需要先查找到对应位置, 然后再插入. 时间复杂度为$O(n)$

// 在链表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在链表指定位置插入元素
public void add(int index, E element) {
    // 下标越界检查
    checkPositionIndex(index);

    // 判断 index 是不是链表尾部位置
    if (index == size)
        // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
        linkLast(element);
    else
        // 如果不是则调用 linkBefore 方法将其插入指定元素之前
        linkBefore(element, node(index));
}

// 将元素节点插入到链表尾部
void linkLast(E e) {
    // 将最后一个元素赋值（引用传递）给节点 l
    final Node<E> l = last;
    // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空
    // 如果 l 是null 意味着这是第一次添加元素
    if (l == null)
        // 如果是第一次添加，将first赋值为新节点，此时链表只有一个元素
        first = newNode;
    else
        // 如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
        l.next = newNode;
    size++;
    modCount++;
}

// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;断言 succ不为 null
    // 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息
    final Node<E> pred = succ.prev;
    // 初始化节点，并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点
    if (pred == null)
        first = newNode;
    else
        // succ 节点前驱的后继引用指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

获取元素有三个函数, getFirst() , getLast() , get(int index)

• getFirst() : 获取链表的头节点元素, 时间复杂度$O(1)$
• getLast() : 获取链表的尾节点元素, 时间复杂度$O(1)$
• get(int index) : 获取指定位置元素, 时间复杂度$O(n)$

// 获取链表的第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 获取链表的最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

// 获取链表指定位置的元素
public E get(int index) {
  // 下标越界检查，如果越界就抛异常
  checkElementIndex(index);
  // 返回链表中对应下标的元素
  return node(index).item;
}

这里的核心在于下面这一段源码

// 返回指定下标的非空节点
Node<E> node(int index) {
    // 断言下标未越界
    // assert isElementIndex(index);
    // 如果index小于size的二分之一  从前开始查找（向后查找）  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历，循环向后查找，直至 i == index
        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;
    }
}

get(int index) 和 remove(int index) 都调用了这个方法来获取指定位置的节点

删除元素有5个方法, removeFirst() , removeLast() , remove(E e) , remove(int index) , clear()

• removeFirst() : 删除头节点. 时间复杂度$O(1)$
• removeLast() : 删除尾节点. 时间复杂度$O(1)$
• remove(E e) : 删除链表中首次出现的指定元素, 如果不存在就返回 false. 时间复杂度$O(n)$
• remove(int index) : 删除链表中指定位置的元素. 时间复杂度$O(n)$
• clear() : 删除链表中全部元素. 时间复杂度$O(n)$

// 删除并返回链表的第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除并返回链表的最后一个元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 删除链表中首次出现的指定元素，如果不存在该元素则返回 false
public boolean remove(Object o) {
    // 如果指定元素为 null，遍历链表找到第一个为 null 的元素进行删除
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 如果不为 null ,遍历链表找到要删除的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 删除链表指定位置的元素
public E remove(int index) {
    // 下标越界检查，如果越界就抛异常
    checkElementIndex(index);
    return unlink(node(index));
}

这里的核心在于 unlink() 方法

E unlink(Node<E> x) {
    // 断言 x 不为 null
    // 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 { // 如果前一个节点不为空
        // 将前一个节点的 next 指针指向当前节点的下一个节点
        prev.next = next;
        // 将当前节点的 prev 指针置为 null，，方便 GC 回收
        x.prev = null;
    }

    // 如果下一个节点为空，则说明当前节点是尾节点
    if (next == null) {
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else { // 如果下一个节点不为空
        // 将下一个节点的 prev 指针指向当前节点的前一个节点
        next.prev = prev;
        // 将当前节点的 next 指针置为 null，方便 GC 回收
        x.next = null;
    }

    // 将当前节点元素置为 null，方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink() 的逻辑如下

1. 首先获取待删除节点 x 的前驱和后继节点.
2. 判断待删除结点是否为头结点或尾节点
   • 如果 x 是头节点, 则将 first 指向 x 的后继节点
   • 如果 x 是尾节点, 则将 last 指向 x 的前驱节点
   • 如果 x 不是头节点也不是尾节点, 则进行下一步操作
3. 将待删除节点的前驱节点的后继指向待删除节点的后继节点, 断开 x 和 x.prev 的连接
4. 将待删除结点的后继节点的前驱指向待删除节点的前驱节点, 断开 x 和 x.next 的连接
5. 将待删除节点 x 的元素置空, 修改链表长度

关于遍历 LinkedList , 推荐使用 for-each 进行遍历

LinkedList<String> list;
list.add("Yonagi");
list.add("Hello");
list.add("World");

for (String s : list) {
    System.out.println(s);
}

LinkedList 遍历的核心其实是它的迭代器

// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 表示上一次调用 next() 或 previous() 方法时经过的节点；
    private Node<E> lastReturned;
    // 表示下一个要遍历的节点；
    private Node<E> next;
    // 表示下一个要遍历的节点的下标，也就是当前节点的后继节点的下标；
    private int nextIndex;
    // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
    private int expectedModCount = modCount;
    …………
}

头到尾方向的迭代

// 判断还有没有下一个节点
public boolean hasNext() {
    // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
    return nextIndex < size;
}
// 获取下一个节点
public E next() {
    // 检查在迭代过程中链表是否被修改过
    checkForComodification();
    // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 将 lastReturned 指向当前节点
    lastReturned = next;
    // 将 next 指向下一个节点
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

尾到头方向的迭代

// 判断是否还有前一个节点
public boolean hasPrevious() {
    return nextIndex > 0;
}

// 获取前一个节点
public E previous() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果没有前一个节点，则抛出异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 将 lastReturned 和 next 指针指向上一个节点
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

Set

Comparable 和 Comparator 的区别

Comparable 和 Comparator 接口都是 Java 中常见的用于排序的接口

• Comparable 接口实际上是出自 java.lang 包, 它有一个 compareTo(Object obj) 方法用于排序
• Comparator 接口实际上出自 java.util 包, 它有一个 compare(Object object1, Object object2) 方法用于排序

无序性和不可重复性的含义是什么

• 无序性是指存储的数据在底层数组中排列的顺序并非是按照数组索引增加进行排序, 而是根据哈希值进行排序
• 不可重复性是指添加元素通过 equals() 判断时, 返回 false.

比较 HashSet, LinkedHashSet, TreeSet

• HashSet , LinkedHashSet 和 TreeSet 都是接口 Set 的实现类, 都能保证元素的不可重复性, 且能保证线程安全
• HashSet , LinkedHashSet 和 TreeSet 的区别在于底层数据结构的不同. HashSet 是底层是哈希表 (基于 HashMap ); LinkedList 的底层是链表和哈希表, 且元素插入取出满足FIFO; TreeSet 的底层是红黑树, 元素是有序的, 排序的方式有自然排序和定制排序
• 底层数据结构的不同又导致它们的应用场景不同. HashSet 用于不需要保证元素插入和取出顺序的场景, LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景, TreeSet 用于支持对元素自定义排序规则的场景

Queue

Queue 和 Deque 的区别

Queue 是单端队列, 只能在一端插入元素, 在另一端删除元素

Queue 实现了 Collection 的接口, 根据容量问题而导致操作失败处理的不同, 分为两类: 一类是操作失败后抛出异常, 一类是操作失败后返回特殊值

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队头	remove()	poll()
查询队头元素	element()	peek()

(说说我个人的喜好, 我个人更喜欢用返回特殊值类型的方法, 抛出异常的方法就我个人而言, 无论是写题还是写项目代码都很少用到)

Deque 是双端队列, 在队头队尾都能插入删除

Deque 实现了 Queue 的接口, 增加了在队头插入/队尾删除的方法. 和 Queue 通用, Deque 根据容量问题而导致操作失败处理的不同, 也分为两类: 一类是操作失败后抛出异常, 一类是操作失败后返回特殊值

Deque 接口	抛出异常	返回特殊值
插入队头	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队头	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队头元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

实际上, Deque 还有 push() 和 pop() 方法, 用于模拟栈

ArrayDeque 与 LinkedList 的区别

• ArrayDeque 是基于可变长的数组和双指针来实现, 而 LinkedList 是基于链表实现
• ArrayDeque 不支持存储 NULL 数据, 而 LinkedList 支持
• ArrayDeque 插入时可能存在扩容过程, 均摊后时间复杂度为$O(1)$, LinkedList 虽不需要扩容, 但是每次插入数据时都需要申请新的空间, 均摊后性能更差

PriorityQueue

• PriorityQueue 利用了二叉堆的数据结构来实现, 底层使用可变长的数组来存储元素
• PriorityQueue 通过堆元素的上浮和下沉, 实现了在$O(\log n)$ 的时间复杂度下插入和删除堆顶元素
• PriorityQueue 是非线程安全的, 且不支持存储 NULL 值和 non-comparable 对象
• PriorityQueue 默认是小根堆, 但是可以接收一个 Comparator 作为构造参数, 自定义元素优先级

BlockingQueue

BlockingQueue 是一个接口, 继承自 Queue . BlockingQueue 阻塞的原因是当队列内没有元素的时候会一直阻塞, 直到有元素; 如果队列已满, 会等到队列有空间了再放入

BlockingQueue 常用于生产者-消费者模型

BlockingQueue 的实现类有哪些?

1. ArrayBlockingQueue : 使用数组实现的有界阻塞队列. 创建时需要指定容量大小, 并且支持公平和非公平两种方式的锁访问机制
2. LinkedBlockingQueue : 使用单向链表实现的可选有界阻塞队列, 在创建时可以指定容量, 如果不指定容量则默认为 Integer.MAX_VALUE . 和 ArrayBlockingQueue 一样, 支持公平和非公平两种方式的锁访问机制
3. PriorityBlockingQueue : 支持优先级排序的无界阻塞队列. 元素必须支持 comparable 或者在构造时指定 Comparator . 不支持插入 NULL 值
4. SynchronousQueue : 同步队列, 是一种不能存储元素的阻塞队列, 每个插入操作必须等待一个删除操作, 同理删除操作必须等待插入操作
5. DelayQueue : 延迟队列, 里面的元素只有经过了指定的延迟时间, 才能出队

ArrayBlockingQueue 和 LinkedBlockingQueue 的区别?

• ArrayBlockingQueue 基于数组实现; LinkedBlockingQueue 基于单向链表实现

• ArrayBlockingQueue 是有界的, 且创建时必须指定大小; LinkedBlockingQueue 是可选有界的, 创建时可以选择指定大小, 如果不指定则默认为 Integer.MAX_VALUE

• ArrayBlockingQueue 的锁是没有分离的, 也就是生产和消费都用的同一个锁; LinkedBlockingQueue 的锁是分离的, 生产和消费各有一个锁, 避免了消费者线程和生产者线程的锁争夺

• ArrayBlockingQueue 需要提前分配内存, 而 LinkedBlockingQueue 则是插入元素时申请新的内存空间