- 浏览: 255627 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
aquarion:
非常感谢,解决了我的问题
Perspective 自定义设置扩展点 -
zheng_zhen:
好文章,进一步问您一下,请问自己实现的run/debug如何能 ...
【原创】Eclipse Launcher (Run/Debug As 菜单扩展)实现 -
salever:
mwdnjupt 写道http://www.xeclipse. ...
浅析OSGI的bundle依赖 -
mwdnjupt:
http://www.xeclipse.com/?p=1165 ...
浅析OSGI的bundle依赖 -
Tom.X:
插件化、模块化应遵循高内聚、低耦合的原则,尽量不要在各bund ...
浅析OSGI的bundle依赖
本文同步发表在http://www.xeclipse.com/?p=1324上
在Java的List类型集合中,ArrayList和LinkedList大概是最常用到的2个了,细看了一下它们的实现,发现区别还是很大的,这里简单的列一下个人比较关心的区别。
类声明
ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
LinkedList
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
二者的定义有些相近,除了都实现List、Cloneable和Serializable以外,继承的类不一样,以及接口有细微的区别。
public abstract class AbstractSequentialList<E> extends AbstractList<E>
AbstractSequentialList也继承自AbstractList,它只是多了一些实现的方法,参照API的doc,这个类用于按顺序访问的List的实现,所谓顺序访问(sequential access),可以与随即访问(random access)的ArrayList对比去理解。
Deque是一个双向(double ended queue)的Queue的接口,因为这个接口的区别,LinkedList里实现的方法要比ArrayList多一些。
元素存储方式
ArrayList:采用数组方式
private transient Object[] elementData;
LinedList:采用链表
private transient Entry<E> header = new Entry<E>(null, null, null); private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
很好理解,从字面都可以理解出来,一个是数组实现,一个是链表实现。
元素添加
二者都有几个add()方法,
void add(E item) 向滚动列表的末尾添加指定的项。
void add(E item, int index) 向滚动列表中索引指示的位置添加指定的项。
先看看ArrayList的实现:
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
对于add(E e)方法,非常简单,首先确保数组容量,然后直接赋值。在不需要扩充数组容量的情况下,效率非常高,而一旦需要数组扩容,代价就会上升:
public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
因为它需要将已有的数组复制到新的数组里去。由此便可以想到一个提高add()效率的方法,在一开始尽量设定一个合理的数组容量,那么可以有效地减少数组的扩容和大量的复制。
对于add(int index, E e),比起add(E e),多一个可能的复制操作,这样才能保证在合理的位置插入新的元素。
LinkedList的实现:
public boolean add(E e) { addBefore(e, header); return true; } private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } /** * Returns the indexed entry. */ private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
粗略看起来要复杂一些,因为LinkedList同时还是一个Deque(JDK 1.6新添加的),所以它的实现也要兼顾双向队列。
下面从一个空的LinkedList开始,看看新的元素是如何添加进来的:
List<Integer> ints = new LinkedList<Integer>(); ints.add(1); ints.add(2); ints.add(3); System.out.println(ints); //[1, 2, 3]
下面一步一步看List内部header和元素之间的关系:
- 初始化: header.element = null; header.next=header.previous=header 这里是一个环状的结构,自己的p和n指针都指向自己
- 添加第一个元素“1”:header.element=null;header.next=1;header.previous=1; 2个元素相互连接
- 添加第二个元素“2” 这里很明显看来了,是一个环状结构
- 添加第三个元素“3” 既然是一个环状,干脆用圆形显示好了,貌似画的不太圆。。。
这里总结一下两种的差别:
- 对于元素的add()来说,LinkedList要比ArrayList要快一些,因为ArrayList可能需要额外的扩容操作,当然如果没有扩容,二者没有很大的差别
- 对于元素的add(int, element),对于LinkedList来说,代价主要在遍历获取插入的位置的元素,而ArrayList的主要代价在于可能有额外的扩容和大量元素的移动
- 小结:对于简单的元素添加,如果事先知道元素的个数,采用预置大小的ArrayList要更好,反之可以考虑LinkedList
元素移除
ArrayList的元素移除:
public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work }
remove(int)和remove(Object)两种方式的返回值是有区别的哦
对于ArrayList来说,主要是的仍然会有元素的移动(这里就是数组的复制),虽然采用的是System的arrayCopy,但是本质上还是复制的思路。还有一点需要注意的是,remove(Object)对null值进行单独处理,这里也说明ArrayList是可以存取null的。
LinkedList元素移除:
public E remove(int index) { return remove(entry(index)); } /** * Returns the indexed entry. */ private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }
这里的实现就是典型的链表删除的实现,其中有几个细节需要提一下:
- modCount的处理,这个变量是用来存储List的修改的次数的,仅仅存储添加和删除的操作此书,用来在Iterator中判断List的状态和行为,防止不同步的修改,抛出ConcurrentModificationException
- 通过索引访问元素的实现entry(int),这里有一个小细节,
if (index < (size >> 1)) {
如果元素的位置在前半段,那么通过next指针查找,否则通过previous指针查找。这一行代码有2个值得学习的地方,第一查找的优化,根据位置判断查找的方向,第二移位操作的运用。不得不佩服Bloch的编程功底。
小结一下:
删除操作中,LinkedList更有优势,一旦找到了删除的节点,它仅仅只是断开链接关系,并没有元素复制移动的行为,而ArrayList不可避免的又要进行元素的移动。
元素索引
indexOf(Object o) 回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。
ArrayList的实现:
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
LinkedList的实现:
public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; }
ArrayList:基于数组的遍历查找
LinkedList:基于链表的遍历查找
按照对象在内存中存储的顺序去考虑,数组的访问要比链接表快,因为对象都存储在一起。
遍历
基于以上的分析,可以得出,按照索引遍历,ArrayList是更好的选择,按照Iterator遍历,也许LinkedList会好一些。
反过来理解,如果是ArrayList,Iterator和index遍历都可以,如果是LinkedList,优先选择Iterator比较好。
其他
- 对于ArrayList和LinkedList, size() isEmpty() 这些都是常量计算,代价很低
- LinkedList实现了更多的方法,包括Queue,所以它也是一种队列
- 对于少量得元素临时存储,优先考虑ArrayList
- 频繁的添加和删除操作的时候,优先使用LinkedList
- 频繁的按索引访问遍历,优先使用ArrayList
发表评论
-
Java 技能树
2016-07-25 18:58 818java技能树 -
Java看书笔记
2014-08-07 17:15 728这一篇专用于一些日常的Java读书笔记 先写一点关 ... -
XStream和Jackson的使用优化
2012-12-17 11:09 0marker一下,需要研究一下这2种lib的使用方式。 -
java.lang.System类浅析
2012-07-25 09:58 1919本文同步发表在 http://www.xeclipse.com ... -
Linux/Unix下JFreeChart的NoClassDefFoundError问题
2012-07-04 14:51 1677最近遇到这样一个问题,使用JFreechart 1.0.13开 ... -
【转】常见的开源协议
2011-08-12 15:47 517Mozilla Public License ... -
【转】JDK发布版本时间以及代号
2011-06-20 14:02 1589已发行的版本: 版本号 名称 中文名 发布日期 ... -
最近的apache学习计划
2011-06-09 11:58 1242最近可能会要做一些apache相关的学习和开发工作,有一些pr ... -
Object类wait,notify,notifyAll的使用
2011-05-06 11:02 1472这三个方法是java的基础类Object中定义的。 w ... -
Java nio 整理整理
2011-02-25 17:17 1113看了看Java的nio类库,整理一下思路。 1,Buf ... -
Java 内存的那些事
2011-02-22 10:38 5024虽然Java屏蔽了一下内存 ... -
一些有用的Web Service 地址
2011-02-11 11:11 2220这里记录一下比较有用的Web Service 地址,可能会有用 ... -
【Java】利用HTML生成PDF之问题整理
2011-01-06 14:38 3957首先,技术为apache 的FOP ... -
【转】如何在java程序中设置文件为“隐藏”属性
2010-10-19 10:55 1634引自http://linshiquan.iteye.com/b ... -
【转】字符,字节和编码
2010-10-18 10:09 1215引言 “字符与编码” ... -
Effective Java 第2版 笔记
2010-08-18 15:45 1876Item 1;Consider static factoriy ... -
Java, 那些美妙的书籍
2010-08-10 15:39 7222整理一下最近看过或者比较有兴趣的Java书籍,以供大家参考 ... -
Object的equals()重写
2010-08-10 14:49 1575JDK1.6 API写道 public boolean e ... -
Object的equals()与hashCode()的关系
2010-08-10 14:37 0笔者在以前Java项目中使用findbugs工具时,经常遇到一 ... -
学习JVM 之 class文件校验器
2010-07-21 11:29 1983JVM中的class文件校 ...
相关推荐
总的来说,理解ArrayList和LinkedList的基本特性和应用场景,以及如何处理与之相关的安全性问题,是Java程序员必备的知识。通过深入学习和实践,可以更好地利用这些数据结构提升程序效率和质量。
测试ArrayList和LinkedList的add方法
在 Java 中,ArrayList 和 LinkedList 是两种常用的集合类,它们各自具有不同的特性和适用场景,主要体现在数据结构、访问效率和操作性能上。 1. 数据结构: - ArrayList 实现了一个动态数组,它内部是一个 Object...
ArrayList LinkedList Vector 区别 ArrayList、LinkedList、Vector 是 Java 中常用的数据结构实现类,它们都实现了 List 接口,但它们在存储方式、性能、线程安全性等方面有着不同特点。 首先,ArrayList 和 ...
【Java面试题】ArrayList和LinkedList区别
### 关于ArrayList与LinkedList的区别 在Java编程语言中,`ArrayList`与`LinkedList`都是`List`接口的具体实现类,用于存储元素集合。虽然它们都实现了同样的接口并且提供了相同的基本功能,但在内部实现机制、性能...
第二个代码示例则比较了从ArrayList和LinkedList中读取100000个元素的时间。在ArrayList中,由于元素存储连续,直接按索引访问几乎瞬间完成。然而,当使用LinkedList时,由于需要从头开始遍历链表,耗时显著增加。 ...
2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、删除数据时,LinkedList的效率比较高,因为ArrayList要移动数据。 ...
ArrayList、LinkedList和Vector是三种常见的动态数组实现,它们各自有特定的特性和使用场景。这里我们将深入探讨这三个类的性能对比,以及它们在不同操作下的表现。 ArrayList是基于动态数组实现的,它提供了随机...
05丨ArrayList还是LinkedList?使用不当性能差千倍.html
- **添加和删除**:对于在列表末尾的添加操作,ArrayList效率较高,因为只需简单地调整数组大小。但是,对于中间或开头的插入和删除,由于需要移动大量元素,效率较低。 - **线程安全**:ArrayList不是线程安全的...
在Java编程语言中,ArrayList、LinkedList和Vector是三种常见的动态数组实现,它们都在java.util包中,用于存储和管理对象的集合。这三个类都实现了List接口,提供了多种操作方法,但它们在内部实现和性能特性上有所...
ArrayList与LinkedList性能比较在java中 ArrayList和LinkedList是java中两个常用的实现List接口的类,它们之间的性能比较是一个非常重要的知识点。 首先,让我们来了解ArrayList和LinkedList的实现原理。ArrayList...
ArrayList和LinkedList是Java集合框架中两种重要的动态数组实现,它们都是List接口的实现类,但它们在存储和操作数据方面有着显著的区别。本文件"arraylist-linkedlist-test.zip"主要探讨了在执行添加和删除元素操作...
《ArrayList与LinkedList源码解析》 在Java编程中,ArrayList和LinkedList是两种常见的动态数组,它们都是Java集合框架的一部分,提供了对元素存储和操作的功能。本篇将深入探讨ArrayList和LinkedList的内部实现...
在Java编程语言中,ArrayList和LinkedList都是集合框架中两种重要的列表实现,它们分别基于不同的数据结构,具有不同的特性和性能特点。以下是对这两个类的详细分析: 1. 数据结构: - ArrayList是基于动态数组的...
### ArrayList、Vector、LinkedList 的区别与用法详解 在Java编程中,选择合适的数据结构对于程序的性能至关重要。本文将深入探讨ArrayList、Vector和LinkedList三种集合类的特点与使用场景,帮助开发者更好地理解...
ArrayList和LinkedList的比较与实现原理 在 Java 中,ArrayList 和 LinkedList 是两个常用的集合类,它们都是 List 接口的实现类,但它们之间有着鲜明的区别。今天,我们将深入探讨这两个集合类的实现原理和比较。 ...
Java 中 ArrayList 与 LinkedList 对比详情 在 Java 中,ArrayList 和 LinkedList 是两个常用的集合实现方式,它们都实现了 Collection 接口,但是它们之间存在着一些关键的差异。本文将通过实例对比 Java 中 ...
10.ArrayList 和LinkedList的区别.avi