将Java中的数组进行二次封装成属于我们自己的数组
我们来简略回顾一下Java数组的基础概念：
- 数组最大的优点是可以快速查询，因为数组直接通过索引查询很快：array[2]。其数据结构是简单的线性序列，这使得元素访问非常快速，并且按照索引遍历数组方便
- 数组最好应用于“索引有语意”的情况
- 但并非所有有语意的索引都适用于数组，例如索引是身份证号这种长度的数字，就无法作为索引使用
- 而数组也同样可以处理“索引没有语意”的情况
- 数组的缺点：
- 根据内容查找元素速度慢
- 数组的大小一经确定不能改变
- 数组只能存储一种类型的数据
- 插入、指定删除元素效率低
- 未封装任何方法，所有操作都需要用户自己定义
“索引没有语意”的情况会遇到的问题：
- 索引没有语意，如何表示没有元素？
- 如何添加元素？如何删除元素？如何修改元素？
所以我们要将Java中的数组进行二次封装成属于我们自己的数组容器，以此来解决这些问题。我们将其封装在一个类中，该类命名为Array，通过提高各种增删改查的方法来操作数组。我们首先来编写这个Array类的基本框架：
/**
* @program: Data-Structure
* @description: 将Java中的静态数组进行二次封装成动态数组
* @author: 01
* @create: 2018-11-02 22:17
**/
public class Array {
/**
* 实际存放数据的数组
*/
private int[] data;
/**
* 表示数组中元素的个数
*/
private int size;
/**
* 传入数组的容量capacity构造Array
* 以便用户自定义数组的容量
*
* @param capacity 容量
*/
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
public Array() {
// 默认数组容量为10
this(10);
}
/**
* 获取数组中元素的个数
*
* @return 数组中元素的个数
*/
public int getSize() {
return size;
}
/**
* 获取数组的容量
*
* @return 数组的容量
*/
public int getCapacity() {
return data.length;
}
/**
* 返回数组是否为空
*
* @return 为空返回true，否则返回false
*/
public boolean isEmpty() {
return size == 0;
}
}
向数组中添加元素
在上一小节中，我们完成了Array基本框架的编写，这一小节我们来实现向数组中添加元素。最简单方式就是向数组的末尾添加元素，因为size始终会指向最后一个元素+1的位置，即数组的末尾第一个没有元素的位置。所以当添加元素的时候，我们将元素放置在size的位置即可，然后我们需要维护size，让其+1，这样size又继续指向数组的末尾，以此类推。
具体代码如下：
/**
* 向最后一个元素+1的位置添加一个新的元素
*
* @param e 新的元素
*/
public void addLast(int e) {
// 若数组已满则抛出异常，这里暂时先不做动态扩容
if (size == data.length) {
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
data[size] = e;
size++;
}
但在一些特殊的需求下，可能需要向指定的位置添加元素，例如数组中的元素是有序的，我希望把新元素插入到合适的位置，以保证数组内元素的有序性，如下图：
在这种情况下，实现思路就是将索引为1位置的元素及其后面的元素都往后挪一下。首先我们从100开始往后挪一，挪到索引为4的位置，99挪到索引为3的位置，88挪到索引为2的位置，此时索引1就空出来了，于是把77放入到索引为1的位置，最后还需要将size+1，让其指向数组末尾即可。
具体实现代码如下：
/**
* 在第index的位置下插入一个新的元素e
*
* @param index 索引
* @param e 新的元素
*/
public void add(int index, int e) {
// 若数组已满则抛出异常，这里暂时先不做动态扩容
if (size == data.length) {
throw new IllegalArgumentException("Add failed. Array is full.");
}
// 若索引为负数或索引大于size，则抛出异常
// 因为index大于size会造成数组内的元素不具有连续性，而index小于0则是无效的索引
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 从最后一个元素开始遍历数组中的元素，直到抵达index指向的索引位置
for (int i = size - 1; i >= index; i--) {
// 每个元素向后挪一位
data[i + 1] = data[i];
}
// 也可以直接使用数组拷贝的函数来实现这个逻辑，这里为了表明这个插入的逻辑，所以没有使用数组拷贝
// System.arraycopy(data, index, data, index + 1, size - index);
// 在index的位置插入新的元素
data[index] = e;
// 最后size需+1
size++;
}
实现了插入的方法后，我们就可以复用该方法，将之前的addLast简化，如下：
/**
* 向最后一个元素+1的位置添加一个新的元素
*
* @param e 新的元素
*/
public void addLast(int e) {
add(size, e);
}
同样的可以复用该方法，实现往数组的最前面添加一个新的元素，如下：
/**
* 往所有元素前添加一个新的元素
*
* @param e 新的元素
*/
public void addFirst(int e) {
add(0, e);
}
数组中查询元素和修改元素
有时候我们需要知道数组中有哪些元素以及数组当前的size和容量是多少，这时候我们就可以实现toString方法，将这些数据作为字符串打印出来，这也属于是查询的一种了。实现代码如下：
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i != size - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
除此之外，我们很多时候需要查询特定的元素以及修改特定的元素，这两个逻辑实现起来也很简单。用户在修改、查询特定元素时，都需将索引传递进来，所以在此之前我们来封装一个私有的方法，用于检查索引是否合法，这样其他方法就能复用这个逻辑，无需重复编写检查index的逻辑了。代码如下：
/**
* 检查索引是否合法
*
* @param index index
*/
private void checkIndex(int index) {
// 若索引为负数或索引大于等于size，则抛出异常
// 因为index大于等于size时用户会访问到无效的数据，而index小于0则是无效的索引
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Require index >= 0 and index <= size.");
}
}
然后实现查询特定的元素以及修改特定的元素的方法：
/**
* 获取index索引位置的元素
*
* @param index index
* @return index索引位置的元素
*/
public int get(int index) {
checkIndex(index);
return data[index];
}
/**
* 获取数组中的最后一个元素
*
* @return 最后一个元素
*/
public int getLast() {
return get(size - 1);
}
/**
* 获取数组中的第一个元素
*
* @return 第一个元素
*/
public E getFirst() {
return get(0);
}
/**
* 修改index索引位置的元素为e
*
* @param index index
* @param e e
*/
public void set(int index, int e) {
checkIndex(index);
data[index] = e;
}
包含，搜索和删除
当我们的数组里有一定数量的元素时，往往会遇到一个需求，就是查询这些元素中，是否包含某个特定的元素。还有一个常见的需求就是查询特定元素所在的索引位置，即搜索该元素并返回该元素所在的索引，若该元素不存在则返回一个特定的值，一般是-1，因为-1通常代表无效索引。
这两个逻辑实现起来也很简单，具体代码如下：
/**
* 查找数组中是否有元素e
*
* @param e e
* @return 有返回true，没有返回false
*/
public boolean contains(int e) {
int index = indexOf(e);
return index != -1;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
*
* @param e e
* @return 元素e所在的索引，或-1
*/
public int indexOf(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
接下来我们看看如何删除指定索引位置的元素，例如我要删除索引为1的元素，如下图：
其实这个删除与我们之前实现的插入逻辑差不多，反过来就可以了。如图中，我们需要删除的索引为1的元素，只需要把索引为2的元素往左移一格，覆盖索引为1的元素，然后索引为3的元素再往左移一格，覆盖索引为2的元素，接着索引为4的元素再往左移一格，覆盖索引为3的元素，以此类推...直到所有的元素都往左移一格后，将size-1即可。最后原本索引为1的元素已经被覆盖掉了，数组中不再有77这个元素，也就实现了删除的逻辑，如下图：
有的小伙伴可能会有疑问，最后数组中多了一个元素，会有影响吗？其实并不会有影响，因为size所指向的索引位置及其后面的索引位置，对于用户来说都是不可见的。而且数组在初始化的时候也是会有一个默认值的，例如这里是int类型的数据默认值就为0，由于用户只能访问到他添加进数组的元素，并且我们在上一小节中也编写了一个检查索引的方法，能够保证用户的索引是合法的，所以用户并不知道这里多了一个元素，也就不会有任何影响。当然你也可以在size-1后将这个多出来的元素给覆盖掉。最后还需要提一下的是，基本数据类型的数组可以不用管也无所谓，但如果是引用类型的数组的话，最好是将这个多出来的元素覆盖为null，这样该数据就能够快速的被垃圾回收掉，能够稍微优化一些性能。
具体的实现代码如下：
/**
* 从数组中删除index位置的元素，并返回删除的元素
*
* @param index index
* @return 被删除的元素
*/
public int remove(int index) {
checkIndex(index);
int ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// 同样的，这里也可以直接使用数组拷贝的函数来实现这个逻辑
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = 0;
return ret;
}
然后基于这个删除方法，我们还可以扩展一些便捷的方法提供给用户使用，如下：
/**
* 从数组中删除第一个元素，并返回删除的元素
*
* @return 被删除的元素
*/
public int removeFirst() {
return remove(0);
}
/**
* 从数组中删除最后一个元素，并返回删除的元素
*
* @return 被删除的元素
*/
public int removeLast() {
return remove(size - 1);
}
/**
* 从数组中删除元素e
*
* @param e 需要删除的元素
* @return 删除成功返回true，否则返回false
*/
public boolean removeElement(int e) {
int index = indexOf(e);
if (index != -1) {
remove(index);
return true;
}
return false;
}
/**
* 删除所有的元素e
*
* @param e 需要删除的元素
* @return 删除成功返回true，否则返回false
*/
public boolean removeAllElement(E e) {
for (int i = 0; i < size; ) {
if (data[i] == e) {
remove(i);
} else {
i++;
}
}
return indexOf(e) == -1;
}
使用泛型
到目前为止，我们的Array类只能够存储int类型的数据，但是其作为存储数据的容器，不应该只能存储一种类型的数据，而是能够存储任意类型的数据。为了让我们的Array类能够存储任意类型的数据，就需要使用到Java中的泛型。但是需要知道Java中的泛型是不能够接收基本数据类型的，只能够接收引用类型。不过好在Java中的基本数据类型都有各自的包装类，所谓包装类就是把基本类型封装成一个类，这样泛型就能够接收了。
这里不对泛型进行过多的介绍，如果对泛型不太清楚的话，可以查阅相关资料。使用泛型改造后的Array类代码如下：
/**
* @program: Data-Structure
* @description: 将Java中的静态数组进行二次封装成动态数组
* @author: 01
* @create: 2018-11-02 22:17
**/
public class Array<E> {
/**
* 实际存放数据的数组
*/
private E[] data;
/**
* 数组中元素的个数
*/
private int size;
/**
* 传入数组的容量capacity构造Array
* 以便用户自定义数组的容量
*
* @param capacity 容量
*/
public Array(int capacity) {
// java语法不支持直接new泛型或泛型数组，所以我们需要先new一个Object进行强转
data = (E[]) new Object[capacity];
size = 0;
}
public Array() {
// 默认数组容量为10
this(10);
}
/**
* 获取数组中元素的个数
*
* @return 数组中元素的个数
*/
public int getSize() {
return size;
}
/**
* 获取数组的容量
*
* @return 数组的容量
*/
public int getCapacity() {
return data.length;
}
/**
* 返回数组是否为空
*
* @return 为空返回true，否则返回false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 向最后一个元素+1的位置添加一个新的元素
*
* @param e 新的元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 往所有元素前添加一个新的元素
*
* @param e 新的元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在第index的位置下插入一个新的元素e
*
* @param index 索引
* @param e 新的元素
*/
public void add(int index, E e) {
// 若数组已满则抛出异常
if (size == data.length) {
throw new IllegalArgumentException("Add failed. Array is full.");
}
// 若索引为负数或索引大于size，则抛出异常
// 因为index大于size会造成数组内的元素不具有连续性，而index小于0则是无效的索引
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 从最后一个元素开始遍历数组中的元素，直到抵达index指向的索引位置
for (int i = size - 1; i >= index; i--) {
// 每个元素向后挪一位
data[i + 1] = data[i];
}
// 也可以直接使用数组拷贝的函数来实现这个逻辑，这里为了表明这个插入的逻辑，所以没有使用数组拷贝
// System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
/**
* 获取index索引位置的元素
*
* @param index index
* @return index索引位置的元素
*/
public E get(int index) {
checkIndex(index);
return data[index];
}
/**
* 获取数组中的最后一个元素
*
* @return 最后一个元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 获取数组中的第一个元素
*
* @return 第一个元素
*/
public E getFirst() {
return get(0);
}
/**
* 修改index索引位置的元素为e
*
* @param index index
* @param e e
*/
public void set(int index, E e) {
checkIndex(index);
data[index] = e;
}
/**
* 查找数组中是否有元素e
*
* @param e e
* @return 有返回true，没有返回false
*/
public boolean contains(E e) {
int index = indexOf(e);
return index != -1;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
*
* @param e e
* @return 元素e所在的索引，或-1
*/
public int indexOf(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素，并返回删除的元素
*
* @param index index
* @return 被删除的元素
*/
public E remove(int index) {
checkIndex(index);
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// 同样的，这里也可以直接使用数组拷贝的函数来实现这个逻辑
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = null;
return ret;
}
/**
* 从数组中删除第一个元素，并返回删除的元素
*
* @return 被删除的元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 从数组中删除最后一个元素，并返回删除的元素
*
* @return 被删除的元素
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 从数组中删除元素e
*
* @param e 需要删除的元素
* @return 删除成功返回true，否则返回false
*/
public boolean removeElement(E e) {
int index = indexOf(e);
if (index != -1) {
remove(index);
return true;
}
return false;
}
/**
* 删除所有的元素e
*
* @param e 需要删除的元素
* @return 删除成功返回true，否则返回false
*/
public boolean removeAllElement(E e) {
for (int i = 0; i < size; ) {
if (data[i] == e) {
remove(i);
} else {
i++;
}
}
return indexOf(e) == -1;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i != size - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
/**
* 检查索引是否合法
*
* @param index index
*/
private void checkIndex(int index) {
// 若索引为负数或索引大于等于size，则抛出异常
// 因为index大于等于size时用户会访问到无效的数据，而index小于0则是无效的索引
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Require index >= 0 and index <= size.");
}
}
}
动态数组
通过引入泛型现在我们的Array已经能够存储任意类型的数据了，并且在以上小节中也已经实现了基本的增删查改方法。现在就剩最后一个问题，Array内部的数组还是一个静态数组，而静态数组的容量是有限的，并且在初始化的时候就已经定下了大小无法改变。在实际开发中，我们通常无法确定数组的大小，我们希望当数组容量满了之后可以自动进行扩容，而不是抛出数组越界异常，所以我们要实现动态数组。
其实实现动态扩容的思路也很简单，当添加元素时发现数组容量满了之后，就创建一个容量更大的数组，例如创建一个比原来数组大两倍的一个新数组（ArrayList中为1.5倍），然后把旧数组的元素通通拷贝到新数组中，接着把data的引用指向这个新的数组即可，此时旧数组就会失去引用，从而被垃圾回收掉，这样一来就完成了扩容。剩下的逻辑还是和之前一样把新的元素照常添加到data中就行了。
具体的重置数组容量的方法代码如下：
/**
* 重置数组容量
*
* @param newCapacity 新的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// 可以直接使用数组拷贝的方式
// System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
然后修改添加元素的方法如下：
/**
* 在第index的位置下插入一个新的元素e
*
* @param index 索引
* @param e 新的元素
*/
public void add(int index, E e) {
// 若索引为负数或索引大于size，则抛出异常
// 因为index大于size会造成数组内的元素不具有连续性，而index小于0则是无效的索引
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 若数组已满则进行扩容
if (size == data.length) {
resize(data.length * 2);
}
// 从最后一个元素开始遍历数组中的元素，直到抵达index指向的索引位置
for (int i = size - 1; i >= index; i--) {
// 每个元素向后挪一位
data[i + 1] = data[i];
}
// 也可以直接使用数组拷贝的函数来实现这个逻辑，这里为了表明这个插入的逻辑，所以没有使用数组拷贝
// System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
在删除元素的时候，我们也希望数组中的元素少于数组容量的二分之一时就缩减容量，同样的只需要调用之前写好的resize方法即可。修改remove方法的代码如下：
/**
* 从数组中删除index位置的元素，并返回删除的元素
*
* @param index index
* @return 被删除的元素
*/
public E remove(int index) {
checkIndex(index);
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// 同样的，这里也可以直接使用数组拷贝的函数来实现这个逻辑
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = null;
if (size == data.length / 2) {
resize(data.length / 2);
}
return ret;
}
项目源码的GitHub地址如下：
简单的复杂度分析
我们经常会看到这些表示时间复杂度的符号：O(1), O(n), O(lgn), O(nlogn), O(n^2)
简单来说，大O描述的是算法的运行时间和输入数据之间的关系
我们来看一个简单的例子：
为什么要用大O，叫做O(n)，这是因为通常计算时间复杂度的时候都会忽略掉常数，实际上这个例子的实际时间为：T = c1 * n + c2。这里的常数主要是每一句代码的执行时间，为什么忽略常数呢，主要是因为很多时候这些常数无法估算，在不同的语言以及不同的操作系统和CPU上，同一句代码可能执行的时间都不一样，所以就需要忽略掉这些常数。
这种时间复杂度的分析实际上表示的是渐进时间复杂度，表示在最坏的时候时间复杂度是多少，即描述n在趋近与无穷的情况：
在O(n^2)的时间复杂度下，即便有一个300n的常数也是会被忽略的，因为在这个复杂度下，n就不算什么了。
我们来看看我们实现的Array类中主要方法的时间复杂度：
addLast(e)
由于这个方法只是在数组的末尾添加一个元素，因为只有一个操作，所以复杂度为O(1)
addFirst(e)
该方法在数组的最前面添加元素，然后数组内剩余的n个元素还需要向右移一格，所以复杂度为O(n)
add(index, e)
这个方法的复杂度与index的值息息相关，当index的值为0时，复杂度与addFirst一样，index的值为size时，复杂度就和addLast一样。而index取值范围是数组内元素的个数，所以每个索引被指定的可能性是相等的。之前我们说了，这种复杂度分析是表示在最坏的情况下复杂度是多少。而add方法最坏的情况下就是index为0，因为index为0时数组内所有的元素都需要挪位置，所以复杂度和addFirst是一样的，为O(n)
同样的基于最坏的情况，综合来说我们的添加操作，复杂度为O(N)：
而删除操作和添加操作逻辑上是相似的，所以删除操作的综合时间复杂度也是O(N)：
set(index, e)
这种根据索引修改元素的复杂度显然是O(1)，因为通过索引可以直接访问/操作数组元素
get(index)
同样的，该方法是根据索引直接获取元素，复杂度是O(1)
contains(e)
在不知道索引的情况下，我们只能通过遍历数组元素的方式去判断数组中是否包含某个元素，所以复杂度是O(n)
indexOf(e)
查询元素所在的索引也是同样的，最坏的情况需要遍历整个数组，复杂度是O(n)
动态数组主要方法的时间复杂度总结：
- 增：O(n)
- 删：O(n)
- 改：已知索引 O(1)；未知索引 O(n)
- 查：已知索引 O(1)；未知索引 O(n)
均摊复杂度和防止复杂度的震荡
在上一小节中我们看到了，resize过程的复杂度是O(n)，但是resize对性能的影响并非是那么的糟糕。因为我们在每次添加元素的过程中并非都会触发resize，所以在这种场景下使用最坏的情况去分析复杂度是不合理的。
