Java | 集合框架之ArrayList，LinkedList
Java中，集合是存储对象最常用的一种方式
数组和集合类同为容器，有何不同？数组可以存储基本的数据类型，也可以储存对象，但长度固定；而集合的长度可动态改变，存储不同类型的对象。
一、集合框架
列出几个常用的接口和类
（1）Java集合框架主要两种容器：
Collection（集合）：存储元素集合
Map（图）：存储 key-value 键值对映射
这两种容器为集合框架的根接口，Java的集合类主要由这俩接口派生而出
（2）Collection接口派生出主要两个子接口：
List 接口（列表） ：元素存储有序，可存放重复元素
Set 接口（集）：元素存储无序，不可存放重复元素
（3）List 接口的实现类：
ArrayList 类：动态数组结构；查询速度快，直接通过索引查找，插入，删除，修改比较慢；线程不安全
LinkedList 类：链表结构；增删速度快，查询速度慢；线程不安全
Set 接口的实现类：
HashSet 类 ：存取速度快；通过hashCode()方法、== 和 equals() 方法来保证元素的唯一性
TreeSet 类：有序集合，对元素进行了排序；元素以二叉树的形式存放，通过Comparator.compareTo或者comparable.compare()方法来保证元素的唯一性
HashSet依赖于HashMap，TreeSet依赖于TreeMap，它们分别通过HashMap和TreeMap实现的。
（4）Map接口的实现类：
HashMap 类：数组和链表的结合，查询速度快，查找对象时通过哈希函数计算其位置；key和value存在一一对应关系，不能存在相同的key值，value值可以相同；允许存放null键，null值
TreeMap 类：有序的key-value集合，对键进行了排序，排序原理与TreeSet相同
二、常用集合类的特点分析
1、ArrayList 实现类
动态数组结构；查询速度快，直接通过索引查找，插入，删除，修改比较慢；线程不安全
（1）ArrayList 基本操作
1）添加操作
boolean add(E e) 在列表的末尾顺序添加元素
void add(int index, E element) 在指定的索引位置添加元素。索引位置必须介于0和列表中元素个数之间
2）查找操作
E get(int index) 返回指定索引位置处的元素
3）删除操作
E remove(int index) 从列表中删除指定索引位置元素
boolean remove(Object o) 从列表中删除元素
4）返回元素个数操作
int size() 返回列表中的元素个数
（2）遍历 ArrayList 实例
2、LinkedList 实现类
链表结构；增删速度快，查询速度慢；线程不安全
（1）LinkedList 常用操作
LinkedList 的 add() ，get() 等基本操作与 ArrayList 相同，还添加了一些常用的操作
1）void addFirst(E e) 在列表的首部添加元素
2）void addLast(E e) 在列表的末尾添加元素
3）E getFirst() 返回列表中的第一个元素
4）E getLast() 返回列表中的最后一个元素
5）E removeFirst() 删除并返回列表中的第一个元素
6）E removeLast() 删除并返回列表中的最后一个元素
3、ArrayList 与 LinkedList 的对比
ArrayList 查询速度比 LinkedList 快，但是插入元素的速度就不如LinkedList
例如 分别使用 ArrayList 和 LinkedList 添加元素，插入到第一个位置，分别计算出时耗进行对比
ArrayList 代码如下：
LinkedList 代码如下：
运行结果如下：
4、HashMap 实现类
三、总结
1、如果涉及到堆栈、队列等操作，应当考虑List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList
2、哈希表的操作，作为Key的对象要正确复写equals和hashCode方法
3、尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果将来要将ArrayList换成LinkedList时，客户端代码不用改变
4、List可以有类似数组的下标操作，且允许有相同的元素存在；Map是以键值对（KeyValue）的形式存在，不能存在相同的键
