关于ArrayList和LinkedList

Question

你自己看他们的实现就知道了
ArrayList用数组来存，所以读取很快，但是如果你要在中间添加或者删除一个，就要移动后面的所有元素，所以很慢
LinkedList是链表，访问某一节点必须从头或者尾部一个一个找过去，所以读取慢，但是要添加或者删除的话，只需要添加或者解除相邻元素的链接关系就行了

Answer 1

大多数情况下LinkedList插入比ArrayList还要慢
LinkedList逐个遍历实在太耗时了
只有插入表头才优势明显

Answer 2

ArrayList改慢主要是指删除和插入慢，因为ArrayList基于数组。删除和插入操作必然需要把原来的数组复制到新的数组里面，新的数组，删除/或者插入了那个被删/插的元素。每删/插一次，就要复制一次原来的数组。LinkedList慢，主要是get(int)操作慢。你可以看他的源码。假设LinkedList长度100，
list.get(10) 等价于 list.head.next.next.next...10次next。
list.get(49)，也就是size/2是最慢最慢的。
超过size/2以后，list.get(50)等价于list.tail.previous.previous..........类推。

Answer 3

arrayList 底层是 数组，插入和删除 比较慢，原因：例如 插入，加入数组长度10，插入位置5，那么从5开始，后面的每个元素都要往后移动一位，所以速度慢。删除同理。
linkedList  底层数据结构是链表，针对插入和删除，只需要修改 插入位置元素的 指针即可。例如 要在第5为插入一个newElement，只需将5.next 指向 newElement  ，newElement .next 指向 第6个元素（原来表的）。所以插入和删除会比较快速

Answer 4

对于元素的add()来说，LinkedList要比ArrayList要快一些，因为ArrayList可能需要额外的扩容操作，当然如果没有扩容，二者没有很大的差别
对于元素的add(int, element),对于LinkedList来说，代价主要在遍历获取插入的位置的元素，而ArrayList的主要代价在于可能有额外的扩容和大量元素的移动
对于简单的元素添加，如果事先知道元素的个数，采用预置大小的ArrayList要更好，反之可以考虑LinkedList删除操作中，LinkedList更有优势，一旦找到了删除的节点，它仅仅只是断开链接关系，并没有元素复制移动的行为，而ArrayList不可避免的又要进行元素的移动。按照索引遍历，ArrayList是更好的选择，按照Iterator遍历，也许LinkedList会好一些。反过来理解，如果是ArrayList，Iterator和index遍历都可以，如果是LinkedList，优先选择Iterator比较好。对于ArrayList和LinkedList， size() isEmpty() 这些都是常量计算，代价很低
LinkedList实现了更多的方法，包括Queue，所以它也是一种队列
对于少量得元素临时存储，优先考虑ArrayList
频繁的添加和删除操作的时候，优先使用LinkedList
频繁的按索引访问遍历，优先使用ArrayList