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

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