博客

List接口:

public interface IMyList<E> {

    E set(int index, E elem);

    boolean add(E e);

    boolean remove(Object o);

    E remove(int index);

    int indexOf(Object o);

    E get(int index);

    int size();

    boolean isEmpty();

}

ArrayList实现:

import java.util.Arrays;

public class MyArrayList<E> implements IMyList<E> {

    private Object[] elementData;
    private int size;

    public MyArrayList(){
        this(10);
    }

    public MyArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
    }

    @Override
    public E set(int index, E elem) {
        E oldElem = elementData(index);
        elementData[index] = elem;
        return oldElem;
    }

    //添加元素前要确认空间是否足够,不够的话要进行扩容后再添加
    @Override
    public boolean add(E e) {
        ensureCapacity(size+1);
        elementData[size++] = e;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (o == null){
            for (int i=0, len=elementData.length; i<len; i++)
                if (o == elementData[i]){
                    fastRemove(i);
                    return true;
                }
        } else {
            for (int i=0, len=elementData.length; i<len; i++)
                if (o.equals(elementData[i])){
                    fastRemove(i);
                    return true;
                }

        }
        return false;
    }

    @Override
    public E remove(int index) {
        E oldElem = elementData(index);
        fastRemove(index);
        return oldElem;
    }

    private void fastRemove(int index){
        /**
         * 源码是这样的
         *      int numMoved = size - index - 1;
         *      if (numMoved > 0)
         *          System.arraycopy(elementData, index+1, elementData, index, numMoved);
         *
         */
        for (int i=index+1; i<size; i++){
            elementData[i-1] = elementData[i];
        }
        elementData[--size] = null;
    }

    @Override
    public int indexOf(Object o) {
        for (int i=0, len=elementData.length; i<len; i++)
            if (o == elementData[i])
                return i;
        return -1;
    }

    @Override
    public E get(int index) {
        return elementData(index);
    }

    @Override
    public int size() {
        return size;
    }

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

    private E elementData(int index){
        return (E)elementData[index];
    }

    //如果空间不够,要进行扩容,扩容后大小为原来的1.5倍
    private void ensureCapacity(int size){
        if (size > elementData.length){
            int oldCapacity = elementData.length;
            int newCapacity = (oldCapacity >> 1) + oldCapacity;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

测试代码:

public class Main {

    public static void main(String[] args) {
        IMyList<String> list = new MyArrayList<String>();
        for (int i=0; i<12; i++){
            list.add("s" + i);
        }

        list.remove("s3");

        for (int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }

    }
}

运行结果:

s0
s1
s2
s4
s5
s6
s7
s8
s9
s10
s11