JAVA中ArrayList的实现与分析

ArrayList 单链表

是一种可增长的数组实现
优点在于，对get和set的调用花费常数时间
缺点是add和remove的代价昂贵

实现

package com.leeyf.myarraylist;

import java.util.Iterator;

public abstract class MyArrayList<T> implements Iterable<T> {
    //初始化容器容量
    private static final int DEFAULT_CAPACITY = 10;
    //当前项数
    private int theSize;
    //基础数组
    private T[] theItems;

    public MyArrayList() {
        doClear();
    }

    //清空链表
    public void clear() {
        doClear();
    }

    private void doClear() {
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    //返回当前项数
    public int size() {
        return theSize;
    }

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

    //缩减容器大小
    public void trimToSize() {
        ensureCapacity(size());
    }

    public T get(int index) {
        if (index < 0 || index >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return theItems[index];
    }

    public T set(int index, T newVal) {
        if (index < 0 || index >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        T old = theItems[index];
        theItems[index] = newVal;
        return old;
    }

    public void ensureCapacity(int newCapacity) {
        //如果新设置的大小比当前容器大小小，则不执行
        if (newCapacity < size()) {
            return;
        }

        T[] old = theItems;
        theItems = (T[]) new Object[newCapacity]; //泛型数组的创建是非法的.这里创建一个泛型类型界限的数组,然后使用一个数组进行类型转换来实现.
        for (int i = 0; i < size(); i++) {
            theItems[i] = old[i];
        }
    }

    public boolean add(T x) {

        add(size(), x);
        return true;
    }

    public void add(int index, T x) {
        //如果链表已满,则扩容
        if (theItems.length == size()) {
            ensureCapacity(size() * 2 + 1);
        }
        //从最后一项开始到index，后移一位
        for (int i = theSize; i > index; i--) {
            theItems[i] = theItems[i - 1];
        }
        theItems[index] = x;
        theSize++;
    }

    public T remove(int index) {
        T removeItem = theItems[index];
        //从index到最后一项，前移一位
        for (int i = index; i < size() - 1; i++) {
            theItems[i] = theItems[i + 1];
        }
        theSize--;
        return removeItem;
    }

    public java.util.Iterator<T> iterator() {
        return new ArrayListIterator();
    }


    private class ArrayListIterator implements java.util.Iterator<T> {
        private int current = 0;

        public boolean hasNext() {
            return current < size();
        }

        public T next() {
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            return theItems[current++];
        }

        public void remove() {
            MyArrayList.this.remove(--current);
        }
    }

}

分析

ensureCapacity是对容器大小的调整,既可以用来容器扩容,也可做收缩基础数组,只不过当指定容器至少和原大小一样时才适用.
第64行中,因为泛型数组的创建是非法的,所以我们用一个数组来类型转换
两个add方法,第一个add是添加到表的末端的并通过调用来添加到指定位置的.第二个则是添加到指定位置.
remove与add相似,只是在指定位置后的元素,前移一位.
ArrayListIterator内部类则是对Iterator接口的实现类.ArrayListIterator存储当前位置的概念,并提供了hasNext,next和remove的实现.
- 当前位置表示要被查看的下一元素的数组下标,所以初始值为0\