【Java集合】List-蒲公英云

从上篇博客，我们知道了Java集合框架分为Collection和Map，此篇博客开始，将对集合框架中的List，Set，Queue和Map分别总结，进一步学习Java集合。本篇博客从List出发。

一. List的定义

List集合代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合允许加入重复元素，因为它可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引。

二. List的实现

1. List listA=new ArrayList();  
    底层数据结构是数组，查询快，增删慢;线程不安全，效率高
2. List listB=new Vector();  
    底层数据结构是数组，查询快，增删慢;线程安全，效率低
3. List listC=new LinkedList();  
    底层数据结构是链表，查询慢，增删快;线程不安全，效率高

三. ArrayList和Vector

ArrayList和Vector类都是基于数组实现的List类，其封装了一个动态的、允许再分配的Object\[\]数组。ArrayList或Vector对象使用initalCapacity参数来设置该数组的长度，当向ArrayList或Vector中添加元素超过了该数组的长度时，它们的initalCapacity会自动增加。
（一）ArrayList包含三个构造函数方法，如下：
1. ArrayList() ：Constructs an empty list with an initial capacity of ten.  
构造一个空数组，其初始容量默认为10.
2. ArrayList(Collection c) ：Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.  
按照集合迭代器返回的顺序构造包含指定集合元素的列表。
3. ArrayList(int initialCapacity) ：Constructs an empty list with the specified initial capacity.  
构造一个指定初始容量的空数组。
若调用add()方法，向一个数组中添加元素，会先调用ensureCapacityInternal()方法，该方法用来确保数组中是否还有足够容量。最后有个判断：如果剩余容量足够存放这个数据，则进行下一步，如果不够，则需要执行一个重要的方法：grow(int minCapacity) ，对数组进行扩容。  
所以说，ArrayList是一个动态扩展的数组，Vector也同样如此。如果开始就知道ArrayList或Vector集合需要保存多少个元素，则可以在创建它们时就指定initalCapacity的大小，这样可以提高性能。  
此外，ArrayList还提供了两个额外的方法来调整其容量大小：  
1. void ensureCapacity(int minCapacity): 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。  
2. void trimToSize():将此 ArrayList 实例的容量调整为列表的当前大小。
（二）ArrayList支持3种遍历方式：
1. 通过迭代器遍历 ：
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
2. 随机访问，通过索引值去遍历：
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) { value = (Integer)list.get(i); }
3. for循环遍历 ：
Integer value = null;
for (Integer integ:list) {
    value = integ;
}

遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低。

四. LinkedList

LinkedList类是List接口的实现类——这意味着它是一个List集合，可以根据索引来随机访问集合中的元素。除此之外，LinkedList还实现了Deque接口，可以被当作成双端队列来使用，因此既可以被当成“栈”来使用，也可以当成队列来使用。  
LinkedList的实现机制与ArrayList完全不同。ArrayList内部是以数组的形式来保存集合中的元素的，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色。  
（一）LinkedList包含两个构造函数方法，如下：
1. LinkedList() ：Constructs an empty list.  
构造一个空数组.
2. LinkedList(Collection c) ：Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.  
按照集合迭代器返回的顺序构造包含指定集合元素的列表。
LinkedList调用默认构造函数，创建一个链表。由于维护了一个表头，表尾的Node对象的变量。可以进行后续的添加元素到链表中的操作，以及其他删除，插入等操作。也因此实现了双向队列的功能，即可向表头加入元素，也可以向表尾加入元素.
（二）LinkedList支持多种遍历方式：
1.通过迭代器遍历LinkedList
2通过快速随机访问遍历LinkedList
3.通过for循环遍历LinkedList
4.通过pollFirst()遍历LinkedList
5.通过pollLast()遍历LinkedList
6通过removeFirst()遍历LinkedList
7.通过removeLast()遍历LinkedList

其中采用逐个遍历的方式，效率比较高。采用随机访问的方式去遍历LinkedList的方式效率最低。

五. ArrayList和LinkedList性能对比

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。ArrayList应使用随机访问(即，通过索引序号访问)遍历集合元素。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。LinkedList应使用采用逐个遍历的方式遍历集合元素。
如果涉及到“动态数组”、“栈”、“队列”、“链表”等结构，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍。
1. 对于需要快速插入，删除元素，应该使用LinkedList。  
2. 对于需要快速随机访问元素，应该使用ArrayList。  
3. 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)或支持并发的类。

六. ArrayList项目中的应用

之前在项目中遇到过一个需求，按规则分发人员，产品和测试理规则理了很久，而我开发时间其实很短，用编程语言来说，他们的规则，无非是我对几个list集合取并集，交集的操作，而这些操作，List都有实现的方法可直接用，allAll()，retainAll()，最后使用set去重。（set集合将在下篇博客进行详细总结）
List<String> allEmployeesList = new ArrayList<>();
        //根据客户绑定的专线查询对应的员工，分发该询价单
        List<String> dispatchEmployees = companyLineService.dispatchEmployeeByCompanyLine(customerId, companyIdItem);
        logger.info("-------所有绑定该专线员工集合：" + dispatchEmployees);
        //查询对应服务品牌的员工
        List<String> dispatchBrandEmployees = companyLineService.dispatchEmployeeByBrand(brand, companyIdItem);
        logger.info("-------所有绑定该品牌员工集合：" + dispatchBrandEmployees);
        //查询所有在用的员工
        List<String> dispatchUsedEmployee = companyLineService.queryUsedEmployees(companyIdItem);
        logger.info("--------所有在用的员工集合：" + dispatchUsedEmployee);
        //专线员工集合
        allEmployeesList.addAll(dispatchEmployees);
        if (allEmployeesList.size() == 0) {
            //若未查询到绑定专线的员工，则将绑定品牌的集合合并
            allEmployeesList.addAll(dispatchBrandEmployees);
        }
        //若专线+品牌集合都不为空，则取两个集合的差集
        if (dispatchEmployees.size() > 0 && dispatchBrandEmployees.size() > 0) {
            allEmployeesList.addAll(dispatchEmployees);
            allEmployeesList.retainAll(dispatchBrandEmployees);
        }
        //如果专线+品牌的员工集合为空，则合并其他所有在用的员工集合
        if (allEmployeesList.size() == 0) {
            allEmployeesList.addAll(dispatchUsedEmployee);
        }
        //set去除list中的重复元素
        Set<String> set = new HashSet<>(allEmployeesList);
        logger.info("去重后的所有员工id集合:" + set);
        return set;