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 进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。
