Java集合复习之List

1.ArrayList

1.1.ArrayList集合特点

• [可容纳类型] ：只能容纳引用对象（基本类型需要转换为封装类）
• [线程安全] ：线程不安全
• [底层实现] ：底层使用数组实现，基于其实现方式，有以下特点：初始化时需要声明长度，超出长度需要扩容，不适合频繁的移动、删除元素，搜索元素快
• [元素可重复] ：可重复

1.2 ArrayList排序

• 自定义排序：list.sort(new Comparator(){自定义排序规则})
• 快速排序 ，使用Collections.sort(list)

1.3 ArrayList扩容

• ArrayList内部使用Arrays.copyOf(elementData, newCapacity)进行扩容，此方法每次都会创建一个新的newCapacity长度的数组，因此扩容的空间复杂度为O(n),时间复杂度为O(n)

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        // oldCapacity 是旧容量，newCapacity 是新容量
        int oldCapacity = elementData.length;
        //这里进行了扩容，通过位运算，将旧容量扩大为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //检查新容量是否小于最小需要容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再次检查新容量是否大于最大容量
        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();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

1.4 ArrayList序列化

• ArrayList底层是由数组实现，并且可以动态扩容，因此，保存元素的数组不一定全部会使用，也就不需要全部进行序列化
• ArrayList中提供了writeObject()和readObject来序列化或反序列化数组中有保存元素的那一部分，具体使用如下

//序列化
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

//反序列化
ArrayList list = new ArrayList();
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(file));
ois.readObject(list);

2.Vector

2.1.Vector集合特点

• [可容纳类型] ：只能容纳引用对象（基本类型需要转换为封装类）
• [线程安全] ：线程安全（通过方法上添加syncronized关键字保证）
• [底层实现] ：底层使用数组实现，与ArrayList一样，有以下特点：初始化时需要声明长度，超出长度需要扩容，不适合频繁的移动、删除元素，搜索元素快
• [元素可重复] ：可重复

3.LinkedList

3.1.LinkedList集合特点

• [可容纳类型] ：只能容纳引用对象（基本类型需要转换为封装类）
• [线程安全] ：线程不安全
• [底层实现] ：底层使用链表实现，有以下特点：不用声明长度，搜索元素慢，但是插入、删除速度快。
• [元素可重复] ：可重复

4.ArrayList、Vector、LinkedList对比

• 这三种类型的集合都是有序集合，即遍历时输出顺序和保存顺序一致。在功能上表现也很相似，都提供了根据角标进行查询、删除、插入元素操作，都提供迭代器进行遍历等。但是由于底层设计的区别，在性能、线程安全方面存在差异
• Vector是线程安全的，ArrayList和LinkedList都是线程不安全的。Vector的线程安全是通过在方法上添加syncronized关键字来实现的，如果不是一定要保证线程安全，不推荐使用。
• LinkedList 底部使用链表实现，它不需要像ArrayList、Vector一样需要去动态调整容量
• Vector和ArrayList的扩容机制略有不同：Vector初始大小为10，当保存元素数组大小不够时，会根据capacityIncrement进行区分，如果capacityIncrement大于0，则将数组大小扩充为现有的size+capacityIncrement，如果capacityIncrement小于0，则扩容为size*2

5.list的使用场景分析

• Vector和ArrayList底层使用动态数组实现，天然适合随机查询和迭代遍历操作，但是在删除、添加元素时，性能较差。
• LinkedList 进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。