首页 > 编程知识 正文

arraylist用法(什么时候用arraylist和linkedlist)

时间:2023-05-06 15:49:47 阅读:68648 作者:1198

1.ArrayList实现基于动态数组的数据结构,LinkedList是基于链表的数据结构。

2 .关于随机访问get和set,ArrayList觉得优于链接列表。 这是因为链接列表会移动指针。

3 .关于添加和删除操作的add和remove,由于ArrayList移动数据,所以LinedList具有优势。

ArrayList和LinkedList是存储一系列“对象引用”(references )的两个集合类。 例如,可以使用ArrayList存储一系列字符串和整数。 那么,ArrayList和LinkedList的性能有什么不同呢? 我应该什么时候使用ArrayList? 我应该什么时候再使用链接列表?

1 .时间复杂性

首先,ArrayList的内部实现基于基本对象数组,因此在使用get方法访问列表中的任何元素(随机访问)时,它比链接的列表更快。 LinkedList的get方法从列表的一端到另一端依次检查。 LinkedList没有访问列表中指定元素的快速方法。

假设您有一个大列表,其中的元素已经按顺序排列。 此列表可以是阵列列表类型,也可以是链接列表类型。 现在,让我们来对该列表进行二分搜索。 比较列表是ArrayList和链接列表的查询速度。 看看下面的程序:

package com.mangocity.test;

import java.util.LinkedList;

import java.util.List;

import java.util.Random;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

公共类测试列表. {

公共静态金融int n=50000;

公共静态列表值;

静态. {

Integer vals[]=new Integer[N];

Random r=new Random (;

for(intI=0,currval=0; I

vals=newinteger(currval;

currval=r.nextint(100 ) 1;

}

values=Arrays.aslist(vals );

}

静态持续时间(列表列表) . {

long start=system.current time millis (;

for(intI=0; I

intindex=collections.binary search (lst,values.get(I );

If (索引!=i )

system.out.println('***错误*** ' );

}

return system.current time millis (-start;

}

publicstaticvoidmain (字符串args [ ] )…{

system.out.println('Arraylist消耗时间: ' timelist ) new ArrayList (values ) );

system.out.println ('链接列表消耗时间: ' time list ' new linked list ) values ) );

}

}

我得到的输出是ArrayList的消耗时间: 15

链接列表的消耗时间: 2596

这是

个结果虽然不一定,但基本上阵列列表的时间明显小于链接列表的时间。 因此,在这种情况下不应该使用链接列表。 二分搜索法

的随机访问(

访问(对于策略,链接列表不支持高速随机访问。 随机访问一个链接列表所需的时间与此列表的大小成比例

请参阅。 相应地,在ArrayList中随机访问所花的时间是一定的。

这是

是否表明ArrayList总是比链接列表性能更好? 这不一定。 在某些情况下,链接列表可能比阵列列表更好。 一些

算法在LinkedList中实现更高效。 例如,使用Collections.reverse方法反转列表可以提高性能。

通过这样的例子,我们有一个列表,可以进行大量的插入和删除操作。 在这种情况下为LinkedL

ist就是一个较好的选择。请看如下一个极端的例子,我们重复的在一个列表的开端插入一个元素:

package com.mangocity.test;

import java.util.*;

public class ListDemo {

static final int N=50000;

static long timeList(List list){

long start=System.currentTimeMillis();

Object o = new Object();

for(int i=0;i

list.add(0, o);

return System.currentTimeMillis()-start;

}

public static void main(String[] args) {

System.out.println("ArrayList耗时:"+timeList(new ArrayList()));

System.out.println("LinkedList耗时:"+timeList(new LinkedList()));

}

}

这时我的输出结果是:ArrayList耗时:2463

LinkedList耗时:15

和前面一个例子的结果截然相反,当一个元素被加到ArrayList的最开端时,所有已经存在的元素都会后移,这就意味着数据移动和复制上的开销。相反

的,将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录,然后调整两个连接。在LinkedList的开端增加一个元素的开销

是固定的,而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

二.空间复杂度

在LinkedList中有一个私有的内部类,定义如下:

private static class Entry {

Object element;

Entry next;

Entry previous;

}

个Entry对象reference列表中的一个元素,同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的

LinkedList对象将有1000个链接在一起的Entry对象,每个对象都对应于列表中的一个元素。这样的话,在一个LinkedList结构中将

有一个很大的空间开销,因为它要存储这1000个Entity对象的相关信息。

ArrayList

使用一个内置的数组来存储元素,这个数组的起始容量是10.当数组需要增长时,新的容量按如下公式获得:新容量=(旧容量*3)/2+1,也就是说每一次

容量大概会增长50%。这就意味着,如果你有一个包含大量元素的ArrayList对象,那么最终将有很大的空间会被浪费掉,这个浪费是由

ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素,数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配,将

会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素,我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在

ArrayList分配完毕之后去掉浪费掉的空间。

三.总结

ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:

性能总结:

-     add()操作     delete()操作      insert操作         index取值操作     iterator取值操作

ArrayList/Vector/Stack

极优

极优

LinkedList

极优

1.

对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言,主要是在内部数组中增加一

项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。

2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。

3.LinkedList不支持高效的随机元素访问。

4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说:当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比

较好的性能;开心的书包的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

java中ArrayList 、List区别

List集合

List继承自Collection接口。List是一种有序集合,List中的元素可以根据索引(顺序号:元素在集合中处于的位置信息)进行取得/删除/插入操作。

跟Set集合不同的是,List允许有重复元素。对于满足e1.equals(e2)条件的e1与e2对象元素,可以同时存在于List集合中。当然,也有List的实现类不允许重复元素的存在。

同时,List还提供一个listIterator()方法,返回一个ListIterator接口对象,和Iterator接口相比,ListIterator添加元素的添加,删除,和设定等方法,还能向前或向后遍历。

List跟Collection的关系:

java.util.Collection [I]

+--java.util.List [I]

+--java.util.ArrayList [C]

+--java.util.LinkedList [C]

+--java.util.Vector [C]

+--java.util.Stack [C]

List接口的实现类主要有ArrayList,LinkedList,Vector,Stack等。

父子关系.

List是一个接口,ArrayList继承与这个接口并实现了它.

用的时候一般都用ArrayList.没用过List. 可以这么用:List list = new ArrayList();

Collection接口

Collection

是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些

Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java

SDK提供的类都是继承自Collection的“子接口”如List和Set。

所有实现Collection接口的类都必须提供两

个标准的构造 函数:无参数的构造函数用于创建一个空的Collection,有一个

Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后

一个构造函数允许用户复制一个Collection。

如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:

Iterator it = collection.iterator(); // 获得一个迭代子

while(it.hasNext()) {

Object obj = it.next(); // 得到下一个元素

}

由Collection接口派生的两个接口是List和Set。

List接口

List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。

和下面要提到的Set不同,List允许有相同的元素。

了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个

ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,

还能向前或向后遍历。

实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。

LinkedList类

LinkedList

实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在

LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:

List list = Collections.synchronizedList(new LinkedList(...));

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。

size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性 。

个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法

并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样,ArrayList也是非同步的 (unsynchronized)。

总结

如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。

尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。

附:

看过wmdhb写的《Java程序性能优化:让你的Java程序更快、更稳定》,里面介绍的是:

新增:

如果经常需要在list中任意位置插入元素那么考虑用LinkedList

删除:

删除尾部的元素时,ArrayList与LinkedList几乎一样。删除中间和头部的元素时,ArrayList性能很差,但删除中间元素时LinkedList比ArrayList还差。总的来说就是如果经常删除尾部和中间的元素,可以用ArrayList,而经常删除头部和尾部的元素最好用LinkedList。

查询:

3种遍历中,for(int i=...;e;e){}这种遍历对LinkedList很慢,而其他两种遍历方法对ArrayList与LinkedList速度几乎一样。

注:e代表表达式;

相关文章:

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。