1、数据结构分类
1.1 线性表
线性表顾名思义就是数据排成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。常见的线性表有：
- 数组
- 链表
- 队列
-
栈
线性表
1.2 非线性表
与线性表相对应的就是非线性表，在非线性表中，数据之间并不是简单的前后关系。常见的非线性表有
- 树
-
图
非线性表
2、什么是数组
数组是一种线性表数据结构，它使用一块连续的内存来存储数据类型相同的数据。
数组内存结构示意图
3、数组的特性
- 支持随机查找，随机查找的的时间复杂度为O(1)。因为数组在内存中是连续存储的，可以根据索引和数组起始地址计算索引所对应的元素的地址，直接根据这个地址去查找，所以时间复杂度为O(1)。
- 但是插入和删除操作比较低效，时间复杂度为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
说明
文中图片来源：极客时间，王争《数据结构与算法之美》
