[Java]ArrayList、LinkedList、Vector、Stack的比较

2023-02-25 21:14:39

一、介绍

先回顾一下List的框架图

[Java]ArrayList、LinkedList、Vector、Stack的比较

由图中的继承关系，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四个实现类。

  • AbstractList是一个抽象类，它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。

  • AbstractSequentialList 是一个抽象类，它继承于AbstractList。AbstractSequentialList 实现了“链表中，根据index索引值操作链表的全部函数”。

  • ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。

  • LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。

  • Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。

  • Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。

二、性能测试

在对ArrayList、LinkedList、Vector、Stack进行比较之前，我们先来对他们进行一个性能测试，结合源码和测试结果来对ArrayList、LinkedList、Vector、Stack进行详细的分析。



import java.util.*;

public class ListTest {

	private static final int COUNT = 100000;

    private static LinkedList linkedList = new LinkedList();

    private static ArrayList arrayList = new ArrayList();

    private static Vector vector = new Vector();

    private static Stack stack = new Stack();

    public static void main(String[] args) {

        // 换行符

        System.out.println();

        // 插入

        insertByPosition(stack) ;

        insertByPosition(vector) ;

        insertByPosition(linkedList) ;

        insertByPosition(arrayList) ;

        // 换行符

        System.out.println();

        // 随机读取

        readByPosition(stack);

        readByPosition(vector);

        readByPosition(linkedList);

        readByPosition(arrayList);

        // 换行符

        System.out.println();

        // 删除

        deleteByPosition(stack);

        deleteByPosition(vector);

        deleteByPosition(linkedList);

        deleteByPosition(arrayList);

    }

    // 获取list的名称

    private static String getListName(List list) {

        if (list instanceof LinkedList) {

            return "LinkedList";

        } else if (list instanceof ArrayList) {

            return "ArrayList";

        } else if (list instanceof Stack) {

            return "Stack";

        } else if (list instanceof Vector) {

            return "Vector";

        } else {

            return "List";

        }

    }

    // 向list的指定位置插入COUNT个元素，并统计时间

    private static void insertByPosition(List list) {

        long startTime = System.currentTimeMillis();

        // 向list的位置0插入COUNT个数

        for (int i=0; i<COUNT; i++)

            list.add(0, i);

        long endTime = System.currentTimeMillis();

        long interval = endTime - startTime;

        System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms");

    }

    // 从list的指定位置删除COUNT个元素，并统计时间

    private static void deleteByPosition(List list) {

        long startTime = System.currentTimeMillis();

        // 删除list第一个位置元素

        for (int i=0; i<COUNT; i++)

            list.remove(0);

        long endTime = System.currentTimeMillis();

        long interval = endTime - startTime;

        System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms");

    }

    // 根据position，不断从list中读取元素，并统计时间

    private static void readByPosition(List list) {

        long startTime = System.currentTimeMillis();

        // 读取list元素

        for (int i=0; i<COUNT; i++)

            list.get(i);

        long endTime = System.currentTimeMillis();

        long interval = endTime - startTime;

        System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms");

    }

}

得到的结果如下



Stack : insert 100000 elements into the 1st position use time：834 ms

Vector : insert 100000 elements into the 1st position use time：818 ms

LinkedList : insert 100000 elements into the 1st position use time：10 ms

ArrayList : insert 100000 elements into the 1st position use time：822 ms

Stack : read 100000 elements by position use time：5 ms

Vector : read 100000 elements by position use time：3 ms

LinkedList : read 100000 elements by position use time：6088 ms

ArrayList : read 100000 elements by position use time：2 ms

Stack : delete 100000 elements from the 1st position use time：857 ms

Vector : delete 100000 elements from the 1st position use time：835 ms

LinkedList : delete 100000 elements from the 1st position use time：6 ms

ArrayList : delete 100000 elements from the 1st position use time：849 ms

根据结果，可以很明显的看出ArrayList、LinkedList、Vector、Stack的性能有很大的区别。

操作 ArrayList LinkedList Vector Stack
读取 2ms 6088ms 3ms 5ms
插入 822ms 10ms 818ms 834ms
删除 849ms 6ms 835ms 857ms

读取：ArrayList > Vector > Stack > LinkedList

插入：LinkedList > Vector > ArrayList > Stack

删除：LinkedList > Vector > ArrayList > Stack

三、插入的分析

LinkedList

// 在index前添加节点，且节点的值为element

public void add(int index, E element) {

    addBefore(element, (index==size ? header : entry(index)));

}

// 获取双向链表中指定位置的节点

private Entry<E> entry(int index) {

    if (index < 0 || index >= size)

        throw new IndexOutOfBoundsException("Index: "+index+

                                            ", Size: "+size);

    Entry<E> e = header;

    // 获取index处的节点。

    // 若index < 双向链表长度的1/2,则从前向后查找;

    // 否则，从后向前查找。

    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;

}

// 将节点(节点数据是e)添加到entry节点之前。

private Entry<E> addBefore(E e, Entry<E> entry) {

    // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e

    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);

    // 插入newEntry到链表中

    newEntry.previous.next = newEntry;

    newEntry.next.previous = newEntry;

    size++;

    modCount++;

    return newEntry;

}

从中，我们可以看出：通过add(int index, E element)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index；找到之后，再插入一个新节点。

双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

ArrayList

// 将e添加到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++;

}

在这里面有一个非常耗时的操作

System.arraycopy(elementData, index, elementData, index + 1, size - index);

该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。

该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

Vector

public synchronized void insertElementAt(E obj, int index) {

        modCount++;

        if (index > elementCount) {

            throw new ArrayIndexOutOfBoundsException(index

                                                     + " > " + elementCount);

        }

        ensureCapacityHelper(elementCount + 1);

        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);

        elementData[index] = obj;

        elementCount++;

    }

    public void add(int index, E element) {

        insertElementAt(element, index);

    }

可以看到Vector和ArrayList是一样的，都调用了System.arraycopy。由于Stack和继承与Vector，就不仔细分析了。

四、查找的分析

LinkedList

LinkedList随机访问的代码

// 返回LinkedList指定位置的元素

public E get(int index) {

    return entry(index).element;

}

// 获取双向链表中指定位置的节点

private Entry<E> entry(int index) {

    if (index < 0 || index >= size)

        throw new IndexOutOfBoundsException("Index: "+index+

                                            ", Size: "+size);

    Entry<E> e = header;

    // 获取index处的节点。

    // 若index < 双向链表长度的1/2,则从前先后查找;

    // 否则，从后向前查找。

    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;

}

从中，我们可以看出：通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到要index位置的元素；找到之后再返回。

双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

ArrayList

// 获取index位置的元素值

public E get(int index) {

    RangeCheck(index);

    return (E) elementData[index];

}

private void RangeCheck(int index) {

    if (index >= size)

        throw new IndexOutOfBoundsException(

        "Index: "+index+", Size: "+size);

}

我们可以看到ArrayList直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找。

通过源码发现Vector和Stack的操作方式和ArrayList一样，这里就不详细分析了。

五、删除的分析

LinkedList

private E remove(Entry<E> e) {

    if (e == header)

        throw new NoSuchElementException();

    E result = e.element;

    e.previous.next = e.next;

    e.next.previous = e.previous;

    e.next = e.previous = null;

    e.element = null;

    size--;

    modCount++;

    return result;

}

由于删除了某一节点因此调整相应节点的前后指针信息，如下：

e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。

e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。

清空预删除节点：

e.next = e.previous = null;

e.element = null;

交给gc完成资源回收，删除操作结束。

与ArrayList比较而言，LinkedList的删除动作不需要“移动”很多数据，从而效率更高。

ArrayList

    public E remove(int index) {

        rangeCheck(index);

        modCount++;

        E oldValue = elementData(index);

        int numMoved = size - index - 1;

        if (numMoved > 0)

            System.arraycopy(elementData, index+1, elementData, index,

                             numMoved);

        elementData[--size] = null; // clear to let GC do its work

        return oldValue;

    }

恩，又是调用了System.arraycopy。

六、结论

操作 ArrayList LinkedList Vector Stack
读取 O(1) O(n) O(1) O(1)
插入 O(n) O(1) O(n) O(n)
删除 O(n) O(1) O(n) O(n)
  • ArrayList(实现动态数组)，查询快（随意访问或顺序访问），增删慢。整体清空快，线程不同步(非线程安全)。数组长度是可变的百分之五十延长
  • LinkedList（实现链表），查询慢，增删快。
  • Vector（实现动态数组），都慢，被ArrayList替代。长度任意延长。线程安全（同步的类，函数都是synchronized）
  • Stack（实现堆栈）继承于Vector，先进后出。

所以，快速访问ArrayList，快速增删LinkedList，单线程都可以用，多线程只能用同步类Vector

上一篇：查看LOV对应查询语句的研究


下一篇：无废话ExtJs 入门教程十三[上传图片：File]