JAVA基礎(chǔ)MINA基礎(chǔ)學(xué)習(xí)

一般大家都知道ArrayList和LinkedList的大致區(qū)別：
    1.ArrayList是實(shí)現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
    2.對于隨機(jī)訪問get和set，ArrayList覺得優(yōu)于LinkedList，因?yàn)長inkedList要移動指針。
    3.對于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因?yàn)锳rrayList要移動數(shù)據(jù)。
    由于sun的開源所以我們可以從代碼的角度來看他們兩個之間的區(qū)別；
    先從構(gòu)造函數(shù)說起
    ArrayList 的默認(rèn)構(gòu)造函數(shù)
    public ArrayList() {
    this(10);
    }
    這個10是什么意思呢？再看看帶參數(shù)的構(gòu)造函數(shù)就明白了
    public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    this.elementData = new Object[initialCapacity];
    }
    Examda提示: ArrayList 分配了10個Object的數(shù)組存儲空間。
    下面看看LinkedList的構(gòu)造函數(shù)
    public LinkedList() {
    header.next = header.previous = header;
    }
    把鏈表的指針全部歸零，從上面的代碼可以看出LinkedList是個雙向的鏈表。
    下面再來看看兩者的get 和add方法有上面區(qū)別
    首先來看ArrayList add方法
    public boolean add(E e) {
    ensureCapacity(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
    }
    ensureCapacity 考試大提示: 這個函數(shù)是什么意思呢？看看就知道了
    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);
    }
    }
    原來這個確保ArrayList 存儲空間自動增長的，看了代碼就知道原來ArrayList 初始化存儲空間的大小是10 然后以后以1.5+1的級數(shù)增長，在這個過程中先new 原來空間的1.5倍＋1的新空間，然后把原來的數(shù)據(jù)拷貝到新的空間，所以說ArrayList 的添加數(shù)據(jù)的性能低于LinkedList，原來原因出在此處，那么以后就可以在new ArrayList 的時(shí)候，根據(jù)實(shí)際數(shù)據(jù)的多少，大概的指定一下ArrayList 的初始化大小，這樣避免的多次數(shù)據(jù)拷貝，提高了系統(tǒng)性能，哈哈又學(xué)到了優(yōu)化的一招。
    接下來繼續(xù)看LinkedList的add方法
    public boolean add(E e) {
    addBefore(e, header);
    return true;
    }
    private Entry addBefore(E e, Entry entry) {
    Entry newEntry = new Entry(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
    }
    就是雙向鏈表的添加操作，這是數(shù)據(jù)結(jié)構(gòu)里面的必修煉的功力之一，在添加的時(shí)候只要修改一下指針就ok了，沒有ArrayList 的增長空間拷貝數(shù)據(jù)的步驟，所以總體上看來在add的時(shí)候，LinkedList比ArrayList 快。
    下面來看看ArrayList 的get方法
    public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
    }
    RangeCheck 檢測訪問是否越界，然后根據(jù)索引下標(biāo)直接返回值，果然快。
    再來看看LinkedList的get方法
    public E get(int index) {
    return entry(index).element;
    }
    private Entry entry(int index) {
    if (index < 0 || index >= size)
    throw new IndexOutOfBoundsException("Index: "+index+
    ", Size: "+size);
    Entry 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;
    }
    一個一個去找是比較的慢，不過還是優(yōu)化了，如果要找的數(shù)小于等于size的一半就從頭往后找，要是大于size的一半就從后往前找，LinkedList的get和ArrayList 比起來確實(shí)慢了很多。