面试或笔试中经常遇到像


ArrayList


和


LinkedList


以及


HashSet


和


HashMap


有什么区别，或者问你


HashMap


如何实现的。下面我们就自己实现简单的集合类，完成我们平时经常使用的效果，比如添加、移除、返回长度、自动扩容。

ArrayList

下面是


ArrayList


的常用方法

我们就照着功能实现这些方法，首先要知道


ArrayList


的底层实现是数组，而他比数组方便的地方在于可以自动扩容，数组一旦声明了大小就不可改变，那


ArrayList


底层是数组又是怎么实现数组扩容的呢。我们知道数组是引用数据类型，内容不可改变但是可以改变引用的指向，说白了就是重新创建一个新的更大的数组，然后把原来数组的内容拷贝到新的数组，再将原来的引用指向新的数组，这样就实现了数字的扩容

下面是


java


源码中实现数组扩容

下面我们来实现自己的代码

public class MyArrayList {
    //底层实现是一个对象数组，声明Object可以存放任意类型
    private Object[] elementData;
    //表示数组中元素的多少
    private int size;

    //有参构造器，可直接从源码中拷贝
    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else {
            //抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }
    //无参构造器，提供默认参数
    public MyArrayList(){
        this(10);
    }
    //实现添加方法
    public boolean add(Object object){
        ensureCapacityInternal(size);  // 验证是否需要扩容
        elementData[size++] = object;
        return true;
    }
    public boolean add(int index, Object obj){
        checkIndex(index);
        ensureCapacityInternal(size);  // 验证是否需要扩容
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index] = obj;
        size ++ ;
        return true;
    }

    //set方法，改变某一下标的值
    public Object set(int index , Object obj){
        checkIndex(index);
        Object oldValue = elementData[index];
        elementData[index] = obj;
        return oldValue;
    }

    //取值
    public Object get(int index){
        checkIndex(index);
        return elementData[index];
    }

    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //找出元素位置
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    //移除操作
    public Object remove(int index) {
        checkIndex(index);
        Object oldValue = elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    remove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    remove(index);
                    return true;
                }
        }
        return false;
    }

    // 验证是否需要扩容
    private void ensureCapacityInternal(int i) {
        if(i == elementData.length) {  //需要扩容
            //创建一个两倍于原数组的新数组
            Object[] newElementData =  new Object[size*2];
            //拷贝旧数组到新数组
            System.arraycopy(elementData,0,newElementData,0,elementData.length);
            //将引用指向新数组
            elementData = newElementData;
        }
    }

    //检查下标是否越界
    private void checkIndex(int index){
        if(index<0 || index >= size){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args){
        MyArrayList list = new MyArrayList();
        list.add("hello");
        list.add("world");

	list.add("ni");
	list.add("hao");

       System.out.println(list.size);

       System.out.println(list.elementData.length);

    }

}