`
salever
  • 浏览: 254184 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

ArrayList与LinkedList的简单比较

阅读更多

本文同步发表在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
分享到:
评论

相关推荐

    ArrayList和Linkedlist1

    总的来说,理解ArrayList和LinkedList的基本特性和应用场景,以及如何处理与之相关的安全性问题,是Java程序员必备的知识。通过深入学习和实践,可以更好地利用这些数据结构提升程序效率和质量。

    测试ArrayList和LinkedList的add方法

    测试ArrayList和LinkedList的add方法

    Java中ArrayList和LinkedList区别 时间复杂度 与空间复杂度1

    在 Java 中,ArrayList 和 LinkedList 是两种常用的集合类,它们各自具有不同的特性和适用场景,主要体现在数据结构、访问效率和操作性能上。 1. 数据结构: - ArrayList 实现了一个动态数组,它内部是一个 Object...

    ArrayList LinkedList Vector区别

    ArrayList LinkedList Vector 区别 ArrayList、LinkedList、Vector 是 Java 中常用的数据结构实现类,它们都实现了 List 接口,但它们在存储方式、性能、线程安全性等方面有着不同特点。 首先,ArrayList 和 ...

    【Java面试题】ArrayList和LinkedList区别

    【Java面试题】ArrayList和LinkedList区别

    关于arraylist和linkedList的区别

    ### 关于ArrayList与LinkedList的区别 在Java编程语言中,`ArrayList`与`LinkedList`都是`List`接口的具体实现类,用于存储元素集合。虽然它们都实现了同样的接口并且提供了相同的基本功能,但在内部实现机制、性能...

    合理运用ArrayList与LinkedList

    第二个代码示例则比较了从ArrayList和LinkedList中读取100000个元素的时间。在ArrayList中,由于元素存储连续,直接按索引访问几乎瞬间完成。然而,当使用LinkedList时,由于需要从头开始遍历链表,耗时显著增加。 ...

    Arraylist与LinkedList区别

    2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、删除数据时,LinkedList的效率比较高,因为ArrayList要移动数据。 ...

    ArrayList LinkedList Vector性能对比

    ArrayList、LinkedList和Vector是三种常见的动态数组实现,它们各自有特定的特性和使用场景。这里我们将深入探讨这三个类的性能对比,以及它们在不同操作下的表现。 ArrayList是基于动态数组实现的,它提供了随机...

    05丨ArrayList还是LinkedList?使用不当性能差千倍.html

    05丨ArrayList还是LinkedList?使用不当性能差千倍.html

    比较ArrayList、LinkedList、Vector1

    - **添加和删除**:对于在列表末尾的添加操作,ArrayList效率较高,因为只需简单地调整数组大小。但是,对于中间或开头的插入和删除,由于需要移动大量元素,效率较低。 - **线程安全**:ArrayList不是线程安全的...

    ArrayList LinkedList Vector性能测试

    在Java编程语言中,ArrayList、LinkedList和Vector是三种常见的动态数组实现,它们都在java.util包中,用于存储和管理对象的集合。这三个类都实现了List接口,提供了多种操作方法,但它们在内部实现和性能特性上有所...

    java 中ArrayList与LinkedList性能比较

    ArrayList与LinkedList性能比较在java中 ArrayList和LinkedList是java中两个常用的实现List接口的类,它们之间的性能比较是一个非常重要的知识点。 首先,让我们来了解ArrayList和LinkedList的实现原理。ArrayList...

    arraylist-linkedlist-test.zip

    ArrayList和LinkedList是Java集合框架中两种重要的动态数组实现,它们都是List接口的实现类,但它们在存储和操作数据方面有着显著的区别。本文件"arraylist-linkedlist-test.zip"主要探讨了在执行添加和删除元素操作...

    ArrayList-LinkedList-源码.rar

    《ArrayList与LinkedList源码解析》 在Java编程中,ArrayList和LinkedList是两种常见的动态数组,它们都是Java集合框架的一部分,提供了对元素存储和操作的功能。本篇将深入探讨ArrayList和LinkedList的内部实现...

    Java中ArrayList和LinkedList区别

    在Java编程语言中,ArrayList和LinkedList都是集合框架中两种重要的列表实现,它们分别基于不同的数据结构,具有不同的特性和性能特点。以下是对这两个类的详细分析: 1. 数据结构: - ArrayList是基于动态数组的...

    ArrayList Vector LinkedList 区别与用法.

    ### ArrayList、Vector、LinkedList 的区别与用法详解 在Java编程中,选择合适的数据结构对于程序的性能至关重要。本文将深入探讨ArrayList、Vector和LinkedList三种集合类的特点与使用场景,帮助开发者更好地理解...

    当面试官问我ArrayList和LinkedList哪个更占空间时,我这么答让他眼前一亮

    ArrayList和LinkedList的比较与实现原理 在 Java 中,ArrayList 和 LinkedList 是两个常用的集合类,它们都是 List 接口的实现类,但它们之间有着鲜明的区别。今天,我们将深入探讨这两个集合类的实现原理和比较。 ...

    java中ArrayList与LinkedList对比详情

    Java 中 ArrayList 与 LinkedList 对比详情 在 Java 中,ArrayList 和 LinkedList 是两个常用的集合实现方式,它们都实现了 Collection 接口,但是它们之间存在着一些关键的差异。本文将通过实例对比 Java 中 ...

    10.ArrayList 和LinkedList的区别.avi

    10.ArrayList 和LinkedList的区别.avi

Global site tag (gtag.js) - Google Analytics