本文来源于:http://www.blogjava.net/mstar/archive/2006/01/26/29272.html
首先看一下LinkedList和ArrayList的继承关系。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Queue<E>, Cloneable, Serializable
两者都实现List接口,前者实现RandomAccess接口,后者实现Queue接口。
ArrayList
ArrayList其实是包装了一个数组 Object[],当实例化一个ArrayList时,一个数组也被实例化,当向ArrayList中添加对象是,数组的大小也相应的改变。这样就带来以下有缺点:
快速随即访问 你可以随即访问每个元素而不用考虑性能问题,通过调用get(i)方法来访问下标为i的数组元素。
向其中添加对象速度慢 当你创建数组是并不能确定其容量,所以当改变这个数组时就必须在内存中做很多事情。
操作其中对象的速度慢 当你要想数组中任意两个元素中间添加对象时,数组需要移动所有后面的对象。
LinkedList
LinkedList是通过节点直接彼此连接来实现的。每一个节点都包含前一个节点的引用,后一个节点的引用和节点存储的值。当一个新节点插入时,只需要修改其中保持先后关系的节点的引用即可,当删除记录时也一样。这样就带来以下有缺点:
操作其中对象的速度快 只需要改变连接,新的节点可以在内存中的任何地方
不能随即访问 虽然存在get()方法,但是这个方法是通过遍历接点来定位的所以速度慢。
一些结论:
当一些被定义好的数据需要放到与数组对应的List中,ArrayList是很好的选择,因为它可以动态变化,但是不要在整个应用程序用频繁的使用。当你要很方便的操作其中的数据而不用随即访问时LinkList是很好的选择。如果你要频繁随即访问建议使用数组。
另外一个我没有提到的是关于Queue。LinkedList的实现使其具有很好的可扩展性,可以方便的在开始和结尾添加删除节点。所以LinkedList很适合用来实现Queue和Stack,尽管在Java5种已经有了一个Stack的实现。
以上是原文中的观点,但是在回复中也有人反对:
LinkedList有以下缺陷:
对象分配-每添加一项就分配一个对象
回收垃圾-对象分配的结果
随即访问慢-设计上的原因
添加删除慢-因为首先要找到位置
应该使用LinkedList的情况非常少。大多数的建议使使用LinkedList是错误的。
JDK的Stack就是用数组来实现的。
在多数时间里你并不是向List中间添加数据,而是向在结尾添加,这样的操作ArrayList表现的很好。
LinkedList在实现Queue时很有用。
然后是原文作者提供的一些数据:
addFirst() to array list took 1422
addFirst() to linked list using general methods took 16
addFirst() to linked list using linked list methods took 16
addLast() to array list took 16
addLast() to linked list using general methods took 15
addLast() to linked list using linked list methods took 0
addMiddleTest() to array list took 735
addMiddleTest() to linked list using general methods took 11688
addMiddleTest() to linked list using linked list methods took 8406
removeFirst() to array list took 1422
removeFirst() to linked list using general methods took 0
removeFirst() to linked list using linked list methods took 0
removeLast() to array list took 0
removeLast() to linked list using general methods took 0
removeLast() to linked list using linked list methods took 0
removeMiddle() to array list took 734
removeMiddle() to linked list using general methods took 7594
removeMiddle() to linked list using linked list methods took 7719
fetchFirst() to array list took 0
fetchFirst() to linked list using general methods took 0
fetchFirst() to linked list using linked list methods took 0
fetchLast() to array list took 16
fetchLast() to linked list using general methods took 0
fetchLast() to linked list using linked list methods took 0
fetchMiddle() to array list took 15
fetchMiddle() to linked list using general methods took 9156
fetchMiddle() to linked list using linked list methods took 9234
分享到:
相关推荐
10.ArrayList 和LinkedList的区别.avi
Java面试题10.ArrayList LinkedList.mp4
51. ArrayList LinkedList Set HashMap介绍.txt
10.ArrayList和LinkedList基于动态数组,连续内存存储,适合下标访问(随机访问)扩容机制:因为数组长度固定,超出长度存数据时需要新建数组,然后
1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList
一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要...
ArrayList-LinkedList-源码.rar
ArrayList、LinkedList、Vector区别简介。
ArrayList Vector LinkedList 区别与用法.
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动 3.LinkedList不支持高效的随机元素访问 4.ArrayList的
ArrayList、Vector、LinkedList 的区别.docx
该文件内容主要是关于LinkedList在新增/删除元素时效率是否比 ArrayList 高,对比插入和删除时需要花费的时间
1,ArrayList是数组的数据结构,LinkedList是链表的数据结构。 2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、...
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
测试ArrayList和LinkedList的add方法
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
关于arraylist和linkedList的区别
Java集合系列(LinkedHashMap+LinkedList+ArrayList)
【Java面试题】ArrayList和LinkedList区别
05丨ArrayList还是LinkedList?使用不当性能差千倍.html