list是个一唯的线性存储容器。我们可以把它比喻成一个竹签子，你可以把山楂、橘子串在上面，也可以把鸡翅、羊肉串在上面。吃的时候你可以从头、尾或者中间任何地方下口。
我们下面着重介绍下两个常用的实现，ArrayList和LinkedList。
ArrayList
arraylist顾明思议就是通过数组这种数据结构实现的list。数组的实现可以让它从任意的位置读取数据，也可以把数据写入数组的任意位置，但由于数组需要指定长度，所以会有扩容的问题。
LinkedList
LinkedList是通过链表实现的list。它的每个节点都会存储前一个和后一个节点的指针，每个list还会存储头和尾两个指针，所以它不能直接读取指定位置，但不会有扩容的问题。
list的主要场景有4个，顺序写、随机写、顺序读和随机读，下面我们从这4个场景模拟分析下这两种实现的不同点。
1.顺序写
ArrayList
//我们先初始化一个ArrayList, 这时arraylist会帮我们初始化一个长度为10的数组
List list = new ArrayList();
因为数组初始化必须指定长度，所以我们创建ArrayList时就会创建一个定长数组。
//这时我们把调用add方法把1写入到list中
list.add("A");
因为arraylist会保存index，所以add方法只是把数组的index位赋值为A，index加1就可以了。
//这时我们把调用add方法把B写入到list中
list.add("B");
填加B也是同理
LinkedList
//我们先初始化一个LinkedList，初始化时LinkedList并不会做什么
List list = new LinkedList();
//这时我们把调用add方法把A写入到list中
list.add("A");
这时的linkedlist的头指针和尾指针同时指向A
//我们再调用add方法把B写入到list中
list.add("B");
当调用add方法时，因为尾指针指向的是A节点，所以把A节点的next节点指向B，同时尾节点指向B
2.随机写
Arraylist
//我们再调用add方法把C写入到list中
list.add(2, "C");
所以ArrayList的随机写时间复杂度为O(n)
LinkedList
//我们再调用add方法把C写入到list中
list.add(2, "C");
linkedlist虽然不需要做节点移动，但是他要通过A、B、D节点这样遍历的方式找打插入的位置，所以时间复杂度也为O(n)
3.顺序读
Arraylist
在访问arraylist中任意一个元素的时候，因为底层实现是数组，所以都可以直接读取，时间复杂度为O(1)。
LinkedList
使用迭代器读取linkedlist，迭代器会维护一个当前节点的指针，所以也不需要循环查找，时间复杂度为O(1)。
4.随机读
Arraylist
arraylist的随机读通过底层数组支持，时间复杂度为O(1)。
LinkedList
linkedlist的随机读则只能通过从头循环遍历的方式查找，所以时间复杂度为O(n)
5.ArrayList的扩容
数组因为长度固定，所以当数组已经存满的时候就需要扩容。
如图所示，当D插入到arraylist时，发现数组已满，这时arraylist就会新建一个数组，长度是原来的2倍，并把原数组的数据移动到新数组，再把D插入到新数组中。
最后我们对比下这两个实现的时间复杂度。
时间复杂度
ArrayList
LinkedList
顺序写
O(1)
O(1)
随机写
O(n)
O(n)
顺序读
O(1)
O(1)
随机读
O(1)
O(n)
总结下我们应该如果选择
如果数据大小固定，需要随机读取使用ArrayList
如果数据大小不确定，不需要随机读取，使用LinkedList