手寫(xiě)簡(jiǎn)單的ArrayList

注釋都在代碼里，就是數(shù)組集合，實(shí)現(xiàn)簡(jiǎn)單的增刪改查，考慮的沒(méi)有jdk源碼詳細(xì)，歡迎指出bug

package com.ethanzyc.allinone.dataStructure.List;

/**
 * 手寫(xiě)一個(gè)數(shù)組集合
 * @author ethan
 * @date 2019/5/17 02:41
 */
public class MyArrayList<T> {
    /** array list 簡(jiǎn)單說(shuō)就是內(nèi)存地址在硬盤(pán)中是連續(xù)的數(shù)組 **/
    private T[] array;
    /** index相當(dāng)于數(shù)組的指針，通過(guò)指針來(lái)表示數(shù)組的長(zhǎng)度，以及定位添加的位置 **/
    private int index;

    /**
     * 數(shù)組集合無(wú)參構(gòu)造函數(shù)，不指定容量就默認(rèn)為10
     */
    public MyArrayList() {
        this(10);
    }

    /**
     * 數(shù)組集合指定長(zhǎng)度構(gòu)造函數(shù)
     * @param length
     */
    public MyArrayList(int length) {
        this.array = (T[]) new Object[length];
    }

    /**
     * 獲取數(shù)組的長(zhǎng)度，有多少值，size就是多少，不同于數(shù)組的容量
     * 其實(shí)是通過(guò)一個(gè)指針去控制
     * @return
     */
    public int size() {
        return index;
    }


    /**
     * 判斷是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 集合新增元素
     * @param t
     */
    public void add(T t) {
        add(t, index);
    }


    /**
     * 集合指定位置新增元素，
     * ##private##
     * @param t
     * @param index
     */
    public void add(T t, int index) {
        // 如果數(shù)組的長(zhǎng)度等于數(shù)組的指針，就擴(kuò)容
        if (array.length == size()) {
            int newLength = array.length * 2 - 1;
            enlargeList(newLength);
            System.out.println("擴(kuò)容到了" + newLength);
        }
        // 如果指定的位置大于list的長(zhǎng)度，就還是把這個(gè)值add到集合的末尾
        if (index > size()) {
            index = size();
        }
        // 如果插入的位置在他之前，就需要把他之后的元素都向后移一位，然后插入
        if (index < size()) {
            for (int i = size(); i > index-1 ; i--) {
                array[i] = array[i-1];
            }
        }
        array[index] = t;
        this.index++;

    }

    /**
     * 數(shù)組擴(kuò)容
     * @param newSize
     */
    public void enlargeList(int newSize) {
        if (newSize < size()) {
            return;
        }
        T[] oldArr = array;
        array = (T[]) new Object[newSize];
        for (int i = 0; i < oldArr.length; i++) {
            array[i] = oldArr[i];
        }
    }

    /**
     * 獲取下標(biāo)為index的函數(shù)
     * @param index
     * @return
     */
    public T get(int index) {
        return array[index];
    }


    /**
     * 設(shè)置下表為 index 的值，并返回原來(lái)的值
     * @param index
     * @param newVal
     * @return
     */
    public T set(int index, T newVal) {
        if (index < 0 || index > size()) {
            throw  new IndexOutOfBoundsException();
        } else {
            T toReturn = array[index];
            array[index] = newVal;
            return toReturn;
        }
    }

    /**
     * 移除元素
     * 數(shù)組因?yàn)樵趦?nèi)存中是連續(xù)的，所以刪除的時(shí)候把這個(gè)元素的后一位前移一位都行
     * 這也是數(shù)組集合增刪慢的原因
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size()) {
            throw  new IndexOutOfBoundsException();
        } else {
            // 將后面每一位賦值到前一位
            T oldVal = array[index];

            for (int i = index; i < size()-1; i++) {
                array[i] = array[i+1];
            }

            this.index--;

            return oldVal;
        }
    }

    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<Integer>(6);

        System.out.println(list.size());

        /** test1 start**/
//        list.add(1);
//        list.add(2);
//        list.add(3);
//        println(list);
//        list.add(222,10);
//        println(list);
        /** test1 end**/

        /** test2 start**/
        list.add(1);
        System.out.println(list.get(0));
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        println(list);
//        list.enlargeList(20);
        println(list);
        Integer oldVal = list.set(3, 20);
        System.out.printf("原來(lái)的值:%d", oldVal);
        System.out.println();
        println(list);
        Integer remove = list.remove(1);
        System.out.println(remove);
        println(list);
        /** test2 end**/
    }

    private static void println(MyArrayList list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }

    /**
     * 基礎(chǔ)知識(shí)：測(cè)試數(shù)組復(fù)制
     * 1.a = new int[...] 會(huì)把這個(gè)a與這個(gè)數(shù)組對(duì)象的引用斷開(kāi)，重新指向一個(gè)新的內(nèi)存地址，
     *   但是b與a之前的數(shù)組對(duì)象還是存在引用，所以a重新分配對(duì)象并不會(huì)影響到b
     * 2.a[?] = ? 改變的仍是a指向的內(nèi)存地址中的數(shù)據(jù)，由于b也是指向這個(gè)內(nèi)存地址，所以這樣操作會(huì)影響到b
     * @param args
     */
    public static void testCopy(String[] args) {
        int[] a = new int[]{1,2,4};
        println(a);

        int[] b = a;

        println(a);
        println(b);

        a = new int[2];
        println(a);
        println(b);

        int[] c = a;

        println(b);
        println(c);

        a[0] = 101;
        println(b);
        println(c);


    }

    private static void println(int[] list) {
        for (int aList : list) {
            System.out.print(aList + " ");
        }
        System.out.println("");
    }
}

改進(jìn)了下

package array;

/**
 * @author ethan
 * @date 2019/10/21 09:03
 */
@SuppressWarnings("unchecked")
public class ArrayList<E> {

    /**
     * 元素的數(shù)量
     */
    private int size;

    /**
     * 所有元素
     */
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOR_FOUND = -1;

    public ArrayList(int size) {
        if (size <= 0) {
            size = DEFAULT_CAPACITY;
        }
        elements = (E[])new Object[size];
    }

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public int size() {
        return size;
    }


    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(E element) {
        int i = indexOf(element);
        if (i == ELEMENT_NOR_FOUND) {
            return false;
        }
        return true;
    }

    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOR_FOUND;
    }

    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    public E set(int index, E element) {

        rangeCheck(index);

        E old = elements[index];
        elements[index] = element;
        return old;
    }

    public void add(E element) {
        add(size, element);
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacity(size + 1, elements.length);

        for (int i = size; i > index; i--) {
            elements[i] = elements[i-1];
        }
        elements[index] = element;
        size++;
    }

    private void ensureCapacity(int size, int length) {
        if (size > length) {
            E[] newElements = (E[]) new Object[length + (length >> 1)];
            for (int i = 0; i < size - 1; i++) {
                newElements[i] = elements[i];
            }
            elements = newElements;
        }
    }

    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;

        return old;
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index=" + index +", size=" + size);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index=" + index +", size=" + size);
        }
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            builder.append(elements[i]);
            if (i != size -1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.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)容

  • 概念 在Java中List有兩個(gè)，一個(gè)是java.util下的接口，另一個(gè)是java.awt下的類(lèi)，這里只討...
    still_loving閱讀 1,462評(píng)論 0贊 1
  • 傳送門(mén) 解讀阿里Java開(kāi)發(fā)手冊(cè)(v1.1.1) - 異常日志 前言 阿里Java開(kāi)發(fā)手冊(cè)談不上圣經(jīng)，但確實(shí)是大量...
    kelgon閱讀 4,464評(píng)論 4贊 50
  • 從百度文庫(kù)下載下來(lái)的，這里保存一份 別人的原代碼程序員怎樣閱讀 源碼就是指編寫(xiě)的最原始程序的代碼。 運(yùn)行的軟件是要...
    Albert陳凱閱讀 3,477評(píng)論 0贊 15
  • 澳大利亞作家邦妮·韋爾女士在《臨終前最后悔的五件事》一書(shū)中說(shuō)，她在八年里照顧了許多臨終的病人，當(dāng)她問(wèn)這些人有什么遺...
    喜歡空谷幽蘭閱讀 245評(píng)論 0贊 0
  • 1. 故事梗概 在阿富汗的阿米爾少爺和他的仆人哈桑有著快樂(lè)的童年，直到發(fā)生在風(fēng)箏節(jié)上的一次不幸的遭遇，從此改變了他...
    1519f8ccc7b0閱讀 1,049評(píng)論 0贊 2

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