自定义一个ArrayList

ArrayList特点和底层实现

ArrayList底层是用数组实现的存储。 特点：查询效率高，增删效率低，线程不安全。查看源码：

可以看出ArrayList底层使用Object数组来存储元素数据。所有的方法，都围绕这个核心的Object数组来开展。

我们知道，数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么它是怎么实现的呢?本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝到新数组，来实现扩容。 ArrayList的Object数组初始化长度为10，如果我们存储满了这个数组，需要存储第11个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素一起加入到新数组中，源码如下：

自定义一个ArrayList，体会底层原理

代码如下：

package com.msl.mycollection;

import javax.management.RuntimeErrorException;

/**
 * 自定义实现一个ArrayList,体会底层原理
 * @author Senley
 *
 */
public class MslArrayList<E> {

    private Object[] elementData;
    private int size;
    private static final int DEFALT_CAPACITY = 10;

    public MslArrayList() {
        elementData = new Object[DEFALT_CAPACITY];
    }

    public MslArrayList(int capacity) {
        if(capacity<0) {
            throw new RuntimeException("容器的容量不能为负数");
        }else if(capacity==0) {
            elementData = new Object[DEFALT_CAPACITY];
        }else {
            elementData = new Object[capacity];
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size==0?true:false;
    }

    public void add(E element) {
        //什么时候扩容
        if(size == elementData.length) {
            //扩容操作
            Object[] newArray = new Object[elementData.length + (elementData.length>>1)];//10-->10+10/2
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;     
        }
        elementData[size++] = element;
    }

    public E get(int index) {
        checkRange(index);
        return (E) elementData[index];
    }

    public void set(E element,int index) {
        checkRange(index);
        elementData[index] = element;
    }

    public void checkRange(int index) {
        //索引合法判断[0,size)
        if(index<0 || index>size-1) {
            //不合法
            throw new RuntimeException("索引不合法:"+index);
        }
    }

    public void remove(E element) {
        //将element和所有元素挨个比较,获得第一个比较为true的,返回.
        for(int i=0;i<size;i++) {
            if(element.equals(get(i))) {//容器中所有的比较操作都是用的equals而不是==
                //将该元素从此处移除
                remove(i);
            }
        }
    }

    public void remove(int index) {
        int numMoved = elementData.length-index-1;
        if(numMoved>0) {
            System.arraycopy(elementData, index+1, elementData, index, elementData.length-index-1);
        }
        elementData[--size] = null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i=0;i<size;i++) {
            sb.append(elementData[i]+",");
        }
        sb.setCharAt(sb.length()-1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MslArrayList m = new MslArrayList(20);
        for(int i=0;i<40;i++) {
            m.add("senley"+i);
        }
        System.out.println(m);
        m.set("test", 10);
        System.out.println(m.get(10));
        m.remove(3);
        System.out.println(m);
        m.remove("test");
        System.out.println(m);
        System.out.println(m.size);
        System.out.println(m.isEmpty());
    }
}

结果如下：

[senley0,senley1,senley2,senley3,senley4,senley5,senley6,senley7,senley8,senley9,senley10,senley11,senley12,senley13,senley14,senley15,senley16,senley17,senley18,senley19,senley20,senley21,senley22,senley23,senley24,senley25,senley26,senley27,senley28,senley29,senley30,senley31,senley32,senley33,senley34,senley35,senley36,senley37,senley38,senley39]
test
[senley0,senley1,senley2,senley4,senley5,senley6,senley7,senley8,senley9,test,senley11,senley12,senley13,senley14,senley15,senley16,senley17,senley18,senley19,senley20,senley21,senley22,senley23,senley24,senley25,senley26,senley27,senley28,senley29,senley30,senley31,senley32,senley33,senley34,senley35,senley36,senley37,senley38,senley39]
[senley0,senley1,senley2,senley4,senley5,senley6,senley7,senley8,senley9,senley11,senley12,senley13,senley14,senley15,senley16,senley17,senley18,senley19,senley20,senley21,senley22,senley23,senley24,senley25,senley26,senley27,senley28,senley29,senley30,senley31,senley32,senley33,senley34,senley35,senley36,senley37,senley38,senley39]
38
false