数据结构---数组
线性表，顾名思义就像一条线一样，线性表是有序的，这个“有序”不是从小到大之类的概念。当然与之对应就是散列表，散就是乱的，无序的。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); } }