1.数组基础
把数据码成一排进行存放
索引可以有语义；也可以没有语义
数组最大的优点：快速查询
数组最好应用于“所以有语意”的情况
但并非所有有语义的索引都是用于数组
身份证号
2.操作数组
1.向数组添加元素
2.在数组中查询和修改元素
3.在数组中搜索和删除元素
3.使用泛型
让数据结构可以放置“任何”数据类型
不可使基本数据类型，只能是类对象
boolean，byte，char，short，int，long，float，double
每个基本数据类型都有对应的包装类
Boolean，Byte，Char，Short，Int，Long，Float，Double
4.动态数组
新开辟数组，依次将新创建的数组代替原来的数组
5.简单的时间复杂度分析
O(1),O(n),O(lgn),O(nlogn),O(n^2)
大O简单秒杀价：运行时间和输入数据之间的关系，并且忽略常数
6.均摊复杂度分析和防止复杂度震荡
Array类
/** * @description: * @time:2019/5/29 */ public class Array<E>{ private E[] data; private int size; //构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data =(E[])new Object[capacity]; size = 0; } //无参数的构造函数，默认的数组容量capacity=10 public Array(){ this(10); } //获取数组中的元素个数 public int getSize(){ return size; } //获取数组的容量 public int getCapacity(){ return data.length; } //返回数组是否为空 public boolean isEmpty(){ return size == 0; } //向所有元素后新加一个元素 public void addLast(E e){ add(size,e); } //向所有元素前新加一个元素 public void addFirst(E e){ add(0,e); } //在第index个位置插入一个新元素e public void add(int index, E e){ if (index <0 || index > size){ throw new IllegalArgumentException("AddLast failed. Require index >= 0 and index < size"); } if (size == data.length){ resize(2 * data.length); } for (int i = size -1; i>=index;i--){ data[i+1] = data[i]; } data[index] = e; size ++; } //获取index索引位置的元素 public E get(int index){ if (index < 0|| index >= size){ throw new IllegalArgumentException("Get failed. Index is illegal"); } return data[index]; } //修改index所以位置的元素为e public void set(int index,E e){ if (index <0 || index >= size){ throw new IllegalArgumentException("Set failed. Index is illegal"); } data[index] = e; } //查找数组中是否有元素e public boolean contains(E e){ for (int i = 0; i < size; i ++){ if (data[i].equals(e)){ return true; } } return false; } //查找数组中元素e所在的索引，如果不存在索引e，则返回-1 public int find(E e){ for (int i=0; i<size; i++){ if (data[i].equals(e)){ return i; } } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if (index <0 || index >= size){ throw new IllegalArgumentException("Remove failed. Index is illegal"); } E ret = data[index]; for (int i=index+1;i<size;i++){ data[i-1] = data[i]; } size--; data[size] = null; //loitering objects != memory leak if (size == data.length/4 && data.length/2 != 0){ resize(data.length / 2);} return ret; } //从数组中删除第一个元素，返回删除的元素 public E removeFirst(){ return remove(0); } //从数组中删除最后一个元素，返回删除的的元素 public E removeLast(){ return remove(size - 1); } //从数组中删除元素e public void removeElement(E e){ int index = find(e); if (index != -1){ remove(index); } } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array:size = %d, capacity = %d\n",size,data.length)); res.append('['); for (int i = 0;i<size;i++){ res.append(data[i]); if(i != size -1) res.append(", "); } res.append(']'); return res.toString(); } private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; for (int i=0;i<size;i++){ newData[i] = data[i]; } data = newData; } }
