但行好事  莫问前程

ArrayList,LinkedList,Vector,Stack之间的区别

一,线程安全性

Vector、Stack:线程安全

ArrayList、LinkedList:非线程安全

二,实现方式

LinkedList:双向链表

ArrayList,Vector,Stack:数组

三,容量扩展方面

由于ArrayList和Vector(Stack继承自Vector,只在Vector的基础上添加了几个Stack相关的方法,故之后不再对Stack做特别的说明)使用数组实现,当数组长度不够时,其内部会创建一个更大的数组,然后将原数组中的数据拷贝至新数组中。

//ArrayList  
public boolean add(E e) {  
    ensureCapacity(size + 1);  
    elementData[size++] = e;  
    return true;  
}  

public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        int newCapacity = (oldCapacity * 3)/2 + 1;  
        //如果这次扩展不能满足要求,那就直接用minCapacity  
        if (newCapacity < minCapacity)  
            newCapacity = minCapacity;  
        // minCapacity is usually close to size, so this is a win:  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}  

如需扩展,则每次至少扩展至(原长度*3)/2 + 1

//Vector  
public synchronized void addElement(E obj) {  
    modCount++;  
    ensureCapacityHelper(elementCount + 1);  
    elementData[elementCount++] = obj;  
}  

private void ensureCapacityHelper(int minCapacity) {  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object[] oldData = elementData;  
        int newCapacity = (capacityIncrement > 0) ?  
            (oldCapacity + capacityIncrement) : (oldCapacity * 2);  
        //如果这次扩展不能满足要求,那就直接用minCapacity  
        if (newCapacity < minCapacity) {  
            newCapacity = minCapacity;  
        }  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}  

如果在创建Vector时不指定capacityIncrement(自动扩展长度)的值,如需扩展,则每次至少扩展至原长度的2倍

四,效率方面

这里仅仅比较ArrayList和LinkedList之间的效率差异

1. 查询

ArrayList直接通过下标进行定位

//ArrayList  
public E get(int index) {  
    RangeCheck(index);//检查下标是否超过数组长度  
    return (E) elementData[index];  
}  

LinkedList则需要进行遍历,平均遍历次数应为n/4

//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;  
    //size >>1 相当于size/2  
    //由于LinkedList由双向链表实现,故从离得较近的一端开始遍历更快  
    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;  
}  

对于指定位置查询,由于可以通过下标直接进行定位,ArrayList的速度远快于LinkedList,但是如果都为首尾位置的查询,情况会大为不同,因为LinkedList也是

可以直接定位到首尾位置的

//LinkedList  
public E getFirst() {  
    if (size==0)  
        throw new NoSuchElementException();  
    return header.next.element;  
}  

public E getLast()  {  
    if (size==0)  
        throw new NoSuchElementException();  
    return header.previous.element;  
}  

此时ArrayList和LinkedList的效率相同

2,插入

对于ArrayList,指定位置插入有可能首先需要对数组容量进行扩展,之后还有可能导致数组中的数据需要顺次移动(代码中通过数组拷贝实现,避免了数据一个

一个的移动),极端情况下插入一个数据将进行两次数组拷贝。

//ArrayList  
public void add(int index, E element) {  
    if (index > size || index < 0)  
        throw new IndexOutOfBoundsException(  
                "Index: "+index+", Size: "+size);  
    ensureCapacity(size+1);  //如必要,将对数组容量进行扩展  
    System.arraycopy(elementData, index, elementData, index + 1,  
            size - index);  
    elementData[index] = element;  
    size++;  
}  

如果不指定插入位置,则插入至数组末端,此时只需考虑可能的数组容量扩展对性能带来的影响

//ArrayList  
public boolean add(E e) {  
    ensureCapacity(size + 1);   
    elementData[size++] = e;  
    return true;  
}  

由于LinkedList是由链表实现的,并没有指定位置插入的方法,即便如此,一切也显得如此美好

/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;  
}  

当然了,LinkedList可以直接将数据插入至首尾

//LinkedList  
public void addFirst(E e) {  
    addBefore(e, header.next);  
}  

public void addLast(E e) {  
    addBefore(e, header);  
}  

总体来说,LinkedList效率高于ArrayList,即使在末尾插入,ArrayList也需要考虑可能的容量扩展对性能带来的影响

3,修改

和查询属于同一种情况

4,删除

指定位置的删除和插入属于同一种情况

除了删除指定位置数据,ArrayList和LinkedList都包含一个clear()方法用来清除所有数据

//ArrayList  
public void clear() {  
    modCount++;  

    // Let gc do its work  
    for (int i = 0; i < size; i++)  
        elementData[i] = null;  
    size = 0;  
}  
[java] view plain copy 在CODE上查看代码片派生到我的代码片
//LinkedList  
public void clear() {  
    Entry<E> e = header.next;  
    while (e != header) {  
        Entry<E> next = e.next;  
        e.next = e.previous = null;  
        e.element = null;  
        e = next;  
    }  
    header.next = header.previous = header;  
    size = 0;  
    modCount++;  
}  

由于都需要进行遍历,故效率相同。

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » ArrayList,LinkedList,Vector,Stack之间的区别

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我