LinkedList PK ArrayList

LinkedList 和 ArrayList 都实现了List 接口
Collection结构
插入操作
默认顺序插入，两者的时间都是O(1)
指定index插入元素：1、ArrayList 最坏情况性能O(n),最好情况是（容量不够时，需要扩容）O(1) ArrayList扩容机制
2.LinkedList 在都是O(1)

删除操作
1、ArrayList 删除操作最坏情况下性能是O(n)，最好O(1)，删除最后一个元素性能O(1)
2、LinkedList 删除元素操作时性能都是O(1)
搜索操作
ArrayList 搜索性能为O(1)
LinkedList 搜索性能差一些，为O(n/2)
总结

• LinkedList因为要同时维护邻居节点的两个指针，内存消耗大于ArrayList
• 频繁操作插入删除的时候，LinkedList性能好
• 在频繁操作搜索时，ArrayList性能好
• 她们线程都是不安全的。可以通过下面方法实现线程安全

List list = Collections.synchronizedList(new ArrayList()); …
synchronized(list) {
Iterator i = list.iterator(); // 必须在 synchronized 块中
while (i.hasNext())
foo(i.next()); }