List

总体概况：

迭代器：
Iterable接口：
上图中可以看出Iterable是java集合的*接口之一，其中包含如下方法：

// 由实现类自己来实现，返回一个Iterator对象
Iterator<T> iterator();
// 此处的遍历使用的是增强for循环，底层是用对iterator()方法的调用来代替增强的for循环以得到一个Iterator对象，然后调用next和hasNext进行遍历
default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
// 提供了默认的并行迭代器实现，Stream的并行流就利用了这个
default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

Iterator接口：
主要方法如下：

// 是否存在下一个元素
boolean hasNext();
// 获取下一个元素
E next();
// 从迭代器中删除当前元素
default void remove() {
    throw new UnsupportedOperationException("remove");
}

例子_ArrayList：

@Override
public Iterator<E> iterator() {
        return new Itr();
    }

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}

List：
ArrayList（数组）和LinkedList（链表）都是线程不安全的，vector所有方法都是原子的（原子操作：在操作完毕之前不会线程调度器中断）Vector同步容器，对所有容器状态的访问都串行化，严重降低了并发性；当多个线程竞争锁时，吞吐量严重下降；
java5.0之后提供了多种并发容器来改善同步容器的性能，如ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentSkipListMap等；
ArrayList:
基于数组实现，查找某个元素速度快（数组首地址+偏移量offset）的特点导致它修改元素的效率高，但是它添加和删除指定元素的速度慢。
List使用建议：
1.不要在增强for循环里对其进行修改，否则会抛出ConcurrentModificationException，虽然在Itr类中会将expectedModCount = modCount;但是在增强foe循环中调用的remove方式是ArrayList本身的remove方法该方法中只是简单的modCount++;并没有将最新值同步给Itr中的expectedModCount 所以在判断hasNext为true后进行checkForComodification检查时就会抛异常（但是倒数第二个元素除外，应为hasNext为false，不会进入next方法中即不会进行checkForComodification检查）
2.List接口中的equals方法定义在父类AbstractList中，它不关心List的具体实现类。只要所有的元素相等，并且长度也相等就表明两个List是相等的，与具体的容量类型无关，无论是Vector还是ArrayList只要满足上述条件都会返回相等，Set和Map也同理。
3.ArrayList数组实现了RandomAccess接口（随机存取接口），这也就标志着ArrayList是一个可以随机存取的列表。RandomAccess和Cloneable、Serializable一样，都是标志性接口，不需要任何实现，只是用来表明其实现类具有某种特质的实现了RandomAccess则表明这个类可以随机存取，对我们的ArrayList来说也就标志着其数据元素之间没有关联，即两个位置相邻的元素之间没有相互依赖和索引关系，可以随机访问和存储。Java中的foreach语法是iterator（迭代器）的变形用法。对于ArrayList，需要先创建一个迭代器容器，然后屏蔽内部遍历细节，对外提供hasNext、next等方法。问题是ArrayList实现了RandomAccess接口，已表明元素之间本来没有关系，可是，为了使用迭代器就需要强制建立一种互相“知晓”的关系，比如上一个元素可以判断是否有下一个元素，以及下一个元素是什么等关系，这也就是通过foreach遍历耗时的原因。LinkedList用下标进行遍历时采用的是一次2分法进行遍历。所以ArrayList用下标（index）方式遍历，LinkedList用增强for循环（forEach）或者迭代器进行遍历效率最好。
4.Arrays.asList返回的是一个内部ArrayList，该类虽然继承了AbstractList（这个类型的add和remove方法都直接抛了个异常，交由子类趋去实现）但是它没有实现其add和remove方法所以进行添加，修改，删除时都会报错。
5.subList方法是由AbstractList实现的，它返回的SubList类也是AbstractList的子类，其所有的方法如get、set、add、remove等都是在原始列表上的操作，它自身并没有生成一个数组或是链表，也就是子列表只是原列表的一个视图（View），所有的修改动作都反映在了原列表上。他非常有用比如：删除一个集合中20-30的元素：list.subList(20, 30).clear();，生成字列表试图后不要操作原列表了否则会抛checkForComodification异常。
6.实现集合的随机读取的几种方式：
Collections.swap(list, i, randomPosition);

Collections.shuffle(list);
数组使用建议：
1.性能要求较高的场景中使用数组替代集合。比如对100个正式求和，用数组int[100]进行累加相比List<Integer>省去了拆箱的步骤而且进本类型存储在栈中效率更好
2.变成数组：

pubblic static <T> T[] expandCapacity(T[] datas, int newLen) {

    // 不能是负值

    newLen = newLen<0?0:newLen;

    // 生成一个新数组，并浅拷贝(引用类型只是简单拷贝其引用)原值
，
    return Arrays.copyOf(datas, newLen);

}

3.对一串数字去重后取第二小的：数组不能剔除重复数据，但Set集合却是可以的，而且Set的子类TreeSet还能自动排序。

public static int getSecond(Integer[] data){

    //转换为列表

    List<Integer> dataList = Arrays.asList(data);

    //转换为TreeSet，删除重复元素并升序排列

    TreeSet<Integer> ts = new TreeSet<Integer>(dataList);
    //取得比最大值小的最大值，也就是老二了

    return  ts.lower(ts.last());

}

4.asList入参是个变长泛型化参数：

// 输出结果为1，基本类型不能泛型化，整个arr作为一个参数
int[] arr = {1,2,3,4};
// 输出结果为4
Integer[] arr = {1,2,3,4};
List list = Arrays.asList(arr);
System.out.println(list.size());

Queue：
队列是一种先进先出的数据结构,不支持随机访问的数据结构。JDK实现了两套，一套是以ConcurrentLinkedQueue为代表的高性能非阻塞队列，另一套以BlockingQueue接口为代表的阻塞队列，两种都继承自Queue。
非阻塞队列：
ConcurrentLinkedQueue：*队列，不允许null，无锁采用CAS算法实现。
阻塞队列：
当生产者向队列添加元素但队列已满时，生产者会被阻塞；当消费者从队列移除元素但队列为空时，消费者会被阻塞

为什么要使用阻塞队列？

关键在于生产者和消费者可能不会（几乎肯定不会）保持相同的速度，比如，当生产者的速度快于消费者的速度时，队列会越来越大。相比之下，阻塞队列只允许生产者的速度在一定速度上超过消费者的速度，但不会超过很多。使用如下：

add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞

常见队列：

ArrayBlockingQueue：
基于数组的有界阻塞队列，内部维护了一个定长的数组缓存队列，没有实现读写分离（读写一个锁），即生产和消费不能同时进行，长度必需要定义，可以指定先进先出或先进后出，很多场合非常适用。

LinkedBlockingQueue：
基于链表的*阻塞队列，但也可以制定长度，不指定*，内部维护了一个链表缓存队列，实现了读写分离（读写两个锁）

SynchronousQueue：
没有缓冲的队列，生产者的数据直接被消费者消费，add方法必须在take方法之后调用否则会抛异常，add只是将数据直接丢给阻塞等待的线程而并非直接向队列里添加数据

PriorityQueue：
基于优先级的*阻塞队列，（优先级的判断通过构造函数传入的Compator对象来决定，在调用take方法时触发排序并非添加时）

DelayQueue:
带有延迟时间的*阻塞队列，其中的元素只有延迟时间到了，才能从队列中获取该元素。其中的元素必须实现Delayed接口

TransferQueue：
生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费，新添加的transfer方法用来实现这种约束。阻塞就是发生在元素从一个线程transfer到另一个线程的过程中，它有效地实现了元素在线程之间的传递