首先看一下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时很有用。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/bobge/archive/2008/10/20/3110000.aspx
分享到:
相关推荐
一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要...
ArrayList、LinkedList、Vector区别简介。
Java集合系列(LinkedHashMap+LinkedList+ArrayList)
关于arraylist和linkedList的区别
1,ArrayList是数组的数据结构,LinkedList是链表的数据结构。 2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、...
JAVA LinkedList和ArrayList的使用及性能分析,这篇文章也是以JAVA List的总结。
1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList
JAVA链表的介绍(包含单项链表、双向链表)、LinkedList 与 ArrayList 比较、链表的基本操作、基本方法等
【Java面试题】ArrayList和LinkedList区别
测试ArrayList和LinkedList的add方法
列表ADT LinkedList,Doubly LinkedList和ArrayList的Python实现
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动 3.LinkedList不支持高效的随机元素访问 4.ArrayList的
ArrayList Vector LinkedList 区别与用法.
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
ArrayList-LinkedList ArrayList和LinkedList的完整演示。 我们如何添加,删除和遍历列表
10.ArrayList 和LinkedList的区别.avi
主要通过实例对Java中ArrayList与LinkedList进行了对比,需要的朋友可以参考下
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低。以前只直到数据结构会影响两者的查询效率,偶然间得知cpu缓存(硬件级别)也会有影响
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
arraylist 和linked list的时间复杂度