ArrayList和LinkedList的区别
推荐于2018-02-27
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。 这一点我做了实验。在分别有200000条“记录”的ArrayList和LinkedList的首位插入20000条数据,LinkedList耗时约是ArrayList的20分之1。
for(int m=0;m<20000;m++){
linkedlist.add(m,null); //当在200000条数据之前插入20000条数据时,LinkedList只用了1125多ms.这就是LinkedList的优势所在
}
long time4 = new Dte().getTime();
System.out.print("batch linkedlist add:");
System.out.println(time4 - time3);
for(int n=0;n<20000;n++){
arraylist.add(n, null); //当在200000条数据之前插入20000条数据时,ArrayList用了18375多ms.时间花费是arraylist的近20倍(视测试时机器性能)
}
long time5 = new Date().getTime();
System.out.print("batch arraylist add:");
System.out.println(time5 - time4);
4.查找操作indexOf,lastIndexOf,contains等,两者差不多。
5.随机查找指定节点的操作get,ArrayList速度要快于LinkedList.
这里只是理论上分析,事实上也不一定,ArrayList在末尾插入和删除数据的话,速度反而比LinkedList要快。我做过一个插入和删除200000条数据的试验。
long time1 = new Date().getTime();
String s1 = (String) linkedlist.get(100000);// 总记录200000,linkedlist加载第100000条数据耗时15~32ms不等
long time2 = new Date().getTime();
System.out.println(time2 - time1);
String s2 = (String) arraylist.get(100000);// 总记录200000,linkedlist加载第100000条数据耗时0ms
long time3 = new Date().getTime();
System.out.println(time3 - time2);
/*分别insert200000条数据到linkedlist和arraylist
*由于是在末尾插入数据,arraylist的速度比linkedlist的速度反而要快
*/
public static void insertList(LinkedList linklist, ArrayList arraylist) {
long time1 = new Date().getTime();
System.out.println(time1);
for (int i = 0; i < 200000; i++) {
linklist.add(i, "linklist" + i);
}
long time2 = new Date().getTime();
System.out.println(time2 - time1);
for (int j = 0; j < 200000; j++) {
arraylist.add(j, "arraylist" + j);
}
long time3 = new Date().getTime();
System.out.println(time3 - time2);
}
/*delete linkedlist和arraylist中的200000条数据
*由于是在末尾删除数据,arraylist的速度比linkedlist的速度反而要快
*/
public static void deleteList(LinkedList linklist, ArrayList arraylist) {
long time1 = new Date().getTime();
System.out.println(time1);
for (int i = 199999; i >= 0; i--) {
linklist.remove(i);
}
long time2 = new Date().getTime();
System.out.println(time2 - time1);
for (int j = 199999; j >= 0; j--) {
arraylist.remove(j);
}
long time3 = new Date().getTime();
System.out.println(time3 - time2);
}
public static void main(String args[]) {
LinkedList linkedlist = new LinkedList();
ArrayList arraylist = new ArrayList();
insertList(linkedlist, arraylist);
//以下代码省略
插入:
LinkedList 578ms
ArrayList 437ms
删除:
LinkedList 31ms
ArrayList 16ms
ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处。
List 接口的大小可变 数组的实现,位于API文档的 java.util.ArrayList<E>。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的 数组的大小。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行,也就是说,添加 n 个 元素需要 O(n) 时间。其他所有操作都以线性时间运行。与用于 LinkedList 实现的常数因子相比,此实现的常数因子较低。
每个 ArrayList 实例都有一个容量。该容量是指用来存储列表 元素的 数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加 元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加 元素会带来分摊固定时间开销那样简单
在添加 大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
Java中ArrayList和LinkedList区别
ArrayList和LinkedList的大致区别如下:
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
上代码:
1 static final int N=50000;
2 static long timeList(List list){
3 long start=System.currentTimeMillis();
4 Object o = new Object();
5 for(int i=0;i<N;i++) {
6 list.add(0, o);
7 }
8 return System.currentTimeMillis()-start;
9 }
10 static long readList(List list){
11 long start=System.currentTimeMillis();
12 for(int i=0,j=list.size();i<j;i++){
13
14 }
15 return System.currentTimeMillis()-start;
16 }
17
18 static List addList(List list){
19 Object o = new Object();
20 for(int i=0;i<N;i++) {
21 list.add(0, o);
22 }
23 return list;
24 }
25 public static void main(String[] args) {
26 System.out.println("ArrayList添加"+N+"条耗时:"+timeList(new ArrayList()));
27 System.out.println("LinkedList添加"+N+"条耗时:"+timeList(new LinkedList()));
28
29 List list1=addList(new ArrayList<>());
30 List list2=addList(new LinkedList<>());
31 System.out.println("ArrayList查找"+N+"条耗时:"+readList(list1));
32 System.out.println("LinkedList查找"+N+"条耗时:"+timeList(list2));
33 }
当我们在集合中装5万条数据,测试运行结果如下:
显然我们可以看出ArrayList更适合读取数据,linkedList更多的时候添加或删除数据。
2016-04-17 · 百度知道合伙人官方认证企业
LinkedList 采用的将对象存放在独立的空间中,而且在每个空间中还保存下一个链接的索引 但是缺点就是查找非常麻烦 要丛第一个索引开始
Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现。
也许最重要的不同是Hashtable的方法是同步的,而HashMap的方法不是。这就意味着,虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable,但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法,它创建一个线程安全的Map对象,并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时,你不能切断Hashtable中的同步(比如在一个单线程的应用程序中),而且同步增加了很多处理费用。
第三点不同是,只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key,但任意数量的条目可以是空的value。这就是说,如果在表中没有发现搜索键,或者如果发现了搜索键,但它是一个空的值,那么get()将返回null。如果有必要,用containKey()方法来区别这两种情况。
一些资料建议,当需要同步时,用Hashtable,反之用HashMap。但是,因为在需要时,HashMap可以被同步,HashMap的功能比Hashtable的功能更多,而且它不是基于一个陈旧的类的,所以有人认为,在各种情况下,HashMap都优先于Hashtable。
关于Properties
有时侯,你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子,如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法,但Java提供了另外一种方法。
Java.util.Properties类是Hashtable的一个子类,设计用于String keys和values。Properties对象的用法同Hashtable的用法相象,但是类增加了两个节省时间的方法,你应该知道。
Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反,用来读取文件,并设定Properties对象来包含keys和values。
注意,因为Properties扩展了Hashtable,你可以用超类的put()方法来添加不是String对象的keys和values。这是不可取的。另外,如果你将store()用于一个不包含String对象的Properties对象,store()将失败。作为put()和get()的替代,你应该用setProperty()和getProperty(),它们用String参数。
广告 您可能关注的内容 |