我理解的数据结构（一）—— 数组(Array)
首先，我是一个phper，但是毕竟php是一个脚本语言，如果使用脚本语言去理解数据结构具有一定的局限性。因为脚本语言是不需要编译的，如果你的语法写的不错，可能执行起来会要比用一个更好的数据结构来的更快、更高效（在数据量不大的情况下）。而且数据结构是脱离任何一门语言存在的。所以，下面会选用java去更深入的理解数据结构。
注：这里不会去过多的解释java的语法。
一、定义一个数组的两种方式
int[] arr = new int[10];int[] arr = new int[] {10, 20, 30};
二、数组基础
- 数组的容量在数组一开始定义的时候就固定了。
- 数组最大的优点：根据索引快速查询。如：
arr[2]。 - 数组最好应用于“索引有语意”的情况下。
- 但并非所有有语意的索引都适用于数组：比如索引是一个人的身份证号，会开辟过大的空间，不现实。
- 下面会讨论数组“索引没有语意”的情况，基于java数组，二次封装属于我们自己的数组类，更深入的理解数组。
三、创建一个最基本的数组类
学习任何一个数据结构， CRUD必不可少。下面，让我们来一起一步步完善属于我们自己的数组的增、删、改、查 public class Array { // 数组的实际大小 private int size; // 数组 private int[] data; // 构造函数，根据传入的容纳量定义一个int类型的数组 public Array(int capacity) { data = new int[capacity]; size = 0; } // 重载，没有传入容纳量，定义一个长度为10的int类型数组 public Array() { this(10); } // 数组的实际大小 public int getSize() { return size; } // 数组的容纳量 public int getCapacity() { return data.length; } // 数组是否为空 public boolean isEmpty() { return size == 0; }} 四、增
//往数组的任意位置插入public void add(int index, int ele) { // 数组已满 if (size == data.length) { throw new IllegalArgumentException("add failed. arr is full"); } // 插入的索引位不合法 if (index < 0 || index >= size) { throw new IllegalArgumentException("add failed. index < 0 or index >= size"); } // 从index向后的所有元素均向后赋值 for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = ele; size++;}// 第一个位置插入public void addFirst(int ele) { add(0, ele);}// 最后一个位置插入public void addLast(int ele) { add(size, ele);} 五、查和改
// 查询index索引位置的元素public int get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get failed. index is illegal"); } return data[index];}// 查询ele元素的索引，不存在返回-1public int find(int ele) { for (int i = 0; i < size; i++) { if (data[i] == ele) { return i; } } return -1;}// 更新Index的元素public void set(int index, int ele) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get failed. index is illegal"); } data[index] = ele;} 六、删
// 根据索引删除数组中的第一个ele，返回elepublic int remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove failed. index is illegal"); } for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; return data[index];}// 删除第一个元素public int removeFirst() { return remove(0);}// 删除最后一个public int removeLast() { return remove(size - 1);}// 删除指定元素public void removeElement(int ele) { int index = find(ele); if (index != -1) { remove(index); }} 七、包含和重写toString
Overridepublic String toString() { StringBuffer res = new StringBuffer(); 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();}// 查询数组中是否包含元素elepublic boolean contain(int ele) { for (int i = 0; i < size; i++) { if (data[i] == ele) { return true; } } return false;} 注：通过以上方法我们已经创建了一个最最最最最基本的数组类（见下图）。当然，你也可以去添加一些自己需要的方法，例如：removeAll、findAll之类的。
但是，我们现在的数组只支持int类型，太过局限。接下来，我们去给我们的数组升华一哈~
八、使用泛型让我们的数组支持“任意”数据类型
首先，为什么我要在 任意这两个字加上引号，因为java的泛型不支持基本数据类型，只能是类的对象。 但是，这并不代表如果我们使用了泛型，就不可以使用基本数据类型了，因为每一个基本数据类型都有一个对应的 包装类。 使用泛型的时候，我们只需要传入对应的包装类即可。
java的基本数据类型
| 基本数据类型 | 包装类 |
|---|---|
| boolean | Boolean |
| byte | Byte |
| char | Char |
| short | Short |
| int | Int |
| long | Long |
| float | Float |
| double | Double |
所以，我们的代码只需要进行极小的改动即可：
public class ArrayNew<E> { // 数组的实际大小 private int size; // 数组 private E[] data; // 构造函数，根据传入的容纳量定义一个 E 类型的数组 public ArrayNew(int capacity) { // 强转 data = (E[]) new Object[capacity]; size = 0; } // 重载，没有传入容纳量，定义一个长度为10的int类型数组 public ArrayNew() { this(10); } // 数组的实际大小 public int getSize() { return size; } // 数组的容纳量 public int getCapacity() { return data.length; } // 数组是否为空 public boolean isEmpty() { return size == 0; } // 往数组的任意位置插入 public void add(int index, E ele) { // 数组已满 if (size == data.length) { throw new IllegalArgumentException("add failed. arr is full"); } // 插入的索引位不合法 if (index < 0 || index > size) { throw new IllegalArgumentException("add failed. index < 0 or index > size"); } // 从index向后的所有元素均向后赋值 for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = ele; size++; } // 第一个位置插入 public void addFirst(E ele) { add(0, ele); } // 最后一个位置插入 public void addLast(E ele) { add(size, ele); } // 查询index索引位置的元素 public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get failed. index is illegal"); } return data[index]; } // 查询ele元素的索引，不存在返回-1 public int find(E ele) { for (int i = 0; i < size; i++) { if (data[i].equals(ele)) { return i; } } return -1; } // 更新Index的元素 public void set(int index, E ele) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get failed. index is illegal"); } data[index] = ele; } // 根据索引删除数组中的第一个ele，返回ele public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove failed. index is illegal"); } E result = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = (data[i]); } // 空间释放，垃圾回收会自动回收 data[--size] = null; return result; } // 删除第一个元素 public E removeFirst() { return remove(0); } // 删除最后一个 public E removeLast() { return remove(size - 1); } // 删除指定元素 public void removeElement(E ele) { int index = find(ele); if (index != -1) { remove(index); } } // 查询数组中是否包含元素ele public boolean contain(E ele) { for (int i = 0; i < size; i++) { if (data[i].equals(ele)) { return true; } } return false; } @Override public String toString() { StringBuffer res = new StringBuffer(); 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(); }} 注：创建数组时，只需ArrayNew<Student> arr = new ArrayNew<>(20);即可。
九、动态数组
原理：其实，动态数组的原理非常简单，如果我们希望我们的数组具有可伸缩性，只需要我们在添加或者删除元素时判断size是否到达临界。然后去创建一个新capacity的数组，然后把旧数组的引用指向新数组即可。 所以，我们上述代码的改变极小，只需要改变add、remove即可。然后添加一个resize方法。
// 往数组的任意位置插入public void add(int index, E ele) { // 插入的索引位不合法 if (index < 0 || index > size) { throw new IllegalArgumentException("add failed. index < 0 or index > size"); } // 如果size == data.length，数组长度已满 if (size == data.length) { resize(data.length * 2); } // 从index向后的所有元素均向后赋值 for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = ele; size++;}// 根据索引删除数组中的第一个ele，返回elepublic E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove failed. index is illegal"); } E result = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = (data[i]); } // 空间释放，垃圾回收会自动回收 data[--size] = null; // 减小数组长度，不要浪费空间 if (size == data.length / 2 && size != 0) { resize(size); } return result;}// 自动伸缩数组private void resize(int newCapacity) { E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData;} 十、简单复杂度分析我们封装的数组
通过上面的分析和代码实现，我们封装了一个自己的数组，并且实现了一些数组 最基本的功能，包括支持增、删、改、查、支持任意数据类型以及动态数组。那么我们就来分析一下我们自己封装数组的复杂度。
| 操作 | 复杂度 |
|---|---|
| 增 | O(n) |
| 删 | O(n) |
| 改 | 已知索引O(1);未知索引O(n) |
| 查 | 已知索引O(1);未知索引O(n) |
但是：在我们的数组中，增和删我们都调用了resize方法，如果size < data.length，其实我们执行addLast复杂度只是O(1)而已（removeLast同理）。所以，我们应该怎么去分析resize方法所带来的复杂度呢？
十一、均摊复杂度和防止复杂度的震荡
（1）均摊复杂度
让我们拿 增 来举例
| 方法 | 复杂度 |
|---|---|
| addLast(ele) | O(1) |
| addFirst(ele) | O(n) |
| add(index, ele) | O(n/2) = O(n) |
| resize(newCapacity) | O(n) |
其实，在执行addLast的时候，我们并不是每次都会触发resize方法，更多的时候，复杂度只是O(1)而已。
capacity = 8，并且每一次添加操作都使用addLast，第9次addLast操作，触发resize，总共17次基本操作（resize方法会进行8次操作，addLast方法进行9次操作）。平均，每次addLast操作，进行2次基本操作（17 / 9 ≈ 2）。假设：capacity = n， n + 1次addLast，触发resize，总共进行了2n + 1次操作，平均每次addLast操作，进行了2次基本操作。 这样均摊计算，时间复杂度是O(1)！
（2）防止复杂度的震荡
让我们来假设这样一种情况： 当size == data.length时，我们执行了addLast方法添加一个元素，这个时候我们需要去执行resize方法，此时，addLast的复杂度为O(n)。 然后，我去removeLast，此时的removeLast复杂度也是O(n)。 再然后，我再去执行addLast。 . . .
有没有发现，在这样一种极端情况下，addLast和removeLast的复杂度变成了O(n)，其实，这个就是复杂度的震荡。
-
为什么我们会产生这种震荡？
-
add情况下，我们去扩容数组无可厚非。但是remove情况下，我们立刻去缩容数组就有点不合适了。
-
-
怎么去解决这种情况？
- 因为我们之前采取的措施是
Eager - 所以，我们采取一种
Lazy的方式：当size == data.length / 2，我们不要立刻缩容，当size == data.length / 4时，我们才去缩容，就可以很好的解决这种震荡。
- 因为我们之前采取的措施是
具体代码如下，其实只是对 remove进行了极小的改变 public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove failed. index is illegal"); } E result = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } // 空间释放，垃圾回收会自动回收 data[--size] = null; // 减小数组长度，不要浪费空间，防止震荡 if (size == data.length / 4 && data.length / 2 != 0) { resize(data.length / 2); } return result;} 原文地址：https://segmentfault.com/a/1190000016064569