java中有很多数据类型，以下数据类型都出于java.util包下且日常经常使用的，先介绍一下接口，接口可以很快的了解到这个数据结构的特性。

接口

List: 有序队列，如：ArrayList、LinkedList

Deque：双端队列，如：LinkedList

Map: 键值对的集合，如：HashMap、TreeMap

Set：不包含重复元素的集合，如：HashSet

Queue：队列，如：PriorityQueue，LinkedList

ArrayList

可以从上图中发现ArrayList肯定实现了List接口的方法，ArrayList是一个可以动态扩容的数组。一开始初始容量是10，当数组中容量大于一半的时候就自动进行扩容至原数组的两倍。

ArrayList提供了几个构造方法：

public ArrayList();//默认构造一个容量为10的数组
public ArrayList(int initialCapacity);//该方法可以设置数组的初始容量
public ArrayList(Collection<? extends E> c);//可以传一个集合类型的对象

接下来分析其关键方法的时间复杂度。

add()

其添加单个元素是线性的O(1)的时间复杂度，n个元素的添加的时间复杂度就是O(n)。添加元素是直接添加进数组的末尾。

add有很多个重构的方法

ArrayList<Integer> list= new ArrayList<>();
list.add(5);
list.add(4);
list.add(3);
list.add(2);
list.add(1);//add(E e);
System.out.println(list);//[5, 4, 3, 2, 1]

list.add(0,6);//add(int index,E e);
System.out.println(list);//[6, 5, 4, 3, 2, 1]

ArrayList<Integer> list2= new ArrayList<>();
list2.addAll(list);//public boolean addAll(Collection<? extends E> c);
System.out.println(list);//[6, 5, 4, 3, 2, 1]

ArrayList<Integer> list3= new ArrayList<>();
list3.add(10);
list3.add(15);
System.out.println(list3);
list3.addAll(1,list);// public boolean addAll(int index, Collection<? extends E> c);
System.out.println(list);//[6, 5, 4, 3, 2, 1]