黑马程序员技术交流社区

标题: Arraylist,Vector,linkedList之间的性能和区别？ [打印本页]

作者: 王虎 时间: 2012-10-11 10:02
标题: Arraylist,Vector,linkedList之间的性能和区别？
以前面试时遇到过一个公司上机让我写一个操作数据存取的程序，结果写的不是很好，有谁知道他们使用的原理请用简短代码或精练语言说明一下

作者: 张丽 时间: 2012-10-11 10:24
ArrayList是1.2版本以后出现的，Collection集合框架中的，底层用的是数组存储结构，并且是不同步的，其判断元素唯一性的方法是equals()方法。其里面的contains()方法也是用的equal()方法。其取出集合元素的方法是使用迭代器。其改查元素快，增删慢。Vector是1.0版本的，最早期的集合，是同步的，其取出元素的方法是用的枚举。
LinkedList也是1.2版本的，是不同步的，其底层使用的是链表结构，与ArrayList不同的是，ArrayList在迭代的时候，不能对集合元素进行增删，而用LinkedList的LinkIterator迭代器，就可以进行迭代时对元素进行增删。其增删元素快，改查慢。这是我的理解，希望能帮你。

作者: 方志亮 时间: 2012-10-11 10:51
List 元素有序(存储顺序和取出顺序一致)，可重复。
   |--ArrayList
底层数据结构是数组，线程不安全。
增删慢，查询快。
   |--Vector
底层数据结构是数组，线程安全。
增删慢，查询快。但是，线程安全，效率就低。所以查询也慢。
   |--LinkedList
底层数据结构是链表，线程不安全。
增删快，查询慢。

作者: 草上飞 时间: 2012-10-22 22:32
Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。
  当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间

ArrayList和Vector在从指定位置取得元素，从容器的末尾增加和删除元素都非常的有效，所有的这些操作都能在一个常数级的时间(O(1))内完成。
但是从一个其他的位置增加和删除一个元素就显得颇为费时，差不多需要的时间为O(n-i)，这里的n代表元素个数，i代表要增加和删除的元素所在的位置。
这些操作需花费更多的时间，因为你需要挨个移动i和更高位置的元素。那么，以上这些到底说明了什么呢？

  这意味着，如果你取得一个元素，或者从数组末尾增加或删除一个元素的话，随便你使用Vector和ArrayList。
如果你想要对数组内容做其他操作的话，那么就为自己好另一个容器吧。比喻说，LinkedList可以在常数级时间(O(1))内为任意一个位置的元素增加和删除。
但是，取得一个元素，会稍微慢一点，时间要用O(i) ，这个i是元素的位置。通过ArrayList也是很简单的，因为你可以简单使用一个索引，而不是构造一个iterator 。
LinkedList也为每个插入的元素建立一个内部对象。所以，你也必须知道，同时产生了垃圾对象。

作者: 李铁 时间: 2012-10-22 23:23
ArrayList和Vector采用数组方式存储数据，此数组元素大于实际存储的数组以便增加和插入元素，它们都允许直接按序列号索引元素，但是插入涉及数组元素移动等内存操作，
所以牵引快而插入数据慢。
Vector由于使用了synchroniaed方法，通常性能比ArrayList差。
LinkedList采用双向链表实现存储，按序号索引需要向前或向后遍历，但是插入数据只是要记住本项的前后项即可，所以插入速度较快。

作者: fdiskfix 时间: 2012-10-22 23:25
ArrayList->Vector->LinkedList
这是我使用的选择顺序,通常情况下ArrayList的效率要略高一些

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2