线性表，顾名思义就像一条线一样，线性表是有序的，这个“有序”不是从小到大之类的概念。当然与之对应就是散列表，散就是乱的，无序的。Java中List和Set，我们遍历List每次结果都是一样，这就是所谓的有序，遍历Set，每次出来的结果可能都不一样，这就是无序的。
数组是一种相同数据类型的元素组成的集合，是一种线性表，同样属于线性表结构的还有链表，队列，栈。
数组在内存需要连续的空间来存放，这就是为什么申明数组的时候一定要设置大小，因为只有设置了大小，才知道这个数组需要多大的内存空间，才能去内存中寻找大小合适的空间存放。正是因为它是连续的，而且都是有下标索引的，所以具有很好的随机访问性。
为什么数组具有很好的随机访问性？为什么数据可以根据下标访问？为什么下标要从0开始？
这就要说一下数组存储结构。
比如int[] arr = new int[2] 这个数组去内存开辟空间的时候，
假如arr在内存的位置是从1000开始的，那么
Arr[0] 在内存中的位置是 1000
Arr[1] 在内存中的位置是 1000 + arr[0]数据大小
Arr[2] 在内存中的位置是 1000 + arr[0]数据大小 + arr[1]数据大小
因为数组都是同一种数据类型所以每个元素的数据大小是一样的，换做如下表示就更清晰了
Arr[0] 在内存中的位置是 1000 + 0*dataSize(元素数据大小，比如int类型4个字节，long8个字节，对应在内存中的大小)
Arr[1] 在内存中的位置是 1000 + 1*dataSize
Arr[2] 在内存中的位置是 1000 + 2*dataSize
这样一来是不是每个元素的位置就刚好是索引位置乘以数据大小，这样我们就可以根据下标直接定位元素位置了。而且因为它是连续的空间，所以可以借助CPU的缓存机制，预读数据，索引访问效率更高。
但是有利就有弊，当我们想要插入和删除的时候，为了保证连续性，会做很大的搬迁工作。
而且容量有限，还需要注意数组越界问题。
当然如果数组长度声明的过大也会造成空间浪费。Java中的ArrayList就是用数组实现的，正因为如此，所以《effective java》中建议我们声明ArrayList预估容量，创建时就指定合适的容量，因为如果发生扩容，需要重新去创建一个更大的数组来存放，要寻找新的内存空间，一个是耗时，二来还要将原来数组的数据进行搬迁。
ArrayList是对数组进行了封装，提供更多的操作。如果不确定数据多少的情况下肯定选用ArrayList，如果确定了长度，而且有十分在乎性能，那就用数组。
简单实现一个自己的ArrayList，便于理解按照自己的逻辑写，并没有处理越界那些问题，和JDK的ArrayList里面的方法逻辑是有出入的：
package com.nijunyang.algorithm.list;
/**
* Description:
* Created by nijunyang on 2020/3/30 23:25
*/
public class MyArrayList<E>{
private static final int DEFAULT_SIZE = 10;
/**
* 数据（数组存放）
*/
private Object[] elements;
/**
* 当前存放到数组的index
*/
private int currentIndex;
/**
* 总容量大小（数组长度）
*/
private int size;
public MyArrayList() {
this.elements = new Object[DEFAULT_SIZE];
this.size = DEFAULT_SIZE;
}
public MyArrayList(int size) {
this.elements = new Object[size];
this.size = size;
}
public void add(E element) {
elements[currentIndex++] = element; //后++是先赋值了之后再++
//放到最后就进行扩容 容量翻倍
if (currentIndex == size) {
this.size = this.size * 2 ;
Object newData[] = new Object[this.size];
for (int i = 0; i < elements.length; i++) {
newData[i] = elements[i];
}
this.elements = newData;
}
}
/**
* 按索引移除
* @param index
*/
public void remove(int index) {
if (index >= 0 && index < currentIndex) {
//后面的元素来覆盖当前这个元素，然后后面的全部前移
for (int j = index; j < this.elements.length - 1; j++) {
elements[j] = elements[j + 1];
//null 就后不用再移动了
if (elements[j] == null) {
break;
}
}
this.currentIndex--;
}
}
public E get(int index) {
if (index >= 0 && index < currentIndex) {
return (E) this.elements[index];
}
return null;
}
public int size() {
return currentIndex;
}
public String toString() {
if (currentIndex == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i < currentIndex; i++) {
if (i == currentIndex - 1) {
sb.append(elements[i].toString());
sb.append(']');
break;
}
sb.append(elements[i].toString());
sb.append(',');
}
return sb.toString();
}
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList<>(2);
myArrayList.add(0);
myArrayList.add(1);
myArrayList.add(2);
System.out.println(myArrayList.get(0));
System.out.println(myArrayList.size());
System.out.println(myArrayList);
myArrayList.remove(1);
System.out.println(myArrayList.get(0));
System.out.println(myArrayList.size());
System.out.println(myArrayList);
}
}
