List

ArrayList、LinkedList、Vector 实现了 List 接口。其中 Vector 是 ArrayList 的古老实现类，最重要的还是 ArrayList 和 LinkedList。那么 ArrayList 和 LinkedList 的区别有什么？

是否线程安全：二者都是线程不安全的，不保证并发访问。
底层数据结构：ArrayList 底层采用数组，而 LinkedList 底层采用双向链表。
插入和删除：ArrayList 除了在尾部插入和删除的时间复杂度为 O(1)，其余时间复杂度均为 O(n)。LinkedList 在头尾插入和删除的时间复杂度为 O(1)，其余位置因为需要先定位元素再删除，时间复杂度为 O(n)。
是否支持随机访问：ArrayList 支持快速的随机访问，而 LinkedList 不支持。
内存占用：ArrayList 的空间浪费体现在容量大于长度的情况，LinkedList 的空间浪费体现在每一个元素都要记录前驱和后继。

一般都会使用 ArrayList，需要用到 LinkedList 的场景几乎可以用 ArrayList 代替。

ArrayList

扩容机制

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

后续每一次扩容时，扩容为之前的 1.5 倍。下面是扩容核心方法：

/**
 * 要分配的最大数组大小
 */
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;

    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
    // 如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 对minCapacity和MAX_ARRAY_SIZE进行比较
    // 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    // 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Set

Set 之间的不同：

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

Queue

Queue 为单端队列，一端插入数据一端删除数据。Deque 为双端队列，头部和尾部既可以插入也可以删除。

优先队列

基于小根堆实现（或者接受一个 Comparator 支持自定义排序），实现基于优先级的队列，优先级高的先出队。

阻塞队列

阻塞队列（Blocking Queue）类似于 golang 中的 channel，当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

Java 中常用的阻塞队列实现类有以下几种：

ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是，它仅支持非公平的锁访问机制。
PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队，基于优先队列实现。
……

Dawn's Blogs

Java面试之集合 (2) List Set Queue