java.util.LinkedList是双向链表，这个大家都知道，比如Java的基础面试题喜欢问ArrayList和LinkedList的区 别，在什么场景下用。大家都会说LinkedList随机增删多的场景比较合适，而ArrayList的随机访问多的场景比较合适。更进一步，LinkedList.remove(Object)方法的时间复杂度是什么？
           ArrayList 和LinkedList比较
          前者为什么查询效率高？ 后者为什么在增删就快呢？是如何进行增删改查的呢？效率是如何？

ArrayList Vector：以数组的方式存储，增 删速度慢， 改 查速度快。
ArrayList线程不安全，速度快。
Vector 线程安全，速度慢
ListedList 以单链表的方式存储，增删快， 查改慢。

这个就跟数据结构有关系了，可以参考一些数据结构中链表的知识
arraylist 顺序表，用数组的方式实现。想想数组要查询那个元素只给出其下标即可，所以才说arraylist随机访问多的场景比较合适。但是如果删除某个元素比如第 i 个元素，则要将 i 之后的元素都向前移一位以保证顺序表的正确，增加也是一样，要移动多个元素。要多次删除增加的话是很低效的。
而LinkedList是双向链表，注意是链表。要查询只能头结点开始逐步查询，没有什么给出下标即可直接查询的便利，需要遍历。但是，如果要增加后删除一个元素的话，只需要改变其前后元素的指向即可。不需要像arraylist那样整体移动。所以才说多用于增删多的场合
表达能力有限。。想要比较严谨的解释可以看一看一些参考书上的相关内容。

这个要看楼主数据结构的功底了
ArrayList底层实现的数据结构是数组
LinkedList底层实现的数据结构是链表
数组在内存中是连续的
在某个下标想插入一个值的时候
需要把这个下标上的值与他后面所有的值都往后挪一位
如果在存储的数据过多的情况下
你在前面插入一个值后面所有的值都会往后挪一位
挪位操作是通过交换来完成的，所以时间和资源都浪费在交换和挪位上了
但是他的查询是很快的，也是相对链表来说的

链表由于在内存中不一定连续，他是用指针串起来的一个一个的节点
想插入数据直接改变一下指针的指向
（在java里不会直接操作指针，这是底层的实现，你也可理解为引用，其实就是根据一个地址取里面的值）
比如想在a节点后面插入一个p指向的节点b
只需要
b.next=a.next
a.next=p
就直接插入了一个数据
它的插入和删除的效率比数组高的不是一点半点
存储的数据越多愈能显示出来差距
但是链表的查询是很麻烦的
他需要从头至尾一个节点一个节点的遍历
数据越多查询效率就越低
数组恰恰相反
这就是为什么ArrayList 和LinkedList一个查询效率高，一个插入删除效率高的原因
希望能对你有所帮助。。。

ArrayList:底层数据结构是数组结构。线程不安全的。所以ArrayList的出现替代了Vector.但是查询的速度很快.
             查询快是因为其内部封装的数组都有索引，在迭代过程中，根据索引来查询。
LinkedList:底层是链表数据结构。线程不安全的，同时对元算的增删操作效率很高
        增删快是因为链表在增删时不用像数组那样，根据索引挨个向后查找，他是元素就近链接，增加删除都是直接进行查找，而数组呢还要一个一个的对比。
                               

是数组的方式，查询只需要角标便可找到对应的元素，替换的话也只需要对角标对应的元素进行操作，但是往中间插入或者删除的话会让数组长度发生变化，如果在第x个元素删除的话，以后的元素都要往前移一位，插入的话以后的原有元素都要后移一位。
LinkedList 可以看下图，他是双向链表，每个元素头和尾都有一个指针指向上一个和下一个元素，插入和删除还有替换都只需要改变头尾的指针指向就可以了，但是查询则需要从头开始找顺序下去一直到找到为止。
C:\Documents and Settings\Administrator\桌面ArrayList