Java 集合系列08之 List总结(LinkedList, ArrayList等使用场景和性能分析)

Stack : insert 100000 elements into the 1st position use time：1640 ms
Vector : insert 100000 elements into the 1st position use time：1607 ms
LinkedList : insert 100000 elements into the 1st position use time：29 ms
ArrayList : insert 100000 elements into the 1st position use time：1617 ms

Stack : read 100000 elements by position use time：9 ms
Vector : read 100000 elements by position use time：6 ms LinkedList : read 100000 elements by position use time：10809 ms ArrayList : read 100000 elements by position use time：5 ms Stack : delete 100000 elements from the 1st position use time：1916 ms Vector : delete 100000 elements from the 1st position use time：1910 ms LinkedList : delete 100000 elements from the 1st position use time：15 ms ArrayList : delete 100000 elements from the 1st position use time：1909 ms

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

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

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

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

// 获取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的定义
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable // Vector的定义 public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

// 保存ArrayList中数据的数组
private transient Object[] elementData;

// 保存Vector中数据的数组
protected Object[] elementData;

// ArrayList构造函数。默认容量是10。
public ArrayList() {
    this(10); }

// Vector构造函数。默认容量是10。
public Vector() {
    this(10); } 

// 默认构造函数
ArrayList()

// capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。
ArrayList(int capacity) // 创建一个包含collection的ArrayList ArrayList(Collection<? extends E> collection)

// 默认构造函数
Vector()

// capacity是Vector的默认容量大小。当由于增加数据导致容量增加时，每次容量会增加一倍。
Vector(int capacity) // 创建一个包含collection的Vector Vector(Collection<? extends E> collection) // capacity是Vector的默认容量大小，capacityIncrement是每次Vector容量增加时的增量值。 Vector(int capacity, int capacityIncrement)

public void ensureCapacity(int minCapacity) {
    // 将“修改统计数”+1 modCount++; int oldCapacity = elementData.length; // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1” if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; elementData = Arrays.copyOf(elementData, newCapacity); } }

private void ensureCapacityHelper(int minCapacity) {
    int oldCapacity = elementData.length; // 当Vector的容量不足以容纳当前的全部元素，增加容量大小。 // 若 容量增量系数>0(即capacityIncrement>0)，则将容量增大当capacityIncrement // 否则，将容量增大一倍。 if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }

public Enumeration<E> elements() {
    // 通过匿名类实现Enumeration
    return new Enumeration<E>() { int count = 0; // 是否存在下一个元素 public boolean hasMoreElements() { return count < elementCount; } // 获取下一个元素 public E nextElement() { synchronized (Vector.this) { if (count < elementCount) { return (E)elementData[count++]; } } throw new NoSuchElementException("Vector Enumeration"); } }; }