1 数据结构之数组
数组对于每一门编程语言来说都是重要的数据结构之一，当然不同语言对数组的实现及处理也不尽相同。Java 语言中提供的数组是用来存储固定大小的同类型元素。你可以声明一个数组变量，如 numbers[100] 来代替直接声明 100 个独立变量 number0，number1，....，number99。数组一旦声明完毕，长度就固定了。
数组的声明、创建和初始化。
package cc.myall.demo01;import org.junit.Test;public class demo01 { @Test public void test01(){ int[] array = new int[10]; int len = array.length; for(int i=0; i < len; i++ ){ System.out.println(array[i]); //默认值是0 } }} 运行的结果就是打印出10个0。
数组最大的优点就是查询快，使用索引来进行查询；
数组的索引最好是有语义的。
1.1 二次封装自己的数组
基于java数组来二次封装自己的数组类（Array），使之成为动态数组，也就是java内置的ArrayList类。下面来自己实现一下。
size指向的是第一个没有元素的位置。
新建一个类Array，
package cc.myall.demo01;public class Array { private int[] data; //先假定这个数组只能装int类型 private int size; //构造函数，传入数组的容量来构造数组 public Array(int capacity) { data = new int[capacity]; size = 0; //实际大小初始为0 } public Array() { this(10); } //获取数组中元素的个数 public int getSize() { return size; } // 获取数组的容量 public int getCapacity() { return data.length; } //判断数组是否为空 public boolean isEmpty() { return size == 0; }} 测试：
package cc.myall.demo01;import org.junit.Test;public class demo01 { @Test public void test02(){ Array arr = new Array(); System.out.println(arr.getCapacity()); }} 运行结果：10
修改为支持泛型
public class Array{ private E[] data; //先假定这个数组只能装int类型 private int size; //构造函数，传入数组的容量来构造数组 public Array(int capacity) { data = (E[]) new Object[capacity]; size = 0; //实际大小初始为0 } public Array() { this(10); } //获取数组中元素的个数 public int getSize() { return size; } // 获取数组的容量 public int getCapacity() { return data.length; } //判断数组是否为空 public boolean isEmpty() { return size == 0; }}
1.2 使数组具有增删查改功能
addLast(int e) 时间复杂度O(1)
在最后一个元素的后面添加一个元素，原理就是在size处添加，然后让size加1。在Array类中添加addLast函数。
//在最后一个元素的后面添加元素 public void addLast(E e) { if(size == data.length) { throw new IllegalArgumentException("添加失败，数组已满"); } data[size] = e; size ++; } add(int index, int e) 时间复杂度O(n)
在元素中间的某个位置插入元素，让改位置及以后的元素一次移动一个位置，即size-1位置的一道size处，以此类推，移动后如下图，就腾出一个位置来：
这里说的腾出一个位置并不是说改位置为空，而是可以插入覆盖。代码如下
//向指定index处添加元素 public void add(int index, E e) { if(size == data.length) { throw new IllegalArgumentException("添加失败，数组已满"); } if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } for(int i = size-1; i >= index; i --) { data[i+1] = data[i]; } data[index] = e; size ++; } 再看addLast(int e) 时间复杂度O(1)
可以利用add函数改写，此时的index就是size。
//在最后一个元素的后面添加元素 public void addLast(E e) { add(size, e); }
addFirst(int e) 时间复杂度O(n)
可以利用add函数改写，此时的index就是0。在数组的第一个元素出插入元素
// 在数组的第一个位置添加元素 public void addFirst(E e) { add(0, e); } get 和 set时间复杂度O(1)
// 获取index索引处的元素 public E get(int index) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } return data[index]; }
// 改变index索引处的元素 public void set(int index, E e) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } data[index] = e; }
contains()时间复杂度O(n)
查找数组中是否包含元素e
//查找数组中是否有元素e public boolean contains(E e) { for(int i = 0; i < size; i++) { if(data[i].equals(e)) { return true; } } return false; }
find() 时间复杂度O(n)
//查找数组中元素e是否存在，返回索引，不存在返回-1 public int find(E e) { for(int i = 0; i < size; i ++) { if(data[i].equals(e)){ return i; } } return -1; }
remove() 时间复杂度O(n)
删除指定位置的元素，并且返回删除的元素。原理和添加一个元素类似。
// 删除指定位置index的元素 public E remove(int index) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } E ret = data[index]; for(int i = index + 1; i < size; i ++) { data[i-1] = data[i]; } size --; return ret; }
1.3 动态数组的实现
在往数组中添加元素的时候，如果数组已经满了，可以重新建一个新的较大容量的数组，把原来的数组的元素全部放入新数组中，这样就可以实现扩容。减少元素到一定程度就缩容。
//向指定index处添加元素 public void add(int index, E e) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=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 remove(int index) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } E ret = data[index]; for(int i = index + 1; i < size; i ++) { data[i-1] = data[i]; } size --; if(size == data.length / 2) { resize(data.length / 2); } return ret; }
时间复杂度O(n)
private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; for(int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; }
1.4 均摊时间复杂度和防止复杂度震荡
实现动态数组之后，addLast操作的时间复杂度最坏是O(n)的。
假设数组容量是n，n+1次操作触发一次扩容操作，总共2n+1次操作。平均每次addLast操作，进行两次基本操作。这样均摊计算，addLast操作的时间复杂度是O(1)，在这个例子里，均摊计算比最坏计算要有意义。
复杂度振荡产生：当addLast一个元素需要扩容时，复杂度是O(n)，然后又马上删除一个元素，要缩容，时间复杂度也是O(n)。均摊的计算方法就不能用了，产生震荡。
解决办法：让数据元素个数减少到容积的1/4时再缩容，仍缩为原来的一半。
// 删除指定位置index的元素 public E remove(int index) { if(index < 0 || index > size) { throw new IllegalArgumentException("添加失败，要求0<=index<=size"); } E ret = data[index]; for(int i = index + 1; i < size; i ++) { data[i-1] = data[i]; } size --; if(size == data.length / 4 && data.length / 2 != 0) { // Lazy方式 resize(data.length / 2); } return ret; }
代码: https://github.com/zhang-anan/DataStructure/tree/master/src/cc/myall/demo01