数组

1、数据结构分类

1.1 线性表

线性表顾名思义就是数据排成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。常见的线性表有：

1. 数组
2. 链表
3. 队列

4. 栈

   
   
   线性表

1.2 非线性表

与线性表相对应的就是非线性表，在非线性表中，数据之间并不是简单的前后关系。常见的非线性表有

1. 树

2. 图

   
   
   非线性表

2、什么是数组

数组是一种线性表数据结构，它使用一块连续的内存来存储数据类型相同的数据。

数组内存结构示意图

3、数组的特性

1. 支持随机查找，随机查找的的时间复杂度为O(1)。因为数组在内存中是连续存储的，可以根据索引和数组起始地址计算索引所对应的元素的地址，直接根据这个地址去查找，所以时间复杂度为O(1)。
2. 但是插入和删除操作比较低效，时间复杂度为O(n)。因为删除和插入数据的时候，为了保持数组内存的连续性，需要移动数组中原来的数据。

4、自定义ArrayList

自定义ArrayList，支持添加，插入，删除和查找数据，支持自动扩容。关键代码自动扩容

private void checkSize(int addSize) {
      if (addSize == elementData.length) {
          resize((int) (size * 1.5));//当申请的空间满了之后，扩大空间到原来的1.5倍
      }
}

private void resize(int capacity) {
     elementData = Arrays.copyOf(elementData, capacity);
}

插入

    public boolean add(int index, T t) {
        rangeCheckForAdd(index);
        checkSize(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = t;
        size++;
        return true;
    }

删除

   public T remove(int index) {
        checkIndex(index);
        T t = (T) elementData[index];
        size--;
        System.arraycopy(elementData, index + 1, elementData, index,
                size - index);
        return t;
    }

完整代码和测试用例，请查看github之MyArrayList

说明

文中图片来源：极客时间，王争《数据结构与算法之美》