Java——模拟实现ArrayList

Java——模拟实现ArrayList

本文主要是自己动手实现了下ArrayList，让自己有个更深刻的印象。

import Test1.Array;
import java.util.Arrays;

public class ArrayList { //使用泛型
    private E[] elementData;
    private int size;

    private static final int DEFAULT_CAPACITY = 10;

    //构造方法
    ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    ArrayList(int initCapacity) {
        if (initCapacity <= 0)
            initCapacity = DEFAULT_CAPACITY;

        elementData = (E[])new Object[initCapacity];
    }

    //扩容
    public void ensureCapacity(int size){
        int oldCapacity = elementData.length;
        if(size >= oldCapacity){
            int newCapacity = oldCapacity + (oldCapacity>>1); // 扩容1.5倍
            elementData = Arrays.copyOf(elementData,newCapacity); //复制指定数组有指定的程度
        }
    }

    //越界
    public void checkIndex(int index){
        if(index < 0 || index > size)
            throw new IndexOutOfBoundsException("add:index越界");
    }

    //尾插
    public boolean add(E e){
        add(size,e);
        return true;
    }

    //插入任意位置
    public void add(int index,E e){

        checkIndex(index); //检查是否越界

        ensureCapacity(size); //需要的情况下扩容

        for (int i = size-1;i >= index;i--) //找到插入位置
            elementData[i+1] = elementData[i];

        elementData[index] = e; //指定位置赋值
        size ++;
    }

    //获取index位置的元素
    public E get(int index){
        checkIndex(index);
        return elementData[index];
    }

    //将某一位置元素设为e
    public E set(int index,E e){
        checkIndex(index);
        elementData[index] = e;
        return e;
    }

    //删除index位置的元素
    public E remove(int index){
        checkIndex(index);

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

        size --;
        return e;
    }

    //删除某一元素
    public boolean remove(E e){
        remove(indexOf(e));
        return true;
    }


    //清空表
    public void clear(){
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }

    //判断某一元素是否在表中
    public boolean contains(E e){
        return !(-1 == indexOf(e));
    }

    //获取第一次遇见元素e的位置
    public int indexOf(E e){
        for (int i = 0; i < size ; i++) {
            if (e == elementData[i]){
                return i;
            }
        }
        return -1;
    }

    //获取最后一次遇见元素e的位置
    public int lastIndexOf(E e){
        for (int i = size-1; i >= 0 ; i--) {
            if (e == elementData[i]){
                return i;
            }
        }
        return -1;
    }

    //获取一个子序列
    ArrayList subList(int fromIndex,int toIndex){
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("输入参数非法");
        checkIndex(fromIndex);
        checkIndex(toIndex);

        ArrayList list = new ArrayList<>(toIndex-fromIndex);
        for (int i = fromIndex; i <= toIndex; i++) {
            list.add((E)elementData[i]);
        }

        return list;
    }

    @Override
    public String toString() {
        String s = "[" ;
        for(int i = 0; i < size; i++){
            s += elementData[i];
            if (i != (size-1))
                s += ",";
        }
        s += "]" ;
        return s;
    }

    public static void main(String[] args) {
        ArrayList array = new ArrayList<>(10);
        System.out.println("size:"+array.size);
   
        System.out.println("------------插入元素------------");
        array.add(1);
        array.add(2);
        array.add(3);
        array.add(4);
        array.add(5);
        array.add(6);
        array.add(7);
        System.out.println("size = " + array.size);
        System.out.println("array = " + array);

        System.out.println("----------位置3插入8------------");
        array.add(3,8);
        System.out.println("array = " + array);

        System.out.println("------------获取位置6的元素------------");
        System.out.println("array = " + array.get(6));

        System.out.println("------------位置2设为9------------");
        array.set(2,9);
        System.out.println("array = " + array);

        System.out.println("------------删除位置2的元素------------");
        array.remove(2);
        System.out.println("array = " + array);

        System.out.println("------------删除元素5------------");
        array.add(2);
        array.add(2);
        array.add(2);
        System.out.println("array = " + array);
        array.remove((Integer) 5);
        System.out.println("删除元素5后的 array = " + array);

        System.out.println("------------清空表------------");
        array.clear();
        System.out.println("array = " + array);

        System.out.println("------------判断某一元素是否在表内------------");
        array.add(1);
        array.add(2);
        array.add(3);
        array.add(4);
        array.add(2);
        array.add(6);
        array.add(7);
        System.out.println("array = " + array);
        System.out.println("2是否在表内 = " + array.contains(2));
        System.out.println("10是否在表内 = " + array.contains(10));

        System.out.println("------------第一次遇到元素位置------------");
        System.out.println("array = " + array);
        System.out.println("array.indexOf(2) = " + array.indexOf(2));

        System.out.println("------------最后一次遇到元素位置------------");
        System.out.println("array = " + array);
        System.out.println("array.lastIndexOf(2) = " + array.lastIndexOf(2));

        System.out.println("------------获取一个子序列------------");
        System.out.println("array = " + array);
        System.out.println("array.subList(1,4) = " + array.subList(1, array.size));
    }
}