1 /**
  2  * 对比ArrayList和LinkedList的插入、随机读取效率、删除的效率
  3  * 
  4  * @ClassName: List_test_1
  5  * @author Xingle
  6  * @date 2014-5-29 下午5:25:11
  7  */
  8 public class List_test_1 {
  9     private static int COUNT_ = 100000;
 10 
 11     private static LinkedList<Integer> linkedList = new LinkedList<Integer>();
 12     private static ArrayList<Integer> arraylist = new ArrayList<Integer>();
 13     private static Vector<Integer> vector = new Vector<Integer>();
 14     private static Stack<Integer> stack = new Stack<Integer>();
 15 
 16     public static void main(String[] args) {
 17         // 插入
 18         insertByPosition(stack);
 19         insertByPosition(linkedList);
 20         insertByPosition(arraylist);
 21         insertByPosition(vector);
 22         
 23 
 24         // 读取
 25         readByPosition(stack);
 26         readByPosition(linkedList);
 27         readByPosition(arraylist);
 28         readByPosition(vector);
 29         
 30 
 31         // 删除
 32         deleteByPosition(stack);
 33         deleteByPosition(linkedList);
 34         deleteByPosition(arraylist);
 35         deleteByPosition(vector);
 36         
 37 
 38     }
 39 
 40     /**
 41      * 从list的指定位置删除COUNT个元素，并统计时间
 42      * 
 43      * @author xingle
 44      * @data 2014-5-29 下午5:33:55
 45      */
 46     private static void deleteByPosition(List<Integer> list) {
 47         long start = getCurrentTime();
 48         for (int i = 0; i < COUNT_; i++) {
 49             list.remove(0);
 50         }
 51         long end = getCurrentTime();
 52         long interval = end - start;
 53         System.out.println(getListName(list) + " : delete " + COUNT_
 54                 + " delete "+COUNT_+" elements from the 1st position use time：" + interval
 55                 + " ms");
 56 
 57     }
 58 
 59     /**
 60      * 根据position，从list中读取元素，并统计时间
 61      * 
 62      * @param list
 63      * @author xingle
 64      * @data 2014-5-29 下午5:32:58
 65      */
 66     private static void readByPosition(List<Integer> list) {
 67         long start = getCurrentTime();
 68         for (int i = 0; i < COUNT_; i++) {
 69             list.get(i);
 70         }
 71         long end = getCurrentTime();
 72         long interval = end - start;
 73         System.out.println(getListName(list) + " : read " + COUNT_
 74                 + " elements by position use time：" + interval
 75                 + " ms");
 76 
 77     }
 78 
 79     /**
 80      * 向list的指定位置插入COUNT个元素，并统计时间
 81      * 
 82      * @param list
 83      * @author xingle
 84      * @data 2014-5-29 下午5:32:16
 85      */
 86     private static void insertByPosition(List<Integer> list) {
 87         long start = getCurrentTime();
 88         for (int i = 0; i < COUNT_; i++) {
 89             list.add(0, i);
 90         }
 91         long end = getCurrentTime();
 92         long interval = end - start;
 93         System.out.println(getListName(list) + " : insert " + COUNT_
 94                 + " elements into the 1st position use time：" + interval
 95                 + " ms");
 96     }
 97 
 98     /**
 99      * 获取list名称
100      * 
101      * @return
102      * @author xingle
103      * @data 2014-5-29 下午5:38:02
104      */
105     private static String getListName(List<Integer> list) {
106         if (list instanceof LinkedList)
107             return "LinkedList";
108         else if (list instanceof ArrayList)
109             return "ArrayList";
110         else if (list instanceof Stack)
111             return "Stack";
112         else if(list instanceof Vector)
113             return "Vector";
114         else 
115             return "List";
116     }
117 
118     /**
119      * 获取当前时间
120      * 
121      * @return
122      * @author xingle
123      * @data 2014-5-29 下午5:35:33
124      */
125     private static long getCurrentTime() {
126         return System.currentTimeMillis();
127     }
128 
129 }

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

 /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

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