ArrayList的優(yōu)化

當(dāng)向ArrayList中添加和刪除元素時(shí)都需要進(jìn)行元素的移動(dòng)，當(dāng)添加和刪除的是動(dòng)態(tài)數(shù)組的頭部元素，需要將數(shù)組中所有元素進(jìn)行移動(dòng)，其最壞情況的復(fù)雜度為O(n)。
那么能不能在添加和刪除元素時(shí)不進(jìn)行移動(dòng)或者少移動(dòng)元素呢？
我們可以在動(dòng)態(tài)數(shù)組的基礎(chǔ)上增加一個(gè)int front來(lái)記錄一下首元素的位置。
在進(jìn)行添加和刪除，肯定需要修改front，下面先來(lái)看下ArrayList的add和remove方法。

1、ArrayList的add方法

先來(lái)看下之前動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)

public void add(int index, E element) {
    checkIndexForAdd(index);
    ensureCapacity(size+1);
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size++;
}

可以看到這里是先將元素向后移動(dòng)，然后將數(shù)據(jù)設(shè)置到index的位置，過(guò)程如下


image.png

如果使用了front，在進(jìn)行元素添加時(shí)如何實(shí)現(xiàn)不移動(dòng)元素或者少移動(dòng)元素呢？下面分三種情況進(jìn)行分析：

1.1、當(dāng)向數(shù)組頭部添加元素

即調(diào)用add(0,element)。

image.png

由圖可知，在調(diào)用add(0,11)時(shí)，我們可以將元素添加到index=0的位置，然后將front減一此時(shí)front變成0。
image.png

如果再次調(diào)用add(0,55)，那么此時(shí)可以向index=5的位置添加元素。
image.png

有上面分析可知，在每次調(diào)用add(0,element)時(shí)，都會(huì)將元素添加到數(shù)組中角標(biāo)=front-1的位置，即elements[front-1]=element。當(dāng)front-1<0時(shí)，將元素添加到(front-1)+elements.length的位置。代碼如下：

if (index == 0) {
    front = index(-1);
    elements[front] = element;
}

// 修正index
private int index(int index) {
    index += front;
    if (index < 0)
        index += elements.length;
    else
        index = index % elements.length;
    return index;
}

1.2、當(dāng)向數(shù)組末尾添加元素

image.png

此時(shí)size=4，調(diào)用add(size,66)方法，會(huì)向index=5的位置添加元素，即elements[front+size]=66。
image.png

此時(shí)size=5，接著調(diào)用add(size,77)，會(huì)向index=0的位置添加元素，即elements[(front+size)%elements.length]=77。
代碼如下：

if (index == size) {
    elements[index(size)] = element;
}

1.3、當(dāng)向數(shù)組中其他位置添加元素

  • 如果index大于等于size的一半，則將元素向后移動(dòng)，然后設(shè)置指定位置的元素；如：向index=3,添加元素
    image.png
  • 如果index小于size的一半，則將元素向前移動(dòng)，并將front減一，然后設(shè)置指定位置的元素；
    image.png

具體代碼如下：

if (index >= size >> 1) { // 向后移動(dòng)
    for (int i = size - 1; i >= index; i--) {
        elements[index(i + 1)] = elements[index(i)];
    }
    elements[index(index)] = element;
} else { // 向前移動(dòng)
    for (int i = 0; i < index; i++) {
    elements[index(i-1)] = elements[index(i)];
      }
      front = index(-1);
      elements[index(index)] = element;
}

從上面代碼可知，在向數(shù)組頭部添加元素其實(shí)也是屬于index<size>>1的情況，只不過(guò)不需要移動(dòng)元素；
在向數(shù)組尾部添加元素屬于index>=size>>1的情況，只不過(guò)不需要移動(dòng)元素。

1.4、add方法完整代碼如下

public void add(int index, E element) {
    checkIndexForAdd(index);
    ensureCapacity(size + 1);
    if (index >= size >> 1) { // 向后移動(dòng)
        for (int i = size - 1; i >= index; i--) {
            elements[index(i + 1)] = elements[index(i)];
        }
    } else { // 向前移動(dòng)
        for (int i = 0; i < index; i++) {
            elements[index(i-1)] = elements[index(i)];
        }
        front = index(-1);
    }
    elements[index(index)] = element;
    size++;
}

// 修正index
private int index(int index) {
    index += front;
    if (index < 0)
        index += elements.length;
    else
        index = index % elements.length;
    return index;
}

2、ArrayList的remove方法

2.1、刪除數(shù)組頭部元素

刪除數(shù)組頭部元素很簡(jiǎn)單，只需要將頭部的數(shù)據(jù)置成null，然后將front向后移動(dòng)一位即可。


image.png

代碼如下

if (index == 0) {
    elements[front] = null;
    front = index(1);
}

2.2、刪除數(shù)組尾部元素

刪除尾部元素和動(dòng)態(tài)數(shù)組完全一樣，直接將index=size-1位置的元素置成null即可。
代碼如下

if (index == size - 1) {
    elements[index(size - 1)] = null;
}

2.3、刪除其他位置的元素

  • 如果index大于等于size的一半，則將元素向前移動(dòng)，然后設(shè)置指定位置的元素；如：向index=3,添加元素
    image.png
  • 如果index小于size的一半，則將元素向后移動(dòng)，并將front加一；
    如刪除index=2的元素
    image.png

    代碼如下：
if (index >= size >> 1) { // 向前移動(dòng)
    for (int i = index; i < size - 1; i++) {
        elements[index(i)] = elements[index(i + 1)];
    }
    elements[index(size - 1)] = null;
} else { // 向后移動(dòng)
    for (int i = index; i > 0; i--) {
        elements[index(i)] = elements[index(i - 1)];
    }
    elements[front] = null;
    front = index(1);
}

2.4、remove的完整代碼如下

public E remove(int index) {
    checkIndex(index);
    E oldE = elements[index(index)];
    if (index >= size >> 1) { // 向前移動(dòng)
        for (int i = index; i < size - 1; i++) {
            elements[index(i)] = elements[index(i + 1)];
        }
        elements[index(size - 1)] = null;
    } else { // 向后移動(dòng)
        for (int i = index; i > 0; i--) {
            elements[index(i)] = elements[index(i - 1)];
        }
        elements[front] = null;
        front = index(1);
    }
    size--;
    if (size == 0)
        front = 0;
    trim();
    return oldE;
}

3、總結(jié)

加入front后的動(dòng)態(tài)數(shù)組的增刪改查邏輯其實(shí)也很簡(jiǎn)單，在編寫(xiě)邏輯時(shí)先認(rèn)為front不存在，然后按照普通動(dòng)態(tài)數(shù)組的邏輯編寫(xiě)代碼，最后將牽扯到的index位置的地方，使用我們編寫(xiě)的矯正index的方法對(duì)index進(jìn)行矯正，獲取其真實(shí)的index即可。
完整代碼如下：

public class ArrayList2<E> extends AbstractList<E> {
    private E[] elements;
    private static final int DEFAULT_CAPACTITY = 10;
    // 記錄數(shù)組中首元素的位置，默認(rèn)為0
    private int front;

    public ArrayList2() {
        this(DEFAULT_CAPACTITY);
    }

    public ArrayList2(int capacity) {
        if (capacity <= DEFAULT_CAPACTITY)
            capacity = DEFAULT_CAPACTITY;
        elements = (E[]) new Object[capacity];
    }

    /**
     * 向指定位置添加元素
     * 
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        checkIndexForAdd(index);
        ensureCapacity(size + 1);
        if (index >= size >> 1) { // 向后移動(dòng)
            for (int i = size - 1; i >= index; i--) {
                elements[index(i + 1)] = elements[index(i)];
            }
        } else { // 向前移動(dòng)
            for (int i = 0; i < index; i++) {
                elements[index(i - 1)] = elements[index(i)];
            }
            front = index(-1);
        }
        elements[index(index)] = element;
        size++;
    }

    // 修正index
    private int index(int index) {
        index += front;
        if (index < 0)
            index += elements.length;
        else
            index = index % elements.length;
        return index;
    }

    /**
     * 擴(kuò)容
     * 
     * @param capactity
     */
    private void ensureCapacity(int capactity) {
        if (capactity >= elements.length) {
            int newCapacity = capactity + (capactity >> 1);
            System.out.println("擴(kuò)容 oldCapactity:" + elements.length + " newCapacity:" + newCapacity);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[index(i)];
            }
            elements = newElements;
            front = 0;
        }
    }

    /**
     * 獲取指定位置的元素
     * 
     * @param index
     * @return
     */
    public E get(int index) {
        checkIndex(index);
        return elements[index(index)];
    }

    /**
     * 設(shè)置index位置的元素
     * 
     * @param index
     * @param element
     */
    @Override
    public void set(int index, E element) {
        checkIndex(index);
        elements[index(index)] = element;
    }

    /**
     * 刪除指定位置的元素
     * 
     * @param index
     * @return
     */
    public E remove(int index) {
        checkIndex(index);
        E oldE = elements[index(index)];
        if (index >= size >> 1) { // 向前移動(dòng)
            for (int i = index; i < size - 1; i++) {
                elements[index(i)] = elements[index(i + 1)];
            }
            elements[index(size - 1)] = null;
        } else { // 向后移動(dòng)
            for (int i = index; i > 0; i--) {
                elements[index(i)] = elements[index(i - 1)];
            }
            elements[front] = null;
            front = index(1);
        }
        size--;
        if (size == 0)
            front = 0;
        trim();
        return oldE;
    }

    /**
     * 縮容：當(dāng)size==capactity/2時(shí)就進(jìn)行縮容,縮小為容量的一半
     */
    private void trim() {
        int newCapacity = elements.length >> 1;
        if (size <= newCapacity && elements.length > DEFAULT_CAPACTITY) {
            E[] newElement = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElement[i] = elements[index(i)];
            }
            System.out.println(elements.length + "縮容為" + newCapacity);
            front = 0;
            elements = newElement;
        }
    }

    /**
     * 刪除元素
     * 
     * @param element
     * @return
     */
    public E remove(E element) {
        return remove(indexOf(element));
    }

    /**
     * 返回指定元素的位置
     * 
     * @param element
     * @return 返回-1，表示未找到元素
     */
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (element == null) {
                if (elements[index(i)] == null)
                    return i;
            } else {
                if (element.equals(elements[index(i)]))
                    return i;
            }
        }
        return -1;
    }

    /**
     * 清空元素
     */
    public void clear() {
        for (E e : elements)
            e = null;
        size = 0;
        front = 0;
        // 縮容
        if (elements != null && elements.length > DEFAULT_CAPACTITY)
            elements = (E[]) new Object[DEFAULT_CAPACTITY];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size + " capactity=" + elements.length + "  front=" + front + "  [");
        for (int i = 0; i < elements.length; i++) {
            sb.append(elements[i]);
            if (i != elements.length - 1)
                sb.append(",");
        }
        sb.append("]");
        return sb.toString();
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容