什么是数组

• 数组是有序的元素序列，若将有限个类型相同的变量的集合命名，那么这个名称为数组名。
• 组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。
• 用于区分数组的各个元素的数字编号称为下标。
• 数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。这些有序排列的同类数据元素的集合称为数组。

数组的特点

1. 数组是相同数据类型的元素的集合。
2. 数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。
3. 数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

表现形式

1. 一维数组
   int[] a; String[] strs;

2. 二维数组
   int[][] a; String[][] strs;

随机访问

数组是由一块连续的内存空间和相同类型的数据构成的，所有他有个非常重要的特性：随机访问，它可以不需要通过遍历而直接取出某个下标中的元素。
而也正是由于需要保证数组的连续性，当进行插入和删除操作时，就必须做大量的迁移工作。
一维数组寻址公式： i_loc = init_loc + i * size

size 为元素的数据长度 如int类型为4个字节

example: init_loc = 100000

这也是为什么数组都是以0为下标开始的原因

手写一个ArrayList

//定义接口
public interface MyList<E> extends Iterable<E> {

    int size();

    void add(E e);

    void add(E e,int index);

    void remove(int index);

    void remove(E e);

    E get(int index);

    Iterator<E> iterator();

    int indexOf(E e);
}

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

    private Object[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity == 0) {
            data = new Object[DEFAULT_CAPACITY];
        } else {
            data = new Object[initialCapacity];
        }
    }
    @Override
    public void add(E element) {
        ensureAdd();    //判断是否即将越界，扩容
        data[size++] = element;
    }

    @Override
    public void add(E element, int index) { //6  3 size = 5
        ensureAdd();
        // 1 2 3 4 5  -> 1 2 3 6 4 5
        int srcPost = index;
        int destPost = index + 1;
        int length = size - index;
        System.arraycopy(data, srcPost, data, destPost, length);
        data[index] = element;
        size++;
    }

    private void ensureAdd(){
        if (size + 1 > data.length) {
            int newCapacity = data.length * 2;
            data = Arrays.copyOf(data, newCapacity);
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        return (E) data[index];
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int cursor;       // index of next element to return
            @Override
            public boolean hasNext() {
                return cursor != size;
            }
            @SuppressWarnings("unchecked")
            @Override
            public E next() {
                if (cursor >= size)
                    throw new NoSuchElementException();
                Object[] elementData = MyArrayList.this.data;
                if (cursor >= elementData.length)
                    throw new ConcurrentModificationException();
                return (E) elementData[cursor++];
            }
        };
    }

    @Override
    public void remove(int index) { // index = 2 size = 5
        //1 2 3 4 5  -> 1 2 4 5
        int srcPost = index + 1;
        int destPost = index;
        int length = size - index - 1; //2
        System.arraycopy(data, srcPost, data, destPost, length);
        data[--size] = null;
    }

    @Override
    public void remove(E element) { // 3 size=5
        //1 2 3 4 5 -> //1 2 4 5
        for (int i = 0; i < size; i++) {
            if (element == data[i]) {
                remove(i);
            }
        }
    }
    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (element == data[i]) return i;
        }
        return -1;
    }
    @Override
    public int size() {
        return size;
    }